Решение задачи 332

Условие:

а) Выписаны числа от 1 до 13. Раскрасьте их в два цвета так, чтобы отношение чисел одинакового цвета не было простым числом.

б) Выписаны 100 произвольных натуральных чисел. Докажите, что их можно покрасить в два цвета так, чтобы отношение чисел одинакового цвета не было простым числом.

Решение:

а) Выписываем в ряд 13 чисел:

1,2,3,4,5,6,7,8,9,10,11,12,13

Понятно, что число 1 не может быть покрашено в один цвет ни с одним простым числом, поэтому сначала покрасим жирным все простые числа:

1,2,3,4,5,6,7,8,9,10,11,12,13

Простые числа могут быть покрашены в один цвет, поскольку отношение любых двух простых чисел простым числом не является. Заметим, что числа 4 и 12, 4 и 8 не могут быть покрашены в один цвет, поэтому покрасим 12 и 8 жирным:

1,2,3,4,5,6,7,8,9,10,11,12,13

Осталось убедиться в том, что данная раскраска удовлетворяет всем условиям задачи.

б) Теперь используя результат пункта а проще цвидеть общее свойство, которым обладают числа одной группы. Сумма степеней простых делителей числа первой группы четна, а второй - нечетна. Раскрасим с помощью этого свойства произвольные 100 чисел. Теперь докажем, что отношение чисел одной группы не будет простым числом. Допустим сумма степеней простых делителей двух чисел четна. Тогда легко заметить, что если отношение этих чисел является целым числом, то сумма степеней простых делителей отношения также четна. Поэтому отношение не является простым числом (сумма степеней простых делителей простого числа равна 1). Аналогично и для чисел второй группы - сумма степеней простых делителей отношения двух чисел из второй группы также четная, поэтому отношение не является простым числом.