Александр и Борис играют в следующую игру. Имеется несколько кучек камней. Ход состоит в том, что игрок разбивает каждую кучку, состоящую более, чем из одного камня, на две меньшие кучки. Ходы делаются поочередно до тех пор, пока во всех кучках не останется по одному камню. Победителем считается игрок, сделавший последний ход. Начинает игру Александр. Первоначально в каждой кучке было от 80 до 120 камней. Кто выигрывает при правильной игре?
Надо следить за максимальным числом камней в одной кучке.
Ответ: Выигрывает Александр Будем следить за максимальным числом камней в одной кучке (обозначим его $M$). Своим первым ходом Александр может получить $M = 63$. Тогда после первого хода Бориса будет $32 \leq M \leq 62$ и своим вторым ходом Александр может получить $M = 31$. Далее Александр может получить $M = 15, 7, 3, 1$ (победа Александра). Таким образом, в этой игре выигрывает Александр, если вначале $M \neq 2^k – 1$ и Борис, если $M = 2^k – 1$
