ВсОШ 2026, 9 класс, задача 6

Ответ: ; .

Решение. Разобьём все числа от до на несколько цепочек: первая — — числа с остатком при делении на , вторая — — числа с остатком при делении на , третья — — числа с остатком при делении на и т.д. до последней, одиннадцатой, — — делящиеся на . В первых двух по чисел, в остальных девяти — по . Заметим, что числа, лежащие в разных цепочках, не могут отличаться на , поэтому нам достаточно выбрать наибольшее возможное количество чисел отдельно в каждой цепочке. Разобьем числа в цепочке на пары соседних (например, и , и , и и т.д.). Мы не можем выписать два соседних числа, т.к. они отличаются на . Тогда в цепочках с числами получается пар и одно число без пары, т.е. мы можем выбрать не более чисел. В цепочках с числами — пар и мы тоже можем выбрать не более чисел. Значит, всего мы можем выбрать не более чисел. Это можно сделать, если во всех цепочках брать числа, стоящие через одно, начиная с первого.

Посчитаем теперь количество способов выписать чисел. В цепочках с числами чисел можно выписать ровно одним способом. Цепочки с числами мы разбили на пар. Если в какой-то паре мы выписали большее число, то во всех последующих парах мы обязаны выписать тоже большее число. Выбрать пару, в которой выписано большее число мы можем способами ( пар + вариант, когда во всех парах выписано меньшее число), значит выписать чисел из такой цепочки мы можем способами. Цепочек с числами две, значит всего вариантов .