Цена игры

Лемма. а) На доске выбраны 11 произвольных клеток. Тогда среди них можно найти три клетки такие, что от одной из них можно двумя ходами ладьи обойти вторую и третью клетки.

б) На доске, суммарное числом столбцов и строк в которой не более 11, выбраны 8 клеток. Тогда среди них можно найти три клетки такие, что от одной их них можно двумя ходами ладьи обойти вторую и третью клетки.

Доказательство леммы. Если в столбце/строке выбрана одна клетка, будем называть её одиночной, а если две — будем называть каждую из двух клеток парной. Будем говорить, что клетка занимает строку/столбец, если она стоит в этой строке/столбце. Заметим, что никакие другие клетки не могут быть выбраны в столбце/строке, где стоит одиночная или парная клетки. Тогда каждая пара клеток занимает суммарно 3 строки и столбца, а каждая одиночная — 1 строку и 1 столбец.

a) Обозначим число одиночных клеток за а число парных клеток — за Если лемма не выполняется, то нельзя 11 клетками занять более 8 строк и 8 столбцов, то есть 16 в сумме. Тогда имеем систему

Но — противоречие. Следовательно, предположение неверно и пункт а) леммы доказан.

б) Аналогично пункту а) леммы обозначим число одиночных клеток за а число парных клеток за — Если лемма не выполняется, то нельзя 8 клетками занять более 11 строк и столбцов в сумме. Тогда имеем систему

Но — противоречие. Следовательно, предположение неверно и пункт б) леммы доказан.

_________________________________________________________________________________________________________________________________________________________________________________

Рассмотрим 11 клеток с числами от 54 до 64. Из пункта а) леммы следует, что какие-то три из них второй игрок может обойти, придерживаясь условий задачи. Минимальная сумма трёх из этих чисел равна

значит второй игрок всегда может получить сумму не менее 165 . Предположим, что сумму больше 165 не всегда удастся получить. Тогда никакие три из клеток с числами от 54 до 64 помимо 54, 55, 56 не должны оказаться в одной строке/столбце или образовывать "угол".

При этом числа 54, 55, 56 обязаны оказаться в одной строке/столбце или образовывать "угол иначе найдётся другая тройка чисел с большей суммой. Если эти числа располагаются в одной строке/столбце, или образуют "угол то занимают суммарно 4 строки и столбца. Без ограничения общности, пусть эти числа стоят так, как показано ниже, ведь если поменять какие-то строки/столбцы местами, искомая сумма не изменится.

И в том, и в другом случае оставшиеся 8 клеток с числами от 57 до 64 располагаются в выделенном прямоугольнике, количество строк и столбцов в которых суммарно равно 12. Если эти 8 клеток занимают не все строки или столбцы, то они занимают суммарно не более 11 строк и столбцов. Тогда из пункта б) леммы следует, что какие-то три числа стоят в одной строке/столбце или образуют “угол”, а значит, выбрав эти три клетки, мы увеличим искомую сумму. Если эти 8 клеток, среди которых одиночных и парных клеток, занимают все строки и столбцы, то имеем систему

откуда Следовательно, все клетки в выделенном прямоугольнике парные. Тогда найдётся число не менее 52 (на второй таблице число 53 может дополнять серые клетки до квадрата), которое стоит в одной строке или в одном столбце с какой-то парной клеткой из выделенного прямоугольника. Взяв это число и две парные клетки, получим сумму не менее Значит, примера, гарантирующего сумму 165, но не гарантирующего сумму 166, не существует.

Пример, гарантирующий сумму 166, но не гарантирующий сумму 167:

Здесь сумма 166 достигается, например, на числах 54, 55, 57. Все остальные суммы в пределах правого нижнего прямоугольника не превосходят 166. Максимальная сумма в пределах правого нижнего прямоугольника не будет превосходить 166, так как Оставшиеся числа можно ставить в любые из оставшихся клеток, так как максимальная ещё не рассмотренная сумма будет равна