Найдите количество способов раскрасить все натуральные числа от 1 до 20 в красный и синий цвета так, чтобы оба цвета встречались, и произведение всех красных чисел было взаимно просто с произведением всех синих чисел.
Задача была предложена на олимпиаде "Курчатов" по математике 9 марта 2020 года.
Покрасим число 2 в какой-то цвет. Назовём его первым. Тогда все числа, кратные 2, т.е. 4, 6, 8, ..., 18, 20 мы тоже должны покрасить первый цвет. Иначе произведения чисел разных цветов не будут взаимно простыми.
Среди чисел первого цвета оказалось число 6, которое делится на 3. Но тогда и все остальные числа, делящиеся на 3, должны быть покрашены в первый цвет.
Среди чисел первого цвета оказалось число 10, которое делится на 5. Но тогда и все остальные числа, делящиеся на 5, должны быть покрашены в первый цвет.
Какие числа остались непокрашенными?
1 и простые числа 11, 13, 17, 19.
Их мы можем красит в любой цвет, и условие про взаимную простоту не нарушится.
Итак, двумя способами можно покрасить группу чисел, в которую входит двойка; двумя способами можно покрасить единицу; двумя способами можно покрасить 11; ...; двумя способами можно покрасить 19.
Так как эти раскраски независимы, то получается 2^6=64 способов.
Но среди них есть два способа, когда мы всё покрасили в один цвет (красный или синий). Эти два способа надо вычесть.
В итоге получается 2^6-2=62.