Разбиение без квадратов Требуется разбить множество всех целых чисел от 1 до 2017 на три непустых непересекающихся подмножества таким образом, чтобы какие бы три числа (по одному из каждого подмножества) мы ни выбрали, произведение любых двух чисел из этих трёх, сложенное с третьим, НЕ являлось бы квадратом целого числа. Эта задача имеет удивительно простое и на мой взгляд удивительно красивое решение.http://www.mathforum.ru/forum/read/1/92233/92233/#92233Tue, 21 Apr 2026 01:19:42 +0300 Phorum 5.2.10 http://www.mathforum.ru/forum/read/1/92233/92254/#92254 Смешной (сквозь слёзы) рассказhttp://www.mathforum.ru/forum/read/1/92233/92254/#92254
Цитата
anton25

Рассказывайте, смеяться я люблю [smile].
Смешной (сквозь слёзы) рассказ: Данная задача нагло скоммунизжена у товарища Сатылханова (жду от него кренделей):
http://matol.kz/comments/2918/show
Только вот товарищ Сатылханов не потрудился доработать её малость.]]> xenia1996 Высшая математикаTue, 08 Aug 2017 15:25:47 +0300 http://www.mathforum.ru/forum/read/1/92233/92249/#92249 ...http://www.mathforum.ru/forum/read/1/92233/92249/#92249
Цитата
xenia1996
В первое подмножество кидаем только число 800, во второе - только число 1800, а в третье - всё, что осталось. Тогда, если складывать с 800, получится число, дающее остаток 2 при делении на 3 (а такое число не может быть квадратом). Если же складывать с 1800, получится число, которое делится на 8, но не делится на 16 (а значит, квадратом быть также не может). Ну и наконец, если складывать с элементом из третьего подмножества, получится число, превышающее квадрат числа 1200, но не дотягивающее до квадрата числа 1201.
Ну вот, интрига перешла в облом [biggrin]. По сути-то у Вас то же, что и у меня, только числа поудобней. Честно признаться, я немного на большее рассчитывал, так сказать, на кардинально иное решение, но не страшно. Числа везде круглые, квадраты точные, калькуляторы все сожжены и олимпийцы довольные [smile].
Цитата
xenia1996
Сейчас расскажу рецепт. Вот перед вами задача, в условии которой фигурируют числа от 1 до 2017. Попробуйте заменить 2017 на маленькие числа и увидеть закономерность. Возьмите, скажем, числа от 1 до 24. Видите что-нибудь?
Эйлером Вам быть [smile]. Я, если честно, сразу определил формат своей проверки (по последней цифре, по остатку и по недостатку) и решал эту задачу уже с параметром, а не с 2017, потом просто в решении конкретное значение задал. Показалось, что так интересней будет. Также очень интересным показался вопрос о возможности "разбиения без квадратов" всех натуральных чисел, но он вышел чуть сложнее чем ожидалось.

Цитата
xenia1996
Но это ещё цветочки. Вы будете бурно и долго смеяться, когда я вам расскажу, как эта задача вообще родилась на свет
Рассказывайте, смеяться я люблю [smile].]]> anton25 Высшая математикаMon, 07 Aug 2017 00:46:50 +0300 http://www.mathforum.ru/forum/read/1/92233/92244/#92244 Ну ладно, публикую моё решение:http://www.mathforum.ru/forum/read/1/92233/92244/#92244
В первое подмножество кидаем только число 800, во второе - только число 1800, а в третье - всё, что осталось. Тогда, если складывать с 800, получится число, дающее остаток 2 при делении на 3 (а такое число не может быть квадратом). Если же складывать с 1800, получится число, которое делится на 8, но не делится на 16 (а значит, квадратом быть также не может). Ну и наконец, если складывать с элементом из третьего подмножества, получится число, превышающее квадрат числа 1200, но не дотягивающее до квадрата числа 1201.

Сейчас расскажу рецепт. Вот перед вами задача, в условии которой фигурируют числа от 1 до 2017. Попробуйте заменить 2017 на маленькие числа и увидеть закономерность. Возьмите, скажем, числа от 1 до 24. Видите что-нибудь? Но это ещё цветочки. Вы будете бурно и долго смеяться, когда я вам расскажу, как эта задача вообще родилась на свет]]> xenia1996 Высшая математикаSat, 05 Aug 2017 23:23:15 +0300 http://www.mathforum.ru/forum/read/1/92233/92243/#92243 В добавлениеhttp://www.mathforum.ru/forum/read/1/92233/92243/#92243
Цитата
anton25
$2000\cdot1983=2000(2000-17)=2000^2-17\cdot2000\in\left((2000-9)^2;\,(2000-8)^2\right)$, а значит $\left[\sqrt{2000\cdot1983}\right]=2000-9=1991$,
после чего наше "долгое" сводится к вычислению столбиками $1992^2-2000\cdot1983$, что при крепких нервах у нормального успевающего школьника (на олимпиады все таки не слабых берут) займет не более 10 минут.
Еще раз на все посмотрел и заметил, что "долгие" 10 минут финальной проверки можно сделать короткими 1-2 минутами вот таким образом:
$1992^2-2000\cdot1983=1992^2-(1992+8)(1992-9)=1992^2-1992^2+1992+72=1992+72=2064$
Теперь под олимпиаду подлазием?[biggrin]]]> anton25 Высшая математикаSat, 05 Aug 2017 21:45:31 +0300 http://www.mathforum.ru/forum/read/1/92233/92241/#92241 Ответ2http://www.mathforum.ru/forum/read/1/92233/92241/#92241
Цитата
xenia1996
Антон, у Вас красивое решение, но оно не очень годится для олимпиады, так как убивает много времени. Ваша "несложная" проверка на олимпиаде не прокатит, долгая слишком. А вообще, будьте добры, распишите Вашу "несложную" проверку, что бы потом не обвинять меня в предвзятости
Ну, ОК. Пишу кратко: при $n\le2017$
1) $2000n+1983$ - не квадрат, т.к. оканчивается на 3,
2) $1983n+2000$ - не квадрат, т.к. дает остаток 2 при делении на 3 (2000=1998+2),
3) $2000\cdot1983+n$ - не квадрат, т.к. $\left(\left[\sqrt{2000\cdot1983}\right]+1\right)^2-2000\cdot1983>2017$

Я так понимаю под "долгая слишком" и "убивает много времени" Вы намекаете на возможное отсутствие калькуляторов на олимпиаде. В этом случае я все таки употребил бы фразу "нудная слишком", но уж никак не "долгая". С признаками делимости на 3 все знакомы. Кроме того, например, можно заметить, что
$2000\cdot1983=2000(2000-17)=2000^2-17\cdot2000\in\left((2000-9)^2;\,(2000-8)^2\right)$, а значит $\left[\sqrt{2000\cdot1983}\right]=2000-9=1991$,
после чего наше "долгое" сводится к вычислению столбиками $1992^2-2000\cdot1983$, что при крепких нервах у нормального успевающего школьника (на олимпиады все таки не слабых берут) займет не более 10 минут. Преимущество этого варианта в том, что он легко обобщается на общий случай и, на самом деле, если сразу решать эту задачу с параметрами, то и столбиков не потребуется. Ну это так к слову. Вы, кстати, до сих пор не показали своего "удивительно простого и удивительно красивого решения". Очень интересно. Ждемс!

P.S. Я, если честно, вообще сторонник небольшого подмешивания в олимпиады немного нудных вычислений хотя бы на каких-то этапах. Просто, как показывает опыт, привыкшие к изяществам, каким-то тонким трюкам и ходам люди, столкнувшись на практике с прикладными, но очень нудными и трудоемкими задачами просто напросто бросают их решать, чуть ли не саботируя таким образом целые проекты. Все таки олимпиады должны выделять не только самых сообразительных, но еще и работоспособных людей.]]> anton25 Высшая математикаSat, 05 Aug 2017 18:30:22 +0300 http://www.mathforum.ru/forum/read/1/92233/92238/#92238 Красиво, но...http://www.mathforum.ru/forum/read/1/92233/92238/#92238
Цитата
anton25
Ну, проходит, например, такой вариант $A=\{1983\}$, $B=\{2000\}$ и $C$ - все остальные. Проверяется несложно. А вообще, при желании здесь можно привести нужное разбиение даже для чуть более общего случая. Если, к примеру, вместо 2017 взять произвольное целое $M$, то можно доказать, что при $M>120$ проходит такое разбиение: $A=\{M_1\}$, $B=\{M_2\}$ и $C$ - все остальные, где
$M_1=30\cdot\left[\frac{M}{30}\right]-27$,
$M_2=30\cdot\left[\frac{M}{30}\right]-10$.

P.S. Интересно, существует ли подобное разбиение (как в условии) множества всех натуральных чисел. Думается, что нет, но вот доказать это, судя по всему, достаточно непросто.
Антон, у Вас красивое решение, но оно не очень годится для олимпиады, так как убивает много времени. Ваша "несложная" проверка на олимпиаде не прокатит, долгая слишком. А вообще, будьте добры, распишите Вашу "несложную" проверку, что бы потом не обвинять меня в предвзятости [biggrin]]]> xenia1996 Высшая математикаSat, 05 Aug 2017 11:03:42 +0300 http://www.mathforum.ru/forum/read/1/92233/92237/#92237 Ответhttp://www.mathforum.ru/forum/read/1/92233/92237/#92237$A=\{1983\}$, $B=\{2000\}$ и $C$ - все остальные. Проверяется несложно. А вообще, при желании здесь можно привести нужное разбиение даже для чуть более общего случая. Если, к примеру, вместо 2017 взять произвольное целое $M$, то можно доказать, что при $M>120$ проходит такое разбиение: $A=\{M_1\}$, $B=\{M_2\}$ и $C$ - все остальные, где
$M_1=30\cdot\left[\frac{M}{30}\right]-27$,
$M_2=30\cdot\left[\frac{M}{30}\right]-10$.

P.S. Интересно, существует ли подобное разбиение (как в условии) множества всех натуральных чисел. Думается, что нет, но вот доказать это, судя по всему, достаточно непросто.]]> anton25 Высшая математикаSat, 05 Aug 2017 00:40:36 +0300 http://www.mathforum.ru/forum/read/1/92233/92233/#92233 Разбиение без квадратовhttp://www.mathforum.ru/forum/read/1/92233/92233/#92233
Эта задача имеет удивительно простое и на мой взгляд удивительно красивое решение.]]> xenia1996 Высшая математикаThu, 03 Aug 2017 15:06:42 +0300