Играют двое. Игровое поле - полоска бумаги, разделенная на 8 клеток. В клетках 4, 6 и 8 помещены шашки. Играющие поочередно передвигают произвольно выбранную шашку из данных трех на любую клетку в направлении, указанном стрелкой. Шашка может быть передвинута и через другую шашку и поставлена на клетку, занятую другой шашкой. Выигрывает тот, кто последним поставит шашку на клетку 1. Как должен играть начинающий игрок, чтобы обеспечить себе победу?
update
Первым нашел стратегию Илья.Ответ
Игра со спичками.
Если я не ошибаюсь, то начинающий игрок первым ходом должен сдвинуть любую фишку на одну клетку.
ОтветитьУдалитьHint: неплохо замаскированная очень известная игра. )
У меня нет ответа на эту головоломку, поэтому желательно подробное решение.
УдалитьВ ходе игры нужно сдвинуть все фишки на клетку 1. При этом в общей сложности первую нужно сдвинуть на 3, вторую на 5, а третью - на 7 клеток.
УдалитьМожно рассматривать фишки как числа (изначально - 3, 5 и 7), которые каждый ход можно уменьшать на произвольную целую величину, но не дальше чем до нуля и только одну за ход.
Или можно интерпретировать так: есть три кучки камней (по 3, 5 и 7 соответственно), и за один ход можно забрать произвольное число камней, но только из одной кучки. Выигрывает тот, кто заберет последний камень. Или так: проигрывает тот, кто не сможет сделать очередной ход.
Эта известная игра называется "Ним". Выигрышная стратегия известна; правда, честно говоря, сомневаюсь, что сам бы до неё когда-нибудь додумался, если бы не прочитал.
Идея стратегии следующая. Представим все исходные числа (3, 5 и 7) в двоичном виде. Произведем в каждом разряде проверку на четность, или говоря по-другому, произведем побитовое сложение:
011
101
111
---
001
Набор чисел назовём "нечетным", если в результате получается 1 хотя бы в одном разряде, в противном случае будем называть его "четным". Заметим, что из четного любым ходом можно сделать только нечётный, а из нечётного всегда подходящим ходом можно сделать чётный. Обратив внимание на тот факт, что конечный набор (0, 0, 0) - чётный, получаем следующую стратегию для первого игрока: всегда сводить своим ходом набор чисел к "чётному". Противник сможет своим ходом добиться только нечётного набора, а следовательно, никогда не сможет победить.
Ну то, что игра конечная, очевидно. )
Да, непростая задача. Спасибо за подробный ответ.
Удалитьчто-то я запутался, как в этой стратегии учитывается то, что можно перепрыгнуть через шашку или поставить шашку в ту же клетку с другой?
Удалитьтак, например, если первым ходом игрок двигает шашку с 8 на 7, то у второго игрока появляются варианты: перепрыгнуть шашкой с 7 на 5, или поставить с 7 на 6. у получившихся позиций разная же четность будет?
Тот факт, что можно перепрыгнуть через шашку или поставить с другой на ту же клетку, можно интерпретировать следующим образом: шашки друг другу не мешают, не конфликтуют. Можно считать, что каждая шашка двигается по своей индивидуальной полосе.
УдалитьПусть первый двинет шашку с 8 на 7, т.е. остаются числа 3, 5, 6.
011
101
110
----
000
Позиция четная.
Если второй сдвинет эту фишку на 5, то получатся числа 4,5,3:
100
101
011
---
010
Нечетная позиция.
Если же сдвинет на 6, то:
101
101
010
---
010
Опять позиция нечетная.
- Если я не ошибаюсь, то начинающий игрок первым ходом должен сдвинуть любую фишку на одну клетку. -
УдалитьМеня лично хватило лишь, чтобы определить, что все остальные ходы (4 -> 1, 4 -> 2, 6 -> 1, 6 -> 2, 6 -> 3, 8 -> 1, 8 -> 2, 8 -> 3, 8 -> 5 ) ведут к проигрышу первого :-) Точнее, дают возможность второму перехватить инициативу. Да, жесткая задача. Без восьми пядей во лбу ее не решить, еще же доказывать надо, что из четной позиции можно прийти только к нечетной. А из нечетной - как к четной, так и нечетной. :-)
То, что из четной можно получить только нечетную, доказывается просто. Действительно, при каждом ходу мы одно из чисел уменьшаем, а следовательно, по крайней мере в одном из его двоичных разрядов произойдет изменение (0 на 1 или 1 на 0), значит в этом разряде чётность также изменится (были в сумме везде нули, а станет по крайней мере в одном из разрядов не ноль).
ОтветитьУдалитьДоказательство того факта, что из нечётной всегда можно прийти к чётной - немного сложнее. :) Но я верю, вы справитесь. :)
Ну и в качестве комментария замечу, что это решение подходит для любого количества фишек и любой начальной расстановки на ленте любой длины. :)
--Доказательство того факта, что из нечётной всегда можно прийти к чётной - немного сложнее. :) Но я верю, вы справитесь. :)--
УдалитьВера творит чудеса! :-)
Доказательство сего может быть примерно таким:
Для наглядности возьмем любой нечетный набор, например:
1101111
0111011
1010101
0110011
0010111
-------
0100101 - сумма
Ищем в сумме единицу в наивысшем разряде (самую левую проще говоря). У нас она на втором месте. Выбираем любое из слагаемых с единицей на этом же месте - очевидно, что как минимум одно такое слагаемое будет существовать. Возьмем, например, 0110011. В этом числе меняем 1 на 0 и 0 на 1 в разрядах, соответствующим единицам суммы 0100101. Получится 0010110. В итоге гарантированно получаем меньшее число (так как мы поменяли единицу старшего разряда на 0), и итоговый набор будет четным.
Такие манипуляции можно провести для любого нечетного набора - поэтому из любого нечетного набора можно как минимум одним способом получить четный. Та-да!!!