Условие

Дана таблица $n\times n$, столбцы которой пронумерованы числами от $1$ до $n$. В клетки таблицы расставляются числа $1,2,\cdots, n$ так, что в каждой строке и в каждом столбце все числа различны. Назовем клетку хорошей, если читсло в ней больше номера столбца, в котором она находится. При каких $n$ существует расстановка, в которй во всех строках одинаковое количество хороших клеток?

Решение

Найдем общее количество хороших клеток. В первом столбце их $n-1$ (все, кроме клетки с числом 1), во вторм их $n-2$ (все, кроме клетки с числом 1 и 2) и т.д., в последнем столбце таких клкеток нет. Значит, всего их $(n-1)+(n-2)+\cdots +1=\frac{n(n-1)}{2}$

Поэтому в каждой строке их должно быть по $\frac{n-1}{2}$, следовательно, $n$ должно быт ьнечетным.

Приведем пример расстановки при нечетном $n$. Пусть в первой строке записаны числа в порядке $1,n,n-1,n-2,\cdots,2$

а каждая следующая строка является циклическим сдвигом предыдущей строки на 1 клетку (см.рис.). Очевидно, в любой строке и в любом столбце каждое из чисел $1,2,\cdots,n$ встречается по одному разу. Рассмотрим $m$-ю строку ($m\in \left \{ 1,2,\cdots,n \right \}$). В ее первых $m$ клетках стоят числа $1,2,\cdots,m$ в обратном порядке, поэтому среди этих клеток ровно $\left [\frac{m}{2} \right]$ хороших. В ее последних $n-m$ клетках(т.е. в столбцах с номерами $m+1,m+2,\cdots,n$) стоят числа $m+1,m+2,\cdots,n$ в обратном порядке, поэтому среди этих клеток ровно $\left [\frac{n-m}{2} \right]$ хороших. Так как числа $m$ и $n-m$ разной четности, то в $m$-й строке ровно $\left [\frac{m}{2} \right]+\left [\frac{n-m}{2} \right]=\frac{m}{2}+\frac{n-m}{2}-\frac{1}{2}=\frac{n-1}{2}$ хороших клеток.

К.Чувилин

Ответ: 25.

Задача М2098

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

Ответ: сможет

Решение

Докажем индукцией по $n$, что первый может играть так, что нарисованные им многоугольники будут давать в объединении некоторый многоугольник $P_{n}$, на границу которого выходят многоугольники не менее $n$ цветов. Отсюда будет следовать, что никакого конечного числа цветов недостаточно.

База индукции очевидна. Пусть утверждение верно для $n=k$, докажем его для $n=k+1$. Из предположения индукции следует, что первый игрок может играть так, чтобы нарисованные многоугольники давали в объединении $k$ многоугольников $P_{k}^{(1)},P_{k}^{(2)},’cdots,P_{k}^{(k)}$, на границу каждого из которых выходят многоугольники не менее $k$ цветов. На границе многоугольника $P_{k}^{(1)}$ выделим отрезок $Delta_{1}$ некоторго цвета 1, на границе многоугольника $P_{k}^{(2)}$ выделим отрезок $Delta_{2}$ некоторго цвета 2, отличного от 1, и т.д., на границе многоугольника $P_{k}^{(k)}$ выделим отрезок $Delta_{k}$ некоторго цвета k, отличного от уже определенных цветов $1,2,cdots,k-1$. Пусть теперь первый нарисует многоугольник $P$, пересекающийся с многоугольником $P_{k}^{(i)}$ по части отрезка $Delta_{i}$ для всех $i=1,2,cdots,k$ (рис.). Второй игрок должен раскрасить многоугольник $P$ в цвет, отличный от цветов $1,2,cdots,k$. Тогда на границу многоугольника, являющего объединением многоугольников $P,P_{k}^{(1)},P_{k}^{(2)},cdots,P_{k}^{(k)}$, выходят не менее $k+1$ цветов. Переход индукции доказан.

Замечания

Строгое доказательство существования многоугольника $P$ из решения задачи далеко не просто (хотя интуитивно все очевидно), оно следует из известной топологической теоремы Жордана.

Отметим, что вопрос, поставленный в задаче, уже рассматривался в «Задачнике «Кванта»» для случая, когда первому игроку позволяется рисовать многоугольники лишь специального вида. Результат этой задачи интресно сопоставить также со знаменитой теоремой о четырех красках, согласно которой для раскрашивания правильным образом любой карты на плоскости достаточно лишь четырех цветов.

Журнал «Квант» — физико-математический журнал для школьников и студентов

ЯНВАРЬ/ФЕВРАЛЬ 1995 г. №1

Условие.

При каких натуральных $n>1$ в таблице

можно выбрать $n$ разных чисел в разных строках и разных столбцах?

Решение и ответ.

Ответ: при нечетном $n$ — можно, при четном — нельзя.

Будем считать, что таблица состоит из клеток $(x;y)$, где $x$ и $y$ — целые числа от $1$ до $n$, причем в клетке $(x;y)$ стоит число $f(x;y)$ от $1$ до $n$ такое, что: $f(x;y)=x+y(mod n).$

Т.е. разность $f(x;y)-(x+y)$ делится на $n$. (Очевидно, это расположение чисел такое же, как в условии).

Если выбраны числа в клетках $(x_{i};y_{i})$, стоящих в разных строках и разных столбцах $(i=1,2,…,n)$, то среди $x_{i}$ и среди $y_{i}$ каждое число $1,2,…,n$ встречается по разу, поэтому $x_{1}+…+x_{n} = y_{1}+…+y_{n} = n(n+1)/2$.

Если все числа $f(x_{i};y_{i})$ различны по модулю $n$, то и сумма $(x_{1}+y_{1})+…+(x_{n}+y_{n})=n(n+1)$

должна равняться $n(n+1)/2$ по модулю $n$. Но если $n$ чётно, $n=2k$, то разность $2k(2k+1)-k(2k+1)=k(2k+1)$

не делится на $n=2k$, так что выбрать числа требуемым образом нельзя.

Если же $n$ нечетно, то достаточно выбрать числа $f(x;y)$ в клетках $x=y$, идущих по диагонали, где все они различны (числа $2,4,…,2n$ дают разные остатки при делении на $n$).

Замечание.

Эта задача — по существу другая формулировка двух более известных:

Ответ. конечно, тот же, что и в задаче $M1472$.

Н.Васильев, А.Савин