МОШ 2026, 10 класс, задача 5
Назовём набор из k последовательных натуральных чисел хорошим, если можно
у каждого из этих чисел выбрать по простому делителю так, чтобы у всяких двух разных чисел
были выбраны разные делители. В противном случае назовём набор плохим. При всяком ли
натуральном k количество плохих наборов из k последовательных натуральных чисел конечно?
Ответ
Ответ: да, количество плохих наборов конечно для любого натурального .
Решение. Пусть . Докажем, что набор является хорошим.
Отметим, что любая пара чисел этого набора не может иметь общий делитель, больший . Действительно, если есть такой общий делитель, то разность чисел также имеет этот делитель, но все разности меньше .
Разделим все числа нашего набора на две группы. В первую группу возьмём те числа, у которых есть хотя бы один простой делитель, больший , во вторую группу — все остальные числа.
Каждому числу из первой группы просто сопоставим любой простой делитель, который больше . Ясно, что данные простые делители не будут совпадать.
Пусть — все простые числа, не большие . Каждое из этих чисел второй группы можно представить в виде , где — целые неотрицательные числа. Для каждого из чисел такого вида выберем делитель такой, что максимален среди множителей . Из условия следует, что для этого будет выполнено . Тогда выбранные простые числа будут различны, иначе у каких-то двух чисел набора будет общий делитель, больший .