Задача 3. Крестики в столбцах, нолики в строках

Сколько знаков нужно для перевеса

Назовём столбец хорошим, если в нём крестиков больше, чем ноликов, а строку — хорошей, если в ней ноликов больше, чем крестиков. По условию хороших столбцов $n-1$ и хороших строк тоже $n-1$.

В каждом столбце и в каждой строке по $n$ клеток. Сколько крестиков нужно, чтобы их было больше, чем ноликов?

• Если $n=2k$ чётно, то $k$ крестиков и $k$ ноликов — это поровну, а не «больше». Нужно хотя бы $k+1$ крестиков. Например, в столбце из $4$ клеток — хотя бы $3$ крестика.
• Если $n=2k+1$ нечётно, то $k+1$ крестиков против $k$ ноликов уже хватает. Например, в столбце из $5$ клеток — хотя бы $3$ крестика.

В обоих случаях нужно больше половины клеток, то есть хотя бы $k+1$. С ноликами в хорошей строке — то же самое.

Зачем это нужно: условие сказано словами «больше, чем», а сравнивать удобнее числа. Пример для $3\times 3$ находится быстро (в модели его легко собрать), а с $4\times 4$ ничего не выходит. Чтобы понять, что мешает, будем считать знаки.

Крестики и нолики спорят за одни клетки

Требование к столбцам говорит о крестиках, требование к строкам — о ноликах. И тем и другим нужно много клеток, а клеток всего $n^2$. Проверим, хватит ли их.

Мысленно закрасим синим каждый крестик, стоящий в хорошем столбце, и жёлтым — каждый нолик, стоящий в хорошей строке. Одна клетка не может быть и синей, и жёлтой: в ней стоит только один знак. Поэтому

Теперь посчитаем, сколько закрашенных клеток требует условие. В каждом из $n-1$ хороших столбцов не меньше $k+1$ крестиков (шаг 1), и все они синие, значит, синих клеток не меньше $(n-1)(k+1)$. Точно так же жёлтых не меньше $(n-1)(k+1)$. Получаем условие, без которого таблицы не бывает:

Если это неравенство нарушено, расставить знаки нельзя. В модели кнопка «Посчитать клетки» закрашивает клетки именно так — в твоей собственной таблице — и сравнивает нужное число клеток с $n^2$.

Чётное n: клеток не хватает

Пусть $n=2k$. Так как $n>2$, то $k\ge 2$. Посчитаем левую часть $2(n-1)(k+1)$ неравенства из шага 2. Здесь $n-1=2k-1$, а $(2k-1)(k+1)=2k^2+k-1$, поэтому она равна $2(2k^2+k-1)=4k^2+2k-2$.

А клеток в таблице $n^2=4k^2$. Разность $(4k^2+2k-2)-4k^2=2k-2$ положительна, потому что $k\ge 2$. Значит, закрашенных клеток нужно больше, чем всего клеток в таблице, — так не бывает. При чётном $n$ расставить знаки нельзя.

Например, при $n=4$: три хороших столбца по $3$ крестика — это $9$ синих клеток, три хороших строки по $3$ нолика — ещё $9$ жёлтых. Нужно $18$ клеток, а их всего $16$.

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

Нечётное n: запас ровно одна клетка

Пусть $n=2k+1$, где $k\ge 1$. Теперь $n-1=2k$, и закрашенных клеток нужно не меньше

а всего клеток

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

• Клетка нижней строки (кроме угловой) стоит в нехорошей строке, поэтому жёлтой она быть не может. Сделаем её синей: поставим крестики во всю нижнюю строку, кроме угла.
• Клетка правого столбца (кроме угловой) стоит в нехорошем столбце, синей она быть не может. Сделаем её жёлтой: поставим туда нолики.
• Угловая клетка — та самая лишняя. Поставим в неё нолик.

Остаётся квадрат $2k\times 2k$ в левом верхнем углу. Каждому его столбцу нужно $k+1$ крестиков, один уже дала нижняя строка, значит, в самом квадрате нужно $k$ крестиков в каждом столбце. Каждой его строке нужно $k+1$ ноликов, один уже дал правый столбец, значит, в квадрате у неё $k$ ноликов, то есть тоже $k$ крестиков.

Такой квадрат легко заполнить: разрежем его на четыре квадрата $k\times k$, левый верхний и правый нижний заполним крестиками, а два других — ноликами. Тогда в каждой строке и в каждом столбце квадрата $2k\times 2k$ ровно $k$ крестиков. (Подойдёт и любое другое заполнение с $k$ крестиками в каждой строке и каждом столбце, например «лесенка», где каждая следующая строка сдвинута на одну клетку вправо по кругу.)

Проверяем пример и записываем ответ

Проверим таблицу из шага 4.

• Каждый из первых $2k$ столбцов: в квадрате $k$ крестиков и $k$ ноликов, внизу ещё крестик. Всего $k+1$ крестиков и $k$ ноликов — столбец хороший.
• Последний столбец: одни нолики — не хороший. Это и есть исключение.
• Каждая из первых $2k$ строк: в квадрате $k$ крестиков и $k$ ноликов, справа ещё нолик. Всего $k+1$ ноликов и $k$ крестиков — строка хорошая.
• Нижняя строка: $2k$ крестиков и один нолик — не хорошая. Это исключение.

Хороших столбцов ровно $n-1$ и хороших строк ровно $n-1$ — условие выполнено при любом нечётном $n$. Например, при $n=3$ (здесь $k=1$) получается таблица

(крестик обозначен $\times$, нолик $\circ$): в первых двух столбцах по два крестика, в первых двух строках по два нолика.

Вместе с шагом 3 получаем ответ: при всех нечётных $n$ ($n=3, 5, 7, \ldots$).