Задача 105218

Темы:    [ Теория игр (прочее) ] [ Арифметическая прогрессия ] [ Суммы числовых последовательностей и ряды разностей ]

Сложность: 4- Классы: 8,9,10

Условие

Алиса и Базилио играют в следующую игру; из мешка, первоначально содержащего 1331 монету, они по очереди берут монеты, причем первый ход делает Алиса и берет 1 монету, а далее при каждом следующем ходе игрок берет (по своему усмотрению) либо столько же монет, сколько взял другой игрок последним ходом, либо на одну больше. Проигрывает тот, кто не может сделать очередной ход по правилам. Кто из игроков может обеспечить себе выигрыш независимо от ходов другого?

Решение

Пусть Алиса независимо от действий Базилио берет первым ходом 1 монету, вторым --2, третьим --3 и т.д., увеличивая каждый раз количество взятых монет на 1. Это не противоречит правилам, так как при такой игре Алисы Базилио сможет первым ходом взять 1 или 2 монеты, вторым --2 или 3 и т.д. Тогда после k-го хода Алисы игроки возьмут монет не менее

(1 + 2 + ... + k) + (1 + 2 + ... + (k - 1)) = k²

и не более

(1 + 2 + ... + k) + (2 + 3 + ... + k) = k(k + 1) - 1.

Так как 36 ^. 37 - 1 = 1331, то монет в любом случае хватит на 36-й ход Алисы. А так как 36² = 1296 и  1331 - 1296 = 35, то монет в любом случае не хватит на 36-й ход Базилио. Таким образом, Алиса выиграет.

Ответ

Выигрывает Алиса.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	62
Год	2006
вариант
Класс	11
задача
Номер	4