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

Рассмотрим одно из них. Чтобы все клетки были побиты, нужно как минимум оборотня, так как каждый из них бьет не более клеток, и, следовательно, и меньше оборотней бьют максимум клеток. Пример расстановки оборотней: выделим непересекающихся Т-образных фигур, в каждой из которых отметим по одному оборотню.

И так как оборотень, стоящий на клетке из одного множества, не может дойти до клеток из трех других, получаем, что всего нужно как минимум оборотней.

Лемма. а) На доске выбраны 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, так как Оставшиеся числа можно ставить в любые из оставшихся клеток, так как максимальная ещё не рассмотренная сумма будет равна

Пример:

Пример подходит, потому что центрами симметрии прямоугольников являются точки пересечения их диагоналей, а данный многоугольник не имеет центра симметрии, так как если он лежит вне синего отрезка, проходящего через середину одной из сторон, левые вершины многоугольника перейдут не в точки многоугольника, а если он лежит вне красного отрезка, проходящего через середину другой стороны, то верхние вершины многоугольника перейдут не в точки многоугольника.

Пронумеруем клетки таблицы так, как показано на рисунке. Ясно, что в левой верхней клетке стоит число 1, а в правой нижней — число 9.

По условию поэтому Рассмотрим случаи.

1) Если то числа и — это 2 и 3. Способов их расстановки всего 2. Теперь вычислим количество вариантов выбора чисел и На их место можно поставить любую из оставшихся пар чисел, причём поэтому расстановка каждой пары определяется однозначно. Всего таких пар Оставшиеся два числа расставляются однозначно. Всего получилось вариантов расстановки.

2) Если то числа и — это 7 и 8, и случай аналогичен предыдущему. Получаем ещё 12 вариантов расстановки.

3) Если то посмотрим, какие числа могут стоять в клетках с номерами и На их место нельзя ставить числа 2 и 8, так как эти числа обязаны быть соседями 1 и 9 соответственно. Если то и Любое из оставшихся чисел можно поставить в клетку тремя способами, оставшиеся числа ставятся однозначно. Рассмотренный вариант аналогичен случаям и — в каждом получаем по 3 варианта расстановки, но были дважды посчитаны случаи, когда числа и — это 3 и 7. Всего таких случаев два:

В итоге получаем вариантов.

Если ни одно из чисел в клетках и не равно 3 или 7, то в клетках и могут стоять лишь числа 4 и 6 в любом порядке. Тогда в клетках и стоят числа 2 и 3 в любом порядке, а в клетках и — числа 7 и 8 в любом порядке. Всего 8 вариантов расстановок.

Все случаи разобраны, искомое число вариантов равно

Заметим, что в прямоугольниках и находится не больше одной принцессы. Иначе в прямоугольнике левая принцесса била бы правую, а в прямоугольнике нижняя принцесса — верхнюю. Значит, принцессы не могут быть в соседних по стороне клетках.

Покажем, что в прямоугольнике не более двух принцесс. Предположим, что в таком прямоугольнике можно разместить хотя бы фигуры принцесс. Так как принцессы не являются соседями по стороне, то возможны два варианта их размещения (розовые квадратики — фигуры прицесс)

В обоих случаях найдется принцесса, которая будет побита.

Тогда если разбить доску на непересекающиеся области размера получим, что принцесс не более

48 принцесс разместить уже возможно: