Играют двое. Игровое поле - полоска бумаги, разделенная на 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), и итоговый набор будет четным.
Такие манипуляции можно провести для любого нечетного набора - поэтому из любого нечетного набора можно как минимум одним способом получить четный. Та-да!!!