вторник, 21 июля 2015 г.

"Змейка" на двух этажах

Соедините одинаковые числа "змейками", которые удовлетворяют следующим условиям:
1) на каждом из этажей змейка является связным множеством клеток.;
2) количество клеток, занятых каждой "змейкой" (в сумме на обоих этажах), равно числам, стоящим в ее концах.
3) любые две соседних клетки "змейки" имеют общую сторону или расположены одна над другой (на двух этажах)
4) каждая из 32 клеток входит не более чем в одну "змейку"

четверг, 9 июля 2015 г.

"5 пиратов" наоборот

Классическая математическая игра, в которой пятерым пиратам предлагается разделить между собой клад из 100 монет, имеет менее известную вариацию, в которой пиратов 100, а монет всего пять.

100 пиратов должны разделить между собой 5 золотых монет. Согласно пиратскому кодексу, делёж добычи происходит следующим образом. Все пираты строго упорядочены по старшинству. 100-й (самый старший) пират предлагает способ распределить монеты между присутствующими и выносит его на голосование. При этом сам он участия в голосовании не принимает. Если его способ получает одобрение хотя бы половины остальных участников, то так и происходит, и на этом делёж заканчивается. В противном случае его выкидывают за борт, а право предложить свой способ получает следующий по старшинству (99-й), и так далее.

Принимая решение, пираты руководствуются следующими приоритетами:
1. Каждый пират хочет выжить.
2. Каждый пират хочет забрать себе как можно больше.
3. При прочих равных условиях, каждый пират предпочтёт выкинуть другого за борт.
Чьё предложение будет в итоге принято?

понедельник, 6 июля 2015 г.

Дележ на троих

Профессор, доцент и аспирант получили на троих грант - 15 золотых монет (монеты неделимы). Чтобы его разделить, они разработали следующий алгоритм. Сначала все по очереди, начиная с профессора и заканчивая аспирантом, предлагают свой вариант дележа. Потом каждый голосует - выбирает то из сделанных предложений, в котором ему достается больше монет. Если таких предложений несколько, он голосует за первое из них. Предложение, получившее больше одного голоса, принимается, и грант делится в соответствии с ним. Если такого предложения не оказалось, то никто ничего не получает. 
Каждый хочет получить как можно большее число монет. Кроме того, все прекрасно умеют логически мыслить. Как окажутся разделены монеты?
[Два уточнения. 1) То, что каждый хочет получить как можно больше, является для героев задачи common knowledge, то есть этот факт все они знают, как и факт "все знают, что все это знают" - и так далее 2) если кто-либо из героев понимает, что у него есть несколько вариантов, приводящих в итоге к одинаковому для него результату, то он выбирает любой из этих вариантов случайным образом.] 

P.S. Автор благодарит Игоря Кривоконя за улучшение исходной версии задачи, а Константина Уварина - за "имена" персонажей.