|
|
 |
Условие
a1, a2, ..., a101 – такая перестановка чисел 2, 3, ..., 102, что ak делится на k при каждом k. Найти все такие перестановки.
Решение
Добавим а102 = 1. Мы получили подстановку на множестве {1, 2, ..., 102}. Она распадается на циклы. Но наименьшее число нетривиального (содержащего более одного числа) цикла стоит на месте с номером, большим самого числа. По условию таким числом может быть только 1, следовательно, нетривиальный цикл только один (и состоит из некоторых делителей числа 102, каждый из которых является делителем следующего), а остальные циклы тривиальны. Вот все варианты нетривиальных циклов (их 13):
(1, 102), (1, 2, 102), (1, 3, 102), (1, 6, 102), (1, 17, 102), (1, 34, 102), (1, 51, 102), (1, 2, 6, 102), (1, 2, 34, 102), (1, 3, 6, 102), (1, 3, 51, 102),
(1, 17, 34, 102), (1, 17, 51, 102).
Замечания
Другой подход. Заметим, что произведение целых чисел ak/k равно 102, следовательно, каждому упорядоченному разложению 102 на множители соответствует перестановка. Например, разложению 102 = 3·2·17 соответствует перестановка a1 = 3, a3 = 3·2 = 6, a6 = 102.
