Условие

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

Решение

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

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

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

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

К.Чувилин

Ответ: 25.

Задача М2098

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

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

Решение

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

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

Замечания

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

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

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

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

Условие.

При каких натуральных [latex]n>1[/latex] в таблице

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

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

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

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

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

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

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

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

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

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

Замечание.

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

Ответ. конечно, тот же, что и в задаче [latex]M1472[/latex].

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