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

ЯНВАРЬ/ФЕВРАЛЬ 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].

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