|
|
 |
Условие
Прямоугольник 1×3 будем называть триминошкой. Петя и Вася независимо друг от друга разбивают доску 20×21 на триминошки. Затем они сравнивают полученные разбиения, и Петя платит Васе столько рублей, сколько триминошек в этих двух разбиениях совпали (оказались на одинаковых позициях). Какую наибольшую сумму выигрыша может гарантировать себе Вася независимо от действий Пети?
Решение
Пример. Вася разбивает доску на горизонтальные триминошки. Пусть количество Петиных горизонтальных триминошек, центр которых лежит в $i$-м столбце, равно $a_i$. Поскольку в столбце 20 клеток, а вертикальная триминошка покрывает три клетки, то $a_{i–1} + a_i + a_{i+1}$ ≡ 2 (mod 3) . Отсюда $a_{i+2}$ ≡ 2 – $a_i - a_{i+1}$ ≡ $a_{i-1}$ (mod 3). Так как по определению $a_0 = a_1$ = 0, то $a_2$ ≡ 2 (mod 3), поэтому в каждом из столбцов 2, 5, 8, 11, 14, 17, 20 лежат центры хотя бы двух горизонтальных триминошек Пети. Они совпадут с Васиными, что даст ему не менее 14 рублей.
Оценка. Можно считать, что Петя знает Васино разбиение. Верхние две строки Петя разбивает на горизонтальные триминошки, они дадут Васе не более 14 совпадений. Оставшуюся доску Петя делит на квадраты 3×3. Если в какой-то квадрат полностью входит Васина горизонтальная триминошка, то Петя разбивает его на вертикальные триминошки, иначе – на горизонтальные, и в этом квадрате не будет совпадений.
Ответ
14 рублей.
Замечания
6 баллов
