Журнал «Квант» — физико-математический журнал для школьников и студентов
ЯНВАРЬ/ФЕВРАЛЬ 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(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).
Замечание.
Эта задача — по существу другая формулировка двух более известных:
Ответ. конечно, тот же, что и в задаче M1472.
Н.Васильев, А.Савин