Изучив чистую игру Ним из теории Шпрага-Гранди, перешел к игре Ним в поддавки. На сайте
ссылка удалена описано доказательство, опирающееся на саму игру Ним, но меня интересует изучение и доказательство для этой игры с "нуля", т.е. так же, как это сделано для обычного Нима. Сейчас имею такие рассуждения:
- Рано или поздно, но мы точно пройдём через такое состояние игры, при котором все кучи будут иметь значения либо 0, либо 1. Доказательство: Если мы минуем такое состояние, то выиграет не тот человек, который походил из предыдущего. В силу того, что игроки играют оптимально, следует, что этого хода никогда не будет. Ч.т.д.
- Рассмотрим состояние игры, когда у нас k куч величины 1, а остальные 0 (либо их больше нет). Тогда несложно понять, что если k - четное (т.е.
), то такое состояние выигрышное. Если же нечетное (т.е. 
), то состояние проигрышное.
Как теперь построить из этих рассуждений математическую индукцию? Возможно ли это вообще? Т.е. теперь я хочу сказать что-либо про состояния, где есть хотя бы 1 куча
. Из доказательства обычного Нима знаем, что из состояния
есть ход только в состояния, где
, но вот с состояниями
дела обстоят по-другому...
