ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98431
Тема:    [ Симметричная стратегия ]
Сложность: 3+
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

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


Решение 1

  Одна из возможных стратегий первого игрока: первый ход в центр доски; далее каждый раз на ход второго в любую клетку он отвечает ходом в симметричную относительно центра клетку. Это возможно, поскольку симметрию каждый раз нарушает второй.

  В конечной позиции в каждой паре клеток, симметричных относительно центра, стоят крестик и нолик. Поэтому в центральной строке и в центральном столбце крестиков больше, чем ноликов; а каждой не проходящей через центр строке (столбцу) соответствует симметричная строка (столбец), причём в одной из них ноликов больше, а в другой меньше, чем крестиков. Таким образом, при этой стратегии выигрыш первого игрока равен 2.
  Теперь укажем стратегию второго игрока. Если у него есть возможность занять клетку, симметричную (относительно центра) клетке, только что занятой первым, он так и поступает. В противном случае он делает любой ход. При такой стратегии после хода второго множество занятых клеток либо симметрично (до тех пор, пока первый не занял центр), либо отличается от симметричного ровно в одной клетке. При этом в каждой паре занятых симметричных клеток будет находиться один крестик и один нолик. Своим последним ходом первый игрок вынужденно создаст позицию, описанную в предыдущем абзаце, и его выигрыш снова равен 2.


Решение 2

  Разобьём доску на части так, как показано на рисунке. Стратегия первого: первым ходом занять левый нижний угол, а затем ходить в ту же часть доски, куда перед этим пошел второй.

  Стратегия второго: если возможно, занять клетку в той же части доски, куда предыдущим ходом пошел первый; если это невозможно – любой ход.
  Если хотя бы один из игроков придерживается указанной для него стратегии, то в конечной позиции в левом нижнем углу стоит крестик, а в каждой из остальных частей доски крестиков и ноликов поровну (по причинам аналогичным изложенным в первом решении: после каждого хода второго во всех занятых "доминошках" стоит по крестику и нолику, и, еще, возможно, в одной стоит нолик).
  Рассмотрим две верхние строки. В сумме в них стоят 9 крестиков и 9 ноликов (поскольку они разбиты на 9 "доминошек"). Поэтому в одной из них больше крестиков, в другой – ноликов. "Ничейный результат" достигается также в третьей и четвёртой, ..., седьмой и восьмой строках сверху, а нижнюю строку "выигрывает" первый (в ней 5 крестиков и 4 нолика). Аналогична ситуация по столбцам (пары соседних столбцов, считая справа, также состоят из 9 "доминошек").


Ответ

B = 2.

Замечания

5 баллов

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

олимпиада
Название Турнир городов
Турнир
Дата 1998/1999
Номер 20
вариант
Вариант весенний тур, тренировочный вариант, 10-11 класс
Задача
Номер 5

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .