СПбГУ 2024, 8-9 классы, задача 2
( баллов) Есть кроликов и клеток, клетки пронумерованы числами от до , а кролики - числами от до . Кроликов рассаживают по клеткам (по одному кролику в клетку) так, чтобы номер каждого кролика был взаимно прост с номером его клетки. Докажите, что количество способов так рассадить кроликов по клеткам не меньше, чем тысяч.
Ответ
Решение. Сначала приведем один способ рассадить кроликов по клеткам. При посадим -го кролика в клетку с номером . Если числа и имеют общий делитель, то этот же делитель имеет их сумма , являющаяся простым числом. Но число не делится на . Поэтому правило рассадки соблюдено.
Имеется восемь кроликов, номера которых являются простыми числами: , , , , , , и . Этих кроликов можно произвольно пересаживать по тем восьми клеткам, которые они занимают, потому что номер любого из этих кроликов - простое число, которое больше номера любой клетки, из-за чего оно не может иметь общих делителей с номером клетки. Количество способов рассадить кроликов по клеткам равно . Мы уже предъявили способов рассадки, поэтому общее количество способов не меньше .