Задача 8. Уголки в таблице 6×6

Уголки живут в квадратах 2×2

Каждый уголок получен из какого-то квадрата $2\times 2$ таблицы. Таких квадратов $5\cdot 5=25$: левая верхняя клетка квадрата стоит в одной из первых пяти строк и одном из первых пяти столбцов. В каждом квадрате $4$ уголка (убираем одну из четырёх клеток) — всего $100$ уголков.

Главное наблюдение: любые три клетки квадрата $2\times 2$ образуют уголок — достаточно убрать четвёртую клетку. Поэтому самый лёгкий уголок квадрата получится, если убрать его наибольшее число (рисунок ниже). Значит, $m$ — это наименьшая по всем $25$ квадратам сумма трёх меньших чисел квадрата.

Зачем это нужно: вместо $100$ уголков думаем о $25$ квадратах, а условие «все уголки не легче $47$» читается просто: в каждом квадрате $2\times 2$ любые три числа дают в сумме не меньше $47$.

Пример: m = 46

Чтобы уголки были тяжёлыми, маленькие числа нельзя ставить кучей: три маленьких числа в одном квадрате дадут лёгкий уголок. Хорошо, если в каждом квадрате $2\times 2$ ровно два числа из первой половины ($1$–$18$) и два из второй ($19$–$36$). Это делает шахматная раскраска: в любом квадрате $2\times 2$ две клетки тёмные (по одной диагонали) и две светлые (по другой).

Поставим $1$–$18$ на тёмные клетки, а $19$–$36$ — на светлые. Тогда в каждом квадрате наибольшее число стоит на светлой клетке, и самый лёгкий уголок — это две тёмные клетки плюс меньшая из двух светлых. Остаётся подобрать числа так, чтобы рядом с самыми маленькими тёмными стояли самые большие светлые. Одна такая таблица — на рисунке ниже.

Проверим все $25$ квадратов, а не только девять, на которые таблица делится ровно: для каждого квадрата сложим две тёмные клетки и меньшую светлую. Например, в левом верхнем квадрате числа $1$, $32$, $31$, $14$: самый лёгкий уголок $1+14+31=46$. Все $25$ сумм выписаны под таблицей: самая маленькая из них $46$, и она встречается. Значит, у этой расстановки $m=46$, и $M\ge 46$.

Если бы все уголки были не легче 47

Докажем, что $m\ge 47$ не бывает ни при какой расстановке. Пусть, наоборот, нашлась расстановка, в которой каждый уголок не легче $47$. Разрежем таблицу на девять квадратов $2\times 2$ (рисунок ниже). По шагу 1 в каждом из них любые три числа дают в сумме не меньше $47$.

Назовём малыми числа от $1$ до $16$, остальные ($17$–$36$) — большими. Почему граница именно $16$: три малых числа дают не больше $14+15+16=45<47$, а вот $15+16+17=48$ уже не меньше $47$.

Значит, ни в одном из девяти квадратов нет трёх малых чисел: они образовали бы уголок легче $47$. Малых чисел $16$, а в девяти квадратах им есть место не больше чем для $2\cdot 9=18$. Двух мест не хватает, поэтому возможны только два случая:

• восемь квадратов с двумя малыми числами и один квадрат без малых;

• семь квадратов с двумя малыми числами и два квадрата с одним малым.

Что требует от квадрата каждое малое число

Возьмём квадрат с двумя малыми числами $a$, $b$ и большими $c<d$; сумму малых обозначим $s=a+b$. Уголок $a$, $b$, $c$ не легче $47$, поэтому $c\ge 47-s$, а $d\ge c+1\ge 48-s$. Сложив, получаем

Чем меньше малые числа, тем больше должны быть большие соседи. Тогда сумма квадрата

зависит от $s$. Чтобы от этого избавиться, прибавим малые числа ещё раз. Назовём весом квадрата сумму его четырёх чисел плюс ещё раз сумму его малых чисел. Тогда вес такого квадрата

Квадрат с одним малым числом $x$ и большими $p<q<r$: уголок $x$, $p$, $q$ не легче $47$, то есть $t=p+q\ge 47-x$. Кроме того, $q\ge p+1$ и $r\ge q+1$, поэтому $2r\ge 2q+2\ge p+q+3=t+3$. Здесь удобно считать удвоенный вес $4x+2t+2r$: в нём стоит $2r$, а его мы только что сравнили с $t$:

Удвоенный вес — чётное число, значит, он не меньше $146$, а сам вес не меньше $73$.

Квадрат без малых: четыре разных числа от $17$ и больше, вес не меньше $17+18+19+20=74$.

Итак, вес квадрата не меньше $95$, $73$ или $74$ — смотря по тому, сколько в нём малых чисел: два, одно или ни одного (рисунок ниже).

Складываем веса девяти квадратов

Сложим веса всех девяти квадратов. Каждое число таблицы попадёт в сумму один раз, а каждое малое — ещё один раз:

С другой стороны, по шагам 3 и 4 сумма весов не меньше:

• в первом случае $8\cdot 95+74=834$;

• во втором случае $7\cdot 95+2\cdot 73=811$.

Оба числа больше $802$ — противоречие. Значит, при любой расстановке найдётся уголок с суммой не больше $46$, то есть всегда $m\le 46$. Вместе с примером из шага 2 получаем $M=46$.