Задача 65395

Темы:    [ Теория игр (прочее) ] [ Оценка + пример ]

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

Условие

Автор: Толпыго А.К.

Играют двое. У первого 1000 чётных карточек (2, 4, ..., 2000), у второго – 1001 нечётная (1, 3, ... , 2001). Ходят по очереди, начинает первый. Ход состоит в следующем: игрок, чья очередь ходить, выкладывает одну из своих карточек, а другой, посмотрев на неё, выкладывает одну из своих карточек; тот, у кого число на карточке больше, записывает себе одно очко, а обе выложенные карточки выбрасываются. Всего получается 1000 ходов (одна карточка второго не используется). Какое наибольшее число очков может гарантировать себе каждый из игроков (как бы ни играл его соперник)?

Решение

  Назовём критическим ход, в котором использована карточка 2001. Докажем, что первый может получать очки на всех ходах второго, кроме, быть может, критического.
  В каждый момент будем обозначать карточки первого  a₁ < a₂ < ... < a_n,  а карточки второго –  b₁ < b₂ < ... < b_n+1  (до критического хода  b_n+1 = 2001).  При сравнении карточки после хода будем обозначать соответственно A_k и B_k. В начальный момент выполнены неравенства  a_k > b_k.  Докажем, что до критического хода первый может сохранить эту ситуацию.
  Именно, при своём ходе первый ходит с a₁, и у него остаются карточки  A_k = a_k+1  (k = 1, 2, ..., n – 1);  при любом ответе для оставшихся у второго карточек выполнено  B_k ≤ b_k+1 < A_k.  Если же ход второго и он кладёт b_i, то первый кладёт a_i (и получает очко). При этом неравенства для оставшихся карточек, очевидно, выполняются.
  После критического хода (независимо от того, чья очередь, первый отдаёт наименьшую карточку), ситуация для первого “улучшается”: теперь выполнены неравенства  a_k > b_k+1.  Аналогично проверяем, что первый может сохранить эту ситуацию до конца игры: при своём ходе он отдаёт a₁, при ходе второго кладёт a_k на b_k+1 (и a₁ на b₁).
  Докажем теперь, что второй может получить очки на всех ходах первого плюс на своём последнем ходе. В тех же обозначениях в начале выполнены неравенства  b_k+1 > a_k.  Действуя аналогично изложенной выше стратегии (при своём ходе – класть b₁, при ходе первого класть b_k+1 на a_k), второй сохраняет эту ситуацию и набирает очки на всех ходах первого. Перед последним ходом у второго остаётся наибольшая на этот момент карточка b₂. Положив её, он получает дополнительное очко.

Ответ

Первый – 499 очков, второй – 501.

Замечания

8-9 кл. – 8 баллов, 10-11 кл. – 9 баллов

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

олимпиада
Название	Турнир городов
Турнир
Номер	25
Дата	2003/2004
вариант
Вариант	осенний тур, основной вариант, 10-11 класс
задача
Номер	5
олимпиада
Название	Турнир городов
Турнир
Номер	25
Дата	2003/2004
вариант
Вариант	осенний тур, основной вариант, 8-9 класс
задача
Номер	7