17 таинственных чисел

[Ktina]

Среди любых 17 (попарно различных -- прим. ред.) натуральных чисел от 1 до $n$ можно выбрать два (различных -- прим. ред.) числа так, что их произведение будет точным квадратом.

Найти наибольшее возможное значение $n$.

[Руст]

Ясно, что $n<29$, иначе берем число1, и 10 простых чисел от 2 до 29 и удвоенные нечетные простые 6,10,14,22,26 еще 15.
А при $n=28$ все нормально.

[Ktina]

Руст, а я при $n=26$ взяла 1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26.

Что я проморгала?

[Руст]

Я пропустил, что $3*7$ так же мал, т.е. с утроенных надо брать $3*5,3*7$.

[Ktina]

Вот моё решение:

Ответ: 25.

При $n=25$:

Из чисел 1, 4, 9, 16 и 25, можно выбрать не более одного, так как все они квадраты.
Из пар (2, 8), (3, 12), (5, 20), (6, 24) также не более одного.
Таким образом, не более 17 чисел.
Но если выберем ровно 17 чисел, среди них придётся оказаться числу 18 (это следует из предыдущих выкладок).
Но одно из чисел 2 и 8 тоже обязано быть среди этих 17. Однако, $18\cdot 2=6^2\quad\text{и}\quad 18\cdot 8=12^2$.
Таким образом, 17 чисел выбрать не получится.

При $n\ge 26$ я уже написала выше.

[Руст]

немного точнее, мы отображаем $N\to Bin$, ставя числу $n$ последовательность нулей и 1 из $Bin$ по формуле $n=p_1^{k_1}p_2^{k_2}...p_m^{k_m}\to (l_1,l_2,...,l_m,0,...)$, где $l_i=1$. если $k_i$ нечетно, иначе 0.
Если у образов $m$ и $n$ одинаковые последовательности битов, то $mn$ квадрат (и только тогда). Вот и распределяем по образам, пока не появилась 17-я последовательность:
(0,0,...) -(1,4,9,16,25,....
(1,0,...)-(2,8,18,32,...)
(0,1,0,...)-(3,12,27,...)
(0,0,1,...)-(5,20,...)
(1,1,0,...)-(6,24,...)
....

[Ktina]

Руст в сообщении #680598 писал(а):

немного точнее, мы отображаем $N\to Bin$, ставя числу $n$ последовательность нулей и 1 из $Bin$ по формуле $n=p_1^{k_1}p_2^{k_2}...p_m^{k_m}\to (l_1,l_2,...,l_m,0,...)$, ....

(Оффтоп)

Помните фильм "Приключения Электроника"?
Там кое-кто задачку для шестого класса через "интригал" решал

[Руст]

Понятно, что школьная задача. Но а если вместо m=17, будет m=170000 или больше, то только приводя к уравнению
$f(n)=\sum_{k=1}^{[\sqrt n]} \mu(k)[\frac{n}{k^2}] <m$. Примерно ясно, что $n$ в районе $m\frac{\pi^2}{6}$.

[Ktina]

Руст, у Вас очень красивое решение, просто я фильм вспомнила