Сколько цифр взять, чтобы было несвободное от квадратов?

[Ktina]

Найти минимальное целое число $k$, обладающее следующим свойством: в любом множестве из $k$ различных десятичных цифр существуют два элемента, что составленное ими двузначное число делится на квадрат целого числа, большего 1.

[gris]

Напрямую с ума сойдёшь. От противного надо приводить примеры множеств, из которых нельзя получить таких чисел.
Например: $k=2: (1,3); k=3: (0,1,3); k=4: (0,1,3,7)$
Для $k=5$... Нельзя, честное слово! Легко, но некрасиво. После небольшого подсчёта возможностей соседства, шесть претендентов покидают спсок.

[Ktina]

gris в сообщении #1109202 писал(а):

Напрямую с ума сойдёшь.

У меня есть очень лёгкое и красивое решение. Я немного подожду, вруг кто-нибудь додумается?

[lopkityu]

Действительно, $ k=5 $. Возьмём три множества: $ A=\{0, 4, 8, 9\}, B=\{2, 5, 7\}, C=\{3, 6\} $. Легко убедиться, что для каждой пары элементов, принадлежащих одному из множеств, хотя бы одно из образуемых ими чисел не является свободным от квадратов. Остается подметить, что среди любых 5 разных цифр хотя бы две одновременно будут принадлежать $ A, B $ или $ C $.

[Ktina]

lopkityu
Спасибо!

А теперь выложу своё:

Мне кажется, что ответ будет 5.

Действительно, разобьём все десятичные цифры на 4 группы: (0, 4, 9), (1, 2, 8), (5, 6, 7), (3).
Если в нашем множестве 5 цифр, то из какой-то вышеуказанной группы взяты как минимум две цифры, а они образуют число, несвободное от квадратов.

С другой стороны, четырёх цифр явно не достаточно, ведь множество из цифр 1, 3, 4 и 7 нарушает условие задачи.