|
|
 |
Условие
Дана таблица n×n клеток и такие натуральные числа k и m > k, что m и n – k взаимно просты. Таблица заполняется следующим образом: пусть в некоторой строчке записаны числа a1, ..., ak, ak+1, ..., am, am+1, ..., an. Тогда в следующей строчке записываются те же числа, но в таком порядке: am+1, ..., an, ak+1, ..., am, a1, ..., ak. В первую строчку записываются (по порядку) числа 1, 2, ..., n. Доказать, что после заполнения таблицы в каждом столбце будут написаны все числа от 1 до n.
Решение
Очевидно достаточно доказать, что ни одно из чисел не вернётся на свое место во 2-й, 3-й, ... , n-й строках. Проследим за судьбой какого-нибудь числа a. При переходе в следующую строку оно сдвигается вправо на одно из (положительных или отрицательных) чисел s = n – k, s – m = n – m – k, – m. Пусть после нескольких шагов оно x раз побывало в первой группе (на одном из мест от 1 до k), y раз – во второй, z раз – в третьей и при этом впервые вернулось на исходное место. Тогда sx + (s – m)y – mz = 0, 0 ≤ x ≤ k, 0 ≤ y ≤ m – k, 0 ≤ z ≤ n – m.
Обозначим s = n – k. Наше уравнение можно переписать в виде s(x + y) = m(y + z). Так как m и s взаимно просты по условию, то x + y делится на m и y + z делится на s. Но 0 ≤ x + y ≤ m и 0 ≤ y + z ≤ s, откуда либо x = y = z = 0, либо x = n – s, y = m + s – n, z = n – m. Первый случай нас не интересует, а во втором случае x + y + z = n, то есть число a возвращается на свое место в (n+1)-й строке, то есть уже за пределами таблицы.
