Олимпиадная задача по математике: стратегия игроков с купюрами — теория алгоритмов и индукция

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 , откуда сразу следует требуемое.

Ответ задачи отсутствует