Есть три кучи, содержащие 52,51 и 50 камней. За ход разрешается взять любое количество камней, но только из одной кучки. Проигрывает тот, кто не сможет сделать ход. Кто выиграет при правильной игре?
Подсказка, данная с условием:
Описать выигрышные и проигрышные позиции в этой игре проще, если количество камней в кучках записывать в двоичной системе счисления.

задан 8 Янв '14 23:41

10|600 символов нужно символов осталось
2

Это хорошо известная игра "ним". Принцип её игры много где описан (например, у Мартина Гарднера), и саму стратегию сформулировать довольно просто, хотя полное доказательство того, что она всегда ведёт к выигрышу, довольно нетривиальное. Количество кучек, как и число камней, может быть каким угодно.

Критерием того, что позиция проиграна для начинающего, является следующее условие: если записать каждое из чисел в двоичной системе, то поразрядная сумма (по принципу 1+1=0) должна быть равна нулю.

Более наглядно можно представлять себе это дело так: каждое число разложим в сумму различных степеней двойки, что эквивалентно записи в двоичной системе. В данном случае будет так:

52=32+16+4

51=32+16+2+1

50=32+16+2

Нужно, чтобы после хода получалось так, что каждая степень двойки встречается чётное число раз. При этом можно проанализировать все выигрывающие ходы (если они есть). Бывает так, что выигрывающий ход всего один. Например, для игры с количеством камней 3, 4, 5 единственный правильный ход -- это взять два камня из первой кучки, оставляя противнику позицию 1, 4, 5. Все остальные ходы проигрывают.

В данном случае имеется три выигрывающих хода (нетрудно заметить, что при взятии камней из заданной кучки такой ход имеется либо один, либо ни одного). Если мы берём камни из первой кучки, то для поддержания "паритета чётности" в ней должен остаться 1 камень. Если мы берём камни из второй кучки, то там должно остаться 4+2=6 камней. Наконец, если берутся камни из третьей кучки, то их должно остаться 4+2+1=7.

ссылка

отвечен 9 Янв '14 0:06

10|600 символов нужно символов осталось
0

Если актуально, можете почитать здесь

ссылка

отвечен 30 Май '15 15:52

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×54
×34

задан
8 Янв '14 23:41

показан
2326 раз

обновлен
30 Май '15 15:52

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru