Игра происходит на квадрате клетчатой бумаги 9×9. Играют двое, ходят по очереди. Начинающий игру ставит в свободные клетки крестики, его партнер – нолики. Когда все клетки заполнены, подсчитывается количество К строк и столбцов, в которых крестиков больше, чем ноликов,и количество Н строк и столбцов, в которых ноликов больше, чем крестиков. Разность  В = К – Н  считается выигрышем игрока, который начинает. Найдите такое значение B, что
  1) первый игрок может обеспечить себе выигрыш не меньше B, как бы ни играл второй игрок;
  2) второй игрок всегда может добиться того, что первый получит выигрыш не больше B, как бы тот ни играл.

   Решение

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

Сложность: 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 баллов

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