Внешние условия, которые заставляют игру быть ациклической, могут быть весьма сложными, и к делу не относятся. Как написал iensen, может быть ограничена сумма увеличивающих ходов.

Стандартный пример из "реальных" задач - это "лестничный ним": т.е. есть n ступенек, в каждой a[i] камней (i=0..n-1), и за один ход мы можем переложить любое количество камней из какой-то k-ой кучки в k-1-ю. Тогда, если рассмотреть только ступеньки с нечётными номерами, т.е. числа a[1], a[3], a[5], и т.д., то получится ним с увеличениями: мы можем либо уменьшить какое-то число (что соответствует перекладыванию из нечётной в чётную), либо увеличить (а это - из чётную в нечётную). Понятно, что увеличения здесь вполне ограничены: хотя бы даже из того факта, что камни всегда передвигаются в сторону к первой ступеньке, т.е. игра не может длиться бесконечно.

Здесь надо понимать этот фокус: у нас была сложная игра с состоянием-массивом чисел, а мы переходим от ней к ниму с увеличениями, и говорим - да, мы можем производить увеличения, и эти увеличения имеют сложную природу, не описываемую в терминах нима, однако лемма показывает, что эти увеличения нам не нужны вовсе. Значит, мы можем забыть про эти увеличения, и сказать, что теперь у нас - самый обычный ним.

Если проще соображать в терминах лестничного нима - то эту лемму можно понять так. Если мы рассмотрим только числа a[1], a[3], a[5], ..., то да, по условию мы можем увеличить какое-то из чисел - но зачем, если у противника на этот случай есть симметричная стратегия? Мы увеличили какое-то число, а противник уменьшит его обратно, при этом мы придём к тому же набору чисел a[1], a[3], a[5], ..., но уже окажемся ближе к концовке игры. Значит, увеличение - это глупый ход, он нам никак не улучшит ситуацию, не позволит достигнуть даже ничьи.


P.S. а про ксоры и мексы хорошо написал kuniavski.

P.P.S. конвей, конечно, крутая книжка, но сказать откровенно - очень тяжело написанная, так что я не уверен, что с её помощью разобраться будет проще.