Спички
В коробке лежат 300 спичек. Двое играющих поочередно имеют право взять из коробки любое количество спичек, но не более половины имеющихся в ней. Проигрывает тот, кто не сможет сделать очередного хода. Кто выиграет и какова выигрышная стратегия?
Ответ: Выигрывает первый игрок. Выигрышными являются позиции, при которых в коробке остается 2n-1 спичка. Поэтому, первый ход - оставить 255 спичек.
Натуральные числа
Двое игроков по очереди называют натуральные числа, причем следующее число должно быть строго меньше предыдущего, но не меньше половины предыдущего. Проигрывает тот, кто будет вынужден назвать число 1. Первым ходом первый игрок назвал 2003. Кто выиграет?
Ответ: Выигрывает второй. Проводя анализ с конца, получаем, что выигрышными позициями для второго будут 1535, 767, 383, 191, 95, 47, 23, 11, 5, 2
Ящик апельсинов
Чебурашка и Шапокляк поедают ящик апельсинов. За один ход Шапокляк может либо съесть один хороший апельсин, либо заменить два хороших апельсина на два гнилых, Чебурашка может либо съесть два хороших апельсина, либо съесть один хороший и выкинуть один гнилой. Первым ходит Чебурашка. Проигрывает тот, кто не сможет сделать ход.
Кто выигрывает при правильной игре, если изначально в ящике было n хороших и ни одного гнилого апельсина?
Ответ: При n = 3k, n = 3k+1 выигрывает Шапокляк. Начинает Чебурашка, т.к. гнилых нет, следовательно, он может только съесть два хороших апельсина. Шапокляк каждым своим ходом съедает один хороший и т.д. После k ходов с обеих сторон останется либо 0 (в первом случае) и 1 (во втором случае) апельсинов, и ход Чебурашки, следовательно, он проиграл.
Пять разбойников делят добычу
Пять разбойников делят добычу в 50 золотых. Делят добычу они следующим образом:
1) Самый старший из них предлагает вариант дележа добычи.
2) Все (включая самого старшего) голосуют.
3) Если за этот вариант дележа проголосует более половины разбойников, то на этом дележ добычи заканчивается.
4) В противном случае все остальные убивают самого старшего разбойника и дележ начинается снова с пункта 1).
Каждый разбойник в первую очередь хочет сохранить себе жизнь, на втором месте в его списке приоритетов стоит получение как можно большей доли.
Каков будет результат дележа?
Ответ: Проще всего рассуждать с конца. Если разбойников останется всего двое, то какой бы вариант ни предложил старший из них, младший никогда не согласится, убъет старшего и всё заберет себе. Старший это понимает, поэтому будет стараться всеми силами не допустить такого развития событий, когда он останется один на один с младшим.
Следовательно, если разбойников будет трое, то какой бы вариант разделения ни предложил самый старший, то средний с таким разделением добычи согласится. Поэтому если бы разбойников было бы трое, то старший бы все оставил себе, а средний бы его поддержал.
Если разбойников будет четверо, то самый старший может дать "взятку" по одной монете двум самым младшим, оставив себе всё остальное. В результате они оба поддержат его, ведь в противном случае четвертого убъют, а при дележе добычи на троих как мы видели двум младшим вообще ничего не останется.
Ну а если разбойников пять, то самому старшему достаточно дать взятку в одну монету третьему (который при дележе на четверых вообще остается без денег) и еще одну взятку в 2 монеты кому-нибудь из двух самых младших. В условии не было четко оговорено поведение разбойника, если бы ему предложили одну и ту же взятку в одну монету, поэтому у самого старшего бандита останется 47 или 48 монет.
Сосисочная стратегия
Имеется цепочка сосисок длины n. Два кота по очереди перегрызают по одной перемычке между сосисками и съедают образовавшиеся одиночные сосиски. Выигрывает тот, кто съест большее число сосисок. Какой должны быть выигрышная стратегия?
Ответ: При нечетном n выигрывает второй кот, при четном n - первый.
В самом деле, пусть n = 2k+1 нечетно. Занумеруем все сосиски подряд числами от 1 до n . Сосиску с номером k+1 будем называть центральной. Второму коту каждым ходом нужно перегрызать перемычку, симметричную той, которую перегрыз на предыдущем ходу первый кот (относительно центральной сосиски). Тогда он съест сосисок не меньше, чем первый, причем первый при такой игре не сможет съесть центральную сосиску (так как ее концы (перемычки) симметричны друг другу относительно этой сосиски). Значит, второй кот съест не менее k+1 сосиски и выиграет.
Пусть теперь n = 2k четно. Занумеруем все сосиски подряд числами от 1 до n . В этом случае первый кот должен первым ходом съесть одну из крайних сосисок (скажем, последнюю). Тогда перед вторым котом окажется нечетное число сосисок, и из них он сможет съесть только меньше половины, если первый игрок будет пользоваться стратегией второго для случая нечетного n. (Другими словами, далее первому игроку надо отвечать на ходы второго симметричными (относительно k+1-ой сосиски) ходами.) При такой стратегии первый игрок съест в результате по крайней мере на две сосиски больше, чем второй.
Комментариев нет:
Отправить комментарий