Задача 97805

Темы:    [ Целочисленные решетки (прочее) ] [ Выигрышные и проигрышные позиции ]

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

Условие

Автор: Азов Д.Г.

  а) На бесконечном листе клетчатой бумаги двое играют в такую игру: первый окрашивает произвольную клетку в красный цвет; второй окрашивает произвольную неокрашенную клетку в синий цвет; затем первый окрашивает произвольную неокрашенную клетку в красный цвет, а второй еще одну неокрашенную клетку в синий цвет и т. д. Первый стремится к тому, чтобы центры каких-то четырёх красных клеток образовали квадрат со сторонами, параллельными линиям сетки, а второй хочет ему помешать. Может ли выиграть первый игрок?
  б) Каков будет ответ на этот вопрос, если второй игрок закрашивает синим цветом сразу по две клетки?

Решение

  а) Пусть a и a₁ – первые клетки, окрашенные, соответственно, игроками К и С (см. рисунок). Вторым ходом К окрашивает клетку b, стоящую в одном столбце с a, так, что расстояние D между клетками b и a больше, чем между a₁ и a.

  После ответного хода С одна из клеток c и c₁ того же столбца, находящихся сответственно от b и a на том же расстоянии D, (пусть c) останется неокрашенной. Её окрашивает К третьим ходом. Аналогично четвёртым ходом К окрашивает клетку d или d₁ (которые находятся от c и a на расстоянии 2D). Допустим, он окрасил d, тогда рассмотрим столбцы, содержащие клетки e, f, g и h. Один из них, например, содержащий e, свободен от синих клеток, потому что синих клеток всего четыре и одна из них – a₁ – заведомо не стоит в этих столбцах. Окрасив e, игрок К получит выигрышную позицию (клетки a, b, c, e): следующим ходом он "дополнит" до квадрата либо клетки a, b, e, либо клетки b, c, e.

  б) Сначала К окрашивает 3⁸ произвольных клеток некоторой (первой) строки. Затем выбирает вторую строку, лежащую под всеми синими клетками, и окрашивает в ней клетки, лежащие под красными клетками первой строки. Очевидно, он успеет окрасить не менее трети таких клеток, то есть 3⁷. Далее аналогично выбирается третья строка и в ней окрашивается 3⁶ клеток, ..., выбирается седьмая строка и в ней окрашивается 3² клеток. Наконец К выбирает диагональ l, лежащую под всеми синими клетками, и окрашивает в ней три клетки, лежащие под красными клетками седьмой строки (а значит, и всех остальных строк).
  Рассмотрим семь столбцов, в которых расположены клетки пересечения l с семью вышеупомянутыми строками. Так как на последнем этапе С закрасил синим шесть клеток, то в одном из этих столбцов новых синих клеток нет (а все старые лежат над l). К закрашивает клетку a пересечения этого столбца с l (и с некоторой – i-й – строкой). В результате образовалось три квадрата с общей "вершиной" а и еще двумя красными "вершинами" – на l и в i-й строке. Следующим ходом К "замкнёт" один из этих квадратов: С сможет "обезопасить" только два из них.

Замечания

1. Аналогичное решение проходит для любого фиксированного числа точек k, закрашиваемых С при своем ходе, – см. решение задачи М808 из Задачника "Кванта". В частности, для  k = 1  оно потребует 3 строк и 16 (при более аккуратной оценке 9) красных клеток в первой строке. Вышеприведённое решение а) даёт более быстрый выигрыш – уже на шестом ходу игрока К.

2. Задача предлагалась в "трудном" варианте второго тура: в 7-8 кл. – только пункт а) (18 баллов), в 9-10 классах – оба пункта (12 + 30 баллов).

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

олимпиада
Название	Турнир городов
Турнир
Дата	1982/1983
Номер	4
вариант
Вариант	9-10 класс
Задача
Номер	4
олимпиада
Название	Турнир городов
Турнир
Дата	1982/1983
Номер	4
вариант
Вариант	второй тур, 7-8 класс
Задача
Номер	4