Игра Ним с нечетным числом камней
Зашел на MO задать вопрос, а там как раз ответили на предыдущий, не прошло и полугода.
Игра Ним хорошо известна, но недолго и напомнить:
есть несколько куч с камнями, играют двое, делая ходы поочередно. За один ход можно взять любое положительное число камней из любой кучи. Проигрывает не имеющий хода.
Известно и полное описание выигрышных позиций: второй выигрывает если и только если при каждом i сумма i-ых с конца двоичных цифр количеств камней в кучах четна.
Отсюда, заметим, следует сразу, что первый выигрывает при общем нечетном числе камней. Естественный вопрос --- нельзя ли это как-то доказать, не пользуясь полным описанием выигрышных позиций?
И вот, как объяснил мне Дуглас Царе (как по-русски?) (специалист по разным интересным играм), очень возможно. Можете подумать самостоятельно, рассуждение Царе под катом.
Докажем индукцией по нечетному числу n, что первый выигрывает, если общее число камней равняется n. Пусть для меньших нечетных чисел это известно. Рассмотрим возможный первый нечетный ход (взятие нечетного числа камней). Предположим, что он проигрывает. Тогда выигрывающим за второго ответа является четный ход (по индукционному предположению), дальше снова надо делать четный ход и так далее, кто сделал нечетный ход тот проиграл. Фактически ребята начинают играть в игру Ним, в которой количества камней вдвое меньше (с округлением вниз) реальных. Теперь первый может применить неявную стратегию. Если выигрывающим ответом на взятие одного камня из нечетной кучи является взятие 2k камней из (изначально) четной кучи, мы можем первым ходом взять оттуда 2k-1 камней. Если же выигрывающий ответ состоит во взятии 2k камней из изначально нечетной кучи (в том числе той, в которую мы пошли первым ходом), мы можем первым ходом взять оттуда 2k+1 камней. А дальше повторять стратегию второго, которая у него якобы есть.
Другой естественный вопрос, который задал и ответил на него сам же Барри Кипра --- как по-простому доказать, что первый выигрывает, если в одной из куч количество камней строго больше, чем во всех остальных вместе взятых. Этот вопрос в некотором смысле двойственен моему: в одной ситуации нечетна сумма младших двоичных цифр, в другой --- старших. Да, конечно, сумма старших цифр может быть нечетна и по многим другим причинам, кроме как быть равной 1, так что аналогия не полная.
Но так или иначе, в этом случае тоже есть изящная неявная стратегия: ответом на каждый ход в большую кучу должен быть ход в одну из малых (иначе передача ходя работает сразу), по принципу Дирихле каким-то двум ходам в большую кучу соответствует один и тот же ответ --- но это значит, что одна проигрышная позиция получается в один ход из другой, что невозможно.
Игра Ним хорошо известна, но недолго и напомнить:
есть несколько куч с камнями, играют двое, делая ходы поочередно. За один ход можно взять любое положительное число камней из любой кучи. Проигрывает не имеющий хода.
Известно и полное описание выигрышных позиций: второй выигрывает если и только если при каждом i сумма i-ых с конца двоичных цифр количеств камней в кучах четна.
Отсюда, заметим, следует сразу, что первый выигрывает при общем нечетном числе камней. Естественный вопрос --- нельзя ли это как-то доказать, не пользуясь полным описанием выигрышных позиций?
И вот, как объяснил мне Дуглас Царе (как по-русски?) (специалист по разным интересным играм), очень возможно. Можете подумать самостоятельно, рассуждение Царе под катом.
Докажем индукцией по нечетному числу n, что первый выигрывает, если общее число камней равняется n. Пусть для меньших нечетных чисел это известно. Рассмотрим возможный первый нечетный ход (взятие нечетного числа камней). Предположим, что он проигрывает. Тогда выигрывающим за второго ответа является четный ход (по индукционному предположению), дальше снова надо делать четный ход и так далее, кто сделал нечетный ход тот проиграл. Фактически ребята начинают играть в игру Ним, в которой количества камней вдвое меньше (с округлением вниз) реальных. Теперь первый может применить неявную стратегию. Если выигрывающим ответом на взятие одного камня из нечетной кучи является взятие 2k камней из (изначально) четной кучи, мы можем первым ходом взять оттуда 2k-1 камней. Если же выигрывающий ответ состоит во взятии 2k камней из изначально нечетной кучи (в том числе той, в которую мы пошли первым ходом), мы можем первым ходом взять оттуда 2k+1 камней. А дальше повторять стратегию второго, которая у него якобы есть.
Другой естественный вопрос, который задал и ответил на него сам же Барри Кипра --- как по-простому доказать, что первый выигрывает, если в одной из куч количество камней строго больше, чем во всех остальных вместе взятых. Этот вопрос в некотором смысле двойственен моему: в одной ситуации нечетна сумма младших двоичных цифр, в другой --- старших. Да, конечно, сумма старших цифр может быть нечетна и по многим другим причинам, кроме как быть равной 1, так что аналогия не полная.
Но так или иначе, в этом случае тоже есть изящная неявная стратегия: ответом на каждый ход в большую кучу должен быть ход в одну из малых (иначе передача ходя работает сразу), по принципу Дирихле каким-то двум ходам в большую кучу соответствует один и тот же ответ --- но это значит, что одна проигрышная позиция получается в один ход из другой, что невозможно.