Здравствуйте, VsevolodC, Вы писали:

VC>Здравствуйте, Grammer, Вы писали:

G>>2a. Два игрока играют по очереди называют число, достоинство воображаемой разменной монеты. При этом нужно, чтобы это число нельзя было выплатить при помощи ранее называнных монет. Проигрывает назвавший число 1. Доказать, что игра не может продолжаться бесконечно. (J.H.Conway)

VC>Очевидно, выигрывает первый игрок, назвав 0

есть множество монет М из натуральных чисел [2..inf]
возьмем произвольное n из M.
произведения С*n (где С — натуральная константа) покроет с шагом n все значения от n

             n                  n
    +-----------------+------------------+
    |                 |                  |
....n................2n.................3n..........

надо доказать, что все числа из диапозона [n..2n] прокроют все числа из диапозона [2n..3n] и всех последующих
.

2n + k = n + n + k

где k < n
т.е. вариантов даже не n, а намного меньше
вывод: перебрав варианты из [n..2n] придется перейти к [2..n]

те вариантов не больше чем 2n.

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