Республиканская олимпиада по математике, 2003 год, 9 класс

$a_1, a_2, \ldots, a_{101}$ — перестановка чисел $2, 3, 4, \ldots, 102$ такая, что $a_k$ делится на $k$ для каждого $k$. Найдите все такие перестановки.

Комментарий/решение

Так как у нас есть числа от 2 до 102, тогда

а101=101(так как среди тех чисел нету числа который делится на 101), то же самое делаем с числами от а100 до а52.

после , у нас остались числа 102,51,50...2.

а50=50, так как 100 уже занято.

а49=49

.....

a18=18.

Теперь остались числа 102,51,17,16...2

а16=16, потому что не осталось чисел делящихся на 16

а15=15

...

а4=4

а2=2

Остались числа 102,51,17,3

И числа а51,а17,а3 и а1.

Дальше подставляя числа сверху к числам снизу , можно заметить, что подходят лишь 6 перестановок.

Ответ:6 перестановок

а34,а6 и а2 также могут быть равны к 102.

а101,а100.....а52 строго будут равны к соответсвующим $k$. (а101=101,а100=100 и тд.).

а50,а49,а48....а35 также строго будут равны к соответсвующим $k$, так как другие кратные числа уже заняты. Аналогично и с числами а33,а32...а18, а16,а15,а14...а7, а5 и а4.

После этого остался набор чисел состоящих из #2,3,6,17,34,51,102# и #а1,а2,а3,а6,а17,а34,а51#. Ниже указан все возможные перестановки этих чисел.

Случай1)а51=102,а34=34,а6=6,а2=2,а3=3, а17=17,а1=51.

Случай2)а51=102,а34=34,а6=6,а2=2,а3=51,а17=17,а1=3.

Случай3)а51=102,а34=34,а6=6,а2=2,а3=3,а17=51а1=17.

Случай4)а34=102,а51=51,а6=6,а3=3,а2=34,а17=17,а1=2.

Случай5)а34=102,а51=51,а6=6,а3=3,а2=2,а17=17,а1=34.

Случай6)а34=102,а51=51,а6=6,а3=3,а2=2,а17=34,а1=17.

$OTBET$ = $6$