Настя записала на доске 9 трехзначных простых чисел...

[Гость]

Настя записала на доске 9 трехзначных простых чисел. Обязательно ли среди них найдутся два числа с разностью, кратной 30?

[Kreativshik]

Да, обязательно. Количество возможных остатков от деления на 30 для таких чисел φ(30) = 8 (это 1, 7, 11, 13, 17, 19, 23, 29). По принципу Дирихле, если взять 9 чисел и разместить их по 8 классам вычетов, то хотя бы два числа попадут в один класс, и их разность будет кратна 30.