Задача
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).
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь