в ниме позиция (x,y,z) проигрышная тогда и только тогда, когда побитовая сумма количеств камней XOR(x,y,z) — нулевая.
На самом деле — это правило работает и для большего количества кучек, причём дословно так же: побитовая сумма всех количеств должна быть нулевой. И это несложно доказать по индукции — проверив, что если мы объявим такие позиции проигрышными, то:
- из проигрышной все ходы будут вести в выигрышные (достаточно посмотреть на любой из изменившихся битов в той кучке, где был сделан ход),
- из выигрышной всегда есть ход в проигрышную (смотрим на то, откуда пришёл старший бит у ненулевого XOR-а, и делаем ход в эту кучку — зная из XOR-а, докуда именно мы хотим её уменьшить).
И из этого несложно увидеть, что это действительно выигрышные и проигрышные позиции. (Собственно, я в детстве в какой-то из детских математических книг — кажется, у Гарднера? — как раз такое рассуждение и увидел.)
Но мне хочется это увидеть другим способом — потому что на этом пути возникает красивая наука: сложение игр, хакенбуш, сюрреальные числа, и так далее.