03.08.2017 15:06 Дата регистрации:
14 лет назад Посты: 523 | Разбиение без квадратов Требуется разбить множество всех целых чисел от 1 до 2017 на три непустых непересекающихся подмножества таким образом, чтобы какие бы три числа (по одному из каждого подмножества) мы ни выбрали, произведение любых двух чисел из этих трёх, сложенное с третьим, НЕ являлось бы квадратом целого числа. Эта задача имеет удивительно простое и на мой взгляд удивительно красивое решение. ----------------------------------------------------- И не ракета орлиная Таню берегла, и дни лежат в небе тем лесом. Наш Вася Тараканечкин променял-таки Кацечку на Тацечку (Кацечка и Тацечка — это общеславянские ласкательные варианты имён Екатерина и Татьяна (Тетяна) соответственно).
|
05.08.2017 00:40 Дата регистрации:
14 лет назад Посты: 780 | Ответ Ну, проходит, например, такой вариант $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. Интересно, существует ли подобное разбиение (как в условии) множества всех натуральных чисел. Думается, что нет, но вот доказать это, судя по всему, достаточно непросто.
|
05.08.2017 11:03 Дата регистрации:
14 лет назад Посты: 523 | Красиво, но... Цитата
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. Интересно, существует ли подобное разбиение (как в условии) множества всех натуральных чисел. Думается, что нет, но вот доказать это, судя по всему, достаточно непросто.
Антон, у Вас красивое решение, но оно не очень годится для олимпиады, так как убивает много времени. Ваша "несложная" проверка на олимпиаде не прокатит, долгая слишком. А вообще, будьте добры, распишите Вашу "несложную" проверку, что бы потом не обвинять меня в предвзятости  ----------------------------------------------------- И не ракета орлиная Таню берегла, и дни лежат в небе тем лесом. Наш Вася Тараканечкин променял-таки Кацечку на Тацечку (Кацечка и Тацечка — это общеславянские ласкательные варианты имён Екатерина и Татьяна (Тетяна) соответственно).
|
05.08.2017 18:30 Дата регистрации:
14 лет назад Посты: 780 | Ответ2 Цитата
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. Я, если честно, вообще сторонник небольшого подмешивания в олимпиады немного нудных вычислений хотя бы на каких-то этапах. Просто, как показывает опыт, привыкшие к изяществам, каким-то тонким трюкам и ходам люди, столкнувшись на практике с прикладными, но очень нудными и трудоемкими задачами просто напросто бросают их решать, чуть ли не саботируя таким образом целые проекты. Все таки олимпиады должны выделять не только самых сообразительных, но еще и работоспособных людей.
|
05.08.2017 21:45 Дата регистрации:
14 лет назад Посты: 780 | В добавление Цитата
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$Теперь под олимпиаду подлазием?
|
05.08.2017 23:23 Дата регистрации:
14 лет назад Посты: 523 | Ну ладно, публикую моё решение: Ну ладно, публикую: В первое подмножество кидаем только число 800, во второе - только число 1800, а в третье - всё, что осталось. Тогда, если складывать с 800, получится число, дающее остаток 2 при делении на 3 (а такое число не может быть квадратом). Если же складывать с 1800, получится число, которое делится на 8, но не делится на 16 (а значит, квадратом быть также не может). Ну и наконец, если складывать с элементом из третьего подмножества, получится число, превышающее квадрат числа 1200, но не дотягивающее до квадрата числа 1201. Сейчас расскажу рецепт. Вот перед вами задача, в условии которой фигурируют числа от 1 до 2017. Попробуйте заменить 2017 на маленькие числа и увидеть закономерность. Возьмите, скажем, числа от 1 до 24. Видите что-нибудь? Но это ещё цветочки. Вы будете бурно и долго смеяться, когда я вам расскажу, как эта задача вообще родилась на свет ----------------------------------------------------- И не ракета орлиная Таню берегла, и дни лежат в небе тем лесом. Наш Вася Тараканечкин променял-таки Кацечку на Тацечку (Кацечка и Тацечка — это общеславянские ласкательные варианты имён Екатерина и Татьяна (Тетяна) соответственно).
|
07.08.2017 00:46 Дата регистрации:
14 лет назад Посты: 780 | ... Цитата
xenia1996
В первое подмножество кидаем только число 800, во второе - только число 1800, а в третье - всё, что осталось. Тогда, если складывать с 800, получится число, дающее остаток 2 при делении на 3 (а такое число не может быть квадратом). Если же складывать с 1800, получится число, которое делится на 8, но не делится на 16 (а значит, квадратом быть также не может). Ну и наконец, если складывать с элементом из третьего подмножества, получится число, превышающее квадрат числа 1200, но не дотягивающее до квадрата числа 1201.
Ну вот, интрига перешла в облом . По сути-то у Вас то же, что и у меня, только числа поудобней. Честно признаться, я немного на большее рассчитывал, так сказать, на кардинально иное решение, но не страшно. Числа везде круглые, квадраты точные, калькуляторы все сожжены и олимпийцы довольные  . Цитата
xenia1996
Сейчас расскажу рецепт. Вот перед вами задача, в условии которой фигурируют числа от 1 до 2017. Попробуйте заменить 2017 на маленькие числа и увидеть закономерность. Возьмите, скажем, числа от 1 до 24. Видите что-нибудь?
Эйлером Вам быть . Я, если честно, сразу определил формат своей проверки (по последней цифре, по остатку и по недостатку) и решал эту задачу уже с параметром, а не с 2017, потом просто в решении конкретное значение задал. Показалось, что так интересней будет. Также очень интересным показался вопрос о возможности "разбиения без квадратов" всех натуральных чисел, но он вышел чуть сложнее чем ожидалось. Цитата
xenia1996
Но это ещё цветочки. Вы будете бурно и долго смеяться, когда я вам расскажу, как эта задача вообще родилась на свет
Рассказывайте, смеяться я люблю .
|
08.08.2017 15:25 Дата регистрации:
14 лет назад Посты: 523 | Смешной (сквозь слёзы) рассказ Цитата
anton25Рассказывайте, смеяться я люблю .
Смешной (сквозь слёзы) рассказ: Данная задача нагло скоммунизжена у товарища Сатылханова (жду от него кренделей): http://matol.kz/comments/2918/show Только вот товарищ Сатылханов не потрудился доработать её малость. ----------------------------------------------------- И не ракета орлиная Таню берегла, и дни лежат в небе тем лесом. Наш Вася Тараканечкин променял-таки Кацечку на Тацечку (Кацечка и Тацечка — это общеславянские ласкательные варианты имён Екатерина и Татьяна (Тетяна) соответственно).
|
