Назад
Задача

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).

Ответ

Ответ задачи отсутствует

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет