Комбинаторика на Изумруде: клетчатые задачи, игры, способы, процессы

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

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

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

Пример:

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

Лемма. а) На доске выбраны 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 вариантов расстановок.

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

Для удобства обозначим изначально записанные на доске числа как .

Поскольку любые два начальных числа взаимно просты, все попарные произведения будут различными, а всего их будет . Именно столько чисел останется после того, как Максим сотрёт все изначальные числа. Все оставшиеся числа имеют вид , где . Произведение двух оставшихся чисел может быть одного из двух видов: или , где .

Всего различных чисел вида столько же, сколько и различных четвёрок чисел , а их всего . Каждое из чисел вида может быть получено тремя способами: при перемножении чисел и и или и . То есть каждое из таких чисел будет написано трижды, поэтому с учётом повторяющихся чисел всего их будет написано 630 .

Чтобы узнать количество чисел вида , необходимо вычесть из количества всех чисел количество чисел вида (с учётом повторяющихся). После второго действия до того, как будут стёрты повторяющиеся числа, их будет всего . Значит, чисел вида всего . Но каждое из чисел вида может быть получено лишь одним способом — при перемножении чисел и , поэтому повторяющихся чисел такого вида не будет. Значит, после того, как Максим сотрёт все повторяющиеся числа, на доске останется чисел.

Замечание. На олимпиаде 2021 года баллы за задачу не снимались, если условие понималось так, что после второго действия Максим стирал все числа вида .

Докажем, что Первый не сможет поставить на доску более 4 полосок. Рассмотрим 8 закрашенных клеток:

Заметим, что любая полоска покрывает ровно одну закрашенную клетку.

Если Первый сумеет сделать четыре хода, то он покроет какие-то 4 закрашенные клетки. Чтобы не дать Первому сделать пятый ход, Второй каждый свой ход также будет покрывать какую-то серую клетку, а если в какой-то момент Второй не сможет положить полоску ни на какую закрашенную клетку, то и Первый не сможет положить полоску ни на какую закрашенную клетку, и игра закончится раньше. Значит, Второй может помешать Первому сделать 5 и более ходов.

_________________________________________________________________________________________________________________________________________________________________________________

Докажем, что Первый сможет выложить четыре полоски . Рассмотрим первые два хода Первого.

Пусть Первый своим первым ходом положил полоску на место прямоугольника 1:

После этого при любом своём ходе Второй не сможет положить полоску так, чтобы она налегала и на прямоугольник 2 , и на прямоугольник 3 . Значит, Первый своим вторым ходом сможет положить полоску либо на прямоугольник 2 , либо на прямоугольник 3. Без ограничения общности, пусть он смог положить полоску на прямоугольник 2. Затем Второй сделает свой второй ход. Поделим доску на области (a), (б), (в):

и рассмотрим все возможные варианты первых двух ходов Второго.

_________________________________________________________________________________________________________________________________________________________________________________

1) Оба хода были совершены в область (в). Тогда своим третьим ходом Первый накрывает полоской область (а). Если после этого Второй своим ходом не задевает область (б), то Первый своим четвёртым ходом накрывает полоской область (б). Если же Второй своим ходом задевает область (б), то внутри области (в) всего две полоски . Каждая полоска пересекает либо два столбца и одну строку, либо две строки и один столбец. Значит, как бы Второй игрок не положил свои полоски в область (в), в ней найдётся хотя бы один столбец или хотя бы одна строка, которые не пересекли полоски. Именно эту строку (столбец) Первый накрывает полоской .

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

3) Оба хода не пересекли область (в). Тогда своим третьим ходом Первый накрывает полоской область третью сверху строку области (в). Как бы ни после этого не сходил Второй, хотя бы одна из строк области (в) останется нетронутой, и Первый своим четвёртым ходом накроет её полоской .

_________________________________________________________________________________________________________________________________________________________________________________

Тем самым мы доказали, что Первый сможет выложить на доску 4 полоски независимо от действий Второго.

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

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

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

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

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

Разобьём клетки доски на группы, как показано на рисунке (разными цифрами обозначены разные группы). Заметим, что если в какой-либо группе клеток все написанные числа равны трём, то кузнечик, прыгая по клеткам этой группы, никогда не сможет попасть в клетки другой группы. Так как кузнечик может обойти все клетки доски, он смог переместиться между клетками разных групп хотя бы раз. Значит троек могло быть не более

Приведём пример заполнения клеток таблицы и порядка обхода этих клеток кузнечиком (см. рисунок В клетках стоят единицы, во всех остальных — тройки. Порядок обхода по возрастанию индексов.

Пусть в турнире участвовало команд, причём команда-победитель выиграла матчей. Тогда каждая из оставшихся команд выиграла по матча. Всего между командами состояпось матчей, в которых суммарно было победителей. С другой стороны, суммарное число побед всех команд равно . Значит,

является целым числом, следовательно,

целое число, а значит — целое, что возможно лишь при .

При матчей не было.

При число , что не является целым.

При число .

Пример: занумеруем команды числами . Команда 1 вынграла у всех, команда 2 выиграла у команды 3, команда 3 выиграла у команды 4, команда 4 выиграла у команды 2.