Разбиение без квадратов

[Ktina]

Требуется разбить множество всех целых чисел от 1 до 2017 на три непустых непересекающихся подмножества таким образом, чтобы какие бы три числа (по одному из каждого подмножества) мы ни выбрали, произведение любых двух чисел из этих трёх, сложенное с третьим, НЕ являлось бы квадратом целого числа.

Эта задача имеет удивительно простое и на мой взгляд удивительно красивое решение.

[worm2]

Красивого не нашёл, но, вроде бы, $\{2009\}$, $\{2016\}$ и $\{\text{всё остальное}\}$ подходит. Для того, чтобы $2009\times 2016+n\in\mathbb{N}$ было квадратом, $n$ должно быть как минимум 2025, а нету такого. $2009n+2016$ не может быть квадратом по делимости на 41 (вот это самое некрасивое место) вот я тупой, потому что делится на 7, но не на 49, $2016n+2009$ — по делимости на 3.

[Ktina]

worm2
Красиво, но можно ещё проще

-- 03.08.2017, 16:12 --

И без делимости на 41 и прочие большие числа.

-- 03.08.2017, 16:13 --

Потому что на настоящей олимпиаде можно запариться потратить много времени на соображения делимости на 41.

-- 03.08.2017, 16:14 --

А, пардон, Вы же зачеркнули 41...
Но всё равно можно ещё проще!

-- 03.08.2017, 16:16 --

У Вас самый трудный момент - 2025 НЕ квадратов, это же надо как-то сосчитать, а на олимпиаде время поджимает, не годится...

-- 03.08.2017, 16:24 --

Так или иначе, я Ваше решение хвалю и приветствую.

[Ktina]

Наверно, напишу уже своё, или можно ещё подождать?

[Ktina]

Ну ладно, публикую:

В первое подмножество кидаем только число 800, во второе - только число 1800, а в третье - всё, что осталось. Тогда, если складывать с 800, получится число, дающее остаток 2 при делении на 3 (а такое число не может быть квадратом). Если же складывать с 1800, получится число, которое делится на 8, но не делится на 16 (а значит, квадратом быть также не может). Ну и наконец, если складывать с элементом из третьего подмножества, получится число, превышающее квадрат числа 1200, но не дотягивающее до квадрата числа 1201.

Сейчас расскажу рецепт. Вот перед вами задача, в условии которой фигурируют числа от 1 до 2017. Попробуйте заменить 2017 на маленькие числа и увидеть закономерность. Возьмите, скажем, числа от 1 до 24. Видите что-нибудь? Но это ещё цветочки. Вы будете бурно и долго смеяться, когда я вам расскажу, как эта задача вообще родилась на свет!

[svv]

Понятно. Значит, в первом подмножестве только число $a=8m$, во втором только $b=18m$, а в третьем все остальные. Здесь $m=3k+1$.
Если $m$ чётно, то $a$ делится на $16$, а $b$ только на $8$.
Если $m$ нечётно, то $a$ делится на $4$, а $b$ только на $2$.

Число $m$ подбирается так, чтобы зазор между $(ab)^2=(12m)^2$ и следующим квадратом вмещал все числа от $1$ до $n$. Это значит, что $n\leqslant 24m$. С другой стороны, $b=18m \leqslant n$.

При больших $n$ отрезки $[18m;24m]$ для соседних $m$ даже перекрываются, и есть выбор. Но для малых остаются дыры, и надо как-то модифицировать шаблон.