Задача 111765

Темы:    [ Выигрышные и проигрышные позиции ] [ Индукция (прочее) ]

Сложность: 5+ Классы: 9,10,11

Условие

Авторы: Челноков Г.Р., Богданов И.И.

На столе лежат купюры достоинством 1, 2, .. , 2n тугриков. Двое ходят по очереди. Каждым ходом игрок снимает со стола две купюры, большую отдает сопернику, а меньшую забирает себе. Каждый стремится получить как можно больше денег. Сколько тугриков получит начинающий при правильной игре?

Решение

n²=1+3+..+(2n-1) при нечетном n , n(n+1)=2+4+..+2n при четном n . Обобщим задачу. Пусть в начале игры на столе лежат купюры достоинством M₁>M₂>..>M2n . Покажем индукцией по n , что игрок, делающий последний ход (назовем этого игрока последним}, всегда может получить не менее M₂+M₄+..+M2n тугриков, а игрок, делающий предпоследний ход (назовем этого игрока предпоследним} – не менее M₁+M₃+..+M2n-1 тугриков. Сразу заметим, что сумма этих чисел равна суммарному достоинству всех купюр; поэтому при оптимальной игре они получат ровно такое количество. База при n=1 очевидна. Пусть утверждение верно для n=k-1 , докажем его для n=k . Пусть k нечетно, тогда ходить должен последний игрок. Он может снять купюры M₁ и M₂ ; тогда в оставшейся игре он получит не меньше M₄+M₆+..+M2k , а за этот ход он получит M₂ ; поэтому у него окажется не меньше M₂+(M₄+..+M2k) тугриков, что и требовалось. Покажем, что при любом ходе последнего предпоследний получит не меньше M₁+M₃+..+M2k-1 тугриков. Пусть последний взял купюры M_i>M_j ; перенумеруем оставшиеся на столе купюры по убыванию: L₁>L₂>..>L2k-2 . Тогда по предположению индукции предпоследний сможет дальше играть так, чтобы получить не меньше, чем L₁+L₃+..+L2k-3 . Поэтому нам достаточно показать, что

M_i+(L₁+L₃+..+L2k-3) M₁+M₃+..+M2k-1. (1)
Пусть 1 d k . Покажем, что в левой части неравенства присутствует не меньше d купюр из 2d-1 наибольших купюр M₁,M₂,..,M2d-1 ; это будет означать, что d -е по величине слагаемое слева не меньше M2d-1 , откуда и следует (1) . Действительно, если i> 2d-1 , то M2d-1=L2d-1 и в левой части содержится d купюр M₁,M₃,..,M2d-1 . Пусть i 2d-1 . Тогда среди M₁,M₂,..,M2d-1 содержатся купюры L₁,L₂,.., L2d-3 , из которых d-1 содержится в левой части; кроме того, в ней содержится M_i , что и требовалось. Аналогично, если k четно, то ходит предпоследний. Если он снимет купюры M₂ и M₃ , то он получит не меньше M₃+(M₁+M₅+M₇+..+M2k-1) , что и требовалось. Далее, пусть предпоследний снял купюры M_i>M_j , оставив на столе купюры L₁>L₂>..>L2k-2 ; тогда по предположению индукции последний сможет за дальнейшую игру получить не меньше, чем L₂+L₄+..+L2k-2 . Поэтому достаточно показать, что
M_i+(L₂+L₄+..+L2k-2) M₂+M₄+..+M2k.
Аналогично предыдущему случаю, легко показать, что в левой части неравенства присутствует не меньше d купюр из наибольших 2d купюр M₁,..,M2d , откуда сразу следует требуемое.

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

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	2007
Этап
Вариант	4
Класс
Класс	11
задача
Номер	07.4.11.4