M1472

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

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

Условие.

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

1 2 3 ... n-1 n
n 1 2 ... n-2 n-1
n-1 n 1 ... n-3 n-2
... ... ... ... ... ...
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(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).

Замечание.

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

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

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

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

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *