Processing math: 100%

M1472

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

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

Условие.

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

1 2 3 n1 n
n 1 2 n2 n1
n1 n 1 n3 n2
3 4 5 1 2
2 3 4 n 1

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

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

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

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

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

Если выбраны числа в клетках (xi;yi), стоящих в разных строках и разных столбцах (i=1,2,,n), то среди xi и среди yi каждое число 1,2,,n встречается по разу, поэтому x1++xn=y1++yn=n(n+1)/2.

Если все числа f(xi;yi) различны по модулю n, то и сумма (x1+y1)++(xn+yn)=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).

Замечание.

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

(1) Можно ли выписать две перестановки чисел 1,2,,n одну под другой так, чтобы суммы чисел по столбцам давали различные остатки от деления на n?
(2) Пусть n штырьков радиолампы и n соответствующих гнезд розетки, в которую она втыкается, расположены по кругу в вершинах правильного n-угольника. Можно ли штырьки и гнезда занумеровать числами 1,2,,n так, чтобы при любом втыкании лампы в розетку ровно один штырек попадал в гнездо с тем же номером?

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

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