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

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

задан 3 Авг '17 16:18

Тащит меня почему-то вот в эту сторону: 2017, 2011 и все остальные числа...

(3 Авг '17 22:15) kipot_l

Или другой вариант - 44^2, 43^2 и все остальные числа. А если что, так у меня ещё много вариантов в запасе...

(3 Авг '17 22:37) kipot_l
1

@kipot_l: по первому варианту: 2017*2011+9 является квадратом.

По второму варианту: 1761*43^2+44^2 является квадратом.

Также 1850*44^2+43^2 есть точный квадрат.

(3 Авг '17 23:05) falcao
1

@falcao: последний на сегодня вариант. Типа 2015 (кратно 5), и 1008 (половина от 2015, кратно 3) и все остальные числа (!). Результаты умножения будут типа 5К+3 и 3К+2 (не являются точным квадратом по остаткам), а произведение 1008*2015 лежит слишком далеко от ближайшего точного квадрата.

(4 Авг '17 1:07) kipot_l
1

@kipot_l: а вот это, я так понимаю, уже проходит! Есть смысл оформить комментарий в виде решения.

(4 Авг '17 9:11) falcao
1

@falcao, у меня решение проще и красивее, и для олимпиады годится, потому что на олимпиаде времени мало, а на "1008*2015 лежит слишком далеко от ближайшего точного квадрата" времени много убьётся :)

(4 Авг '17 17:07) Аллочка Шакед
1

Аллочка, только не публикуйте решение! Пусть народ пашет... I am sorry, но разбиений на такие три множества может быть "туча"! Могу опубликовать с десяток... И последнее, - 1008, 2015, и все остальные числа - это решение (одно из) задачи? Уж откуда я его взял, это второй вопрос...

(4 Авг '17 18:33) kipot_l
1

@Аллочка Шакед: задача красивая, и я довольно много над ней вчера размышлял, но устно -- за неимением бумаги по рукой. Были разные идеи, но ни одна из них не подошла. То, что оказалось возможным обособить по одному числу, было для меня неожиданностью.

(4 Авг '17 20:29) falcao

@falcao, бумаги, говорите, под рукой не было? Вы сейчас будете бурно и долго смеяться, но мне удалось додуматься до решения этой задачи вообще во время поездки в городском автобусе :) Министры, правда, на автобусах не ездят, но ведь я же не настоящая Аллочка :)

(5 Авг '17 1:18) Аллочка Шакед
1

@Аллочка Шакед: вполне допускаю, что то решение, которое Вы нашли, проверяется как-то быстро и сразу. Но дело в том, что я пробовал очень много разных вариантов, основанных на той или иной идее (типа перехода к остаткам от деления по какому-то модулю). Ни один из них не подошёл. При таком анализе записи на бумаге иной раз способны помочь в процессе нахождения нужной конструкции.

(5 Авг '17 7:43) falcao

@Аллочка Шакед: 1. Сознаюсь, что я унизился до того, чтобы использовать калькулятор. Но я ещё не забыл, как делить, умножать, возводить в квадрат и извлекать корень "ручками". Олимпиадная норма времени на задачу - от 5 минут до 4-х часов. За четыре часа при наличии бумаги вполне возможно умножить 1008 на 2015 и извлечь корень из произведения с точностью 2 знака после запятой. Мне повезло, я сразу угадал одно из решений задачи.

(5 Авг '17 9:17) kipot_l
1

@Аллочка Шакед: 2. Что считать решением задачи? Указать один вариант разбиения, или описать их все? Ваше решение описывает все решения задачи? Задача имеет далеко не единственное решение. Их, похоже, десятки и десятки, даже такого вида - А, В, и все остальные 2015 чисел. Задача интересна тем, что имеет естественные обобщения, для начала по количеству чисел в общем наборе и в искомых подмножествах.

(5 Авг '17 9:25) kipot_l
показано 5 из 12 показать еще 7
10|600 символов нужно символов осталось
2

Рискну предложить еще один вариант конструкции.

Как и в двух предыдущих решениях, пусть два из трех множеств состоят всего из одного числа. Для первого множества им будет число $%p^3\cdot q$%, а для второго число $%q^3\cdot p$%, где $%p$% и $%q$% - различные простые числа.

Тогда суммы вида $%p^3q n + q^3p$% не являются точными квадратами ни при каком натуральном $%n$%, поскольку делятся на $%p$%, но не делятся на $%p^2$%, и для второго сложения аналогично.

Осталось проверить только суммы $%p^3q\cdot q^3p + n$%, где $%n$% пробегает все третье множество, то есть может являться любым числом от 1 до 2017, кроме двух уже выбранных. Нам достаточно, чтобы все эти суммы были между двумя соседними квадратами, то есть между $%(p^2q^2)^2$% и $%(p^2q^2+1)^2$%. Здесь одно из двух неравенств очевидно, а второе будет выполняться, если $%2p^2q^2+1>2017$%, то есть $%pq \ge 32$%.

Кроме того, очевидно, нам необходимо выполнение неравенств $%p^3q<2017$% и $%q^3p<2017$%.

Значения $%p=5$% и $%q=7$% подходят.

ссылка

отвечен 6 Авг '17 9:44

@knop, большое спасибо!

(6 Авг '17 17:06) Аллочка Шакед
10|600 символов нужно символов осталось
3

Интуитивное решение. Ищем три множества вида А, В, и все остальные 2015 чисел. Пусть А = 2015 - максимально большое число вида 3к + 2, делящееся на 5. Пусть В = 1008 - половинка от 2015, число вида 5к + 3, делящееся на 3. Тогда выражения вида 2015n + 1008 = 5к +3 и 1008n + 2015 = 3к +2 не являются точными квадратами "по остаткам при делении на 3 и на 5". Произведение 1008*2015 больше, чем 1425^2 и меньше, чем 1426^2 примерно на 2400. Поэтому 1008*2015 + n также не может быть точным квадратом при n < 2018. Полагаю, что решений этой задачи такого вида могут быть десятки и десятки.

ссылка

отвечен 5 Авг '17 11:28

изменен 5 Авг '17 11:34

@kipot_l, опять же, вот это Ваше "примерно на 2400" надо как-то вычислить, а на олимпиаде время безвозвратно уйдёт.

(5 Авг '17 11:51) Аллочка Шакед
2

@Аллочка Шакед: В трудные минуты жизни я вспоминаю, что корень из 2-х равен ~ 1,4142135624.

Мнемоника тут такая - "Я Лида, я дура, но я вот нашла корень из двух!"

Далее: 1008*2015 = 2015000 + 16120 = 2031120 .

Корень из 2,031120 равен ~ 1,4142 + 0,031/2,83 = 1,4142 + 0,011 ~ 1,425 .

1425^2 = 196 + 2*14*1/4 +1/16 = 203 + 0,0625 = 2030625 .

1426^2 = 2030625 + 2851 = 2033476 .

Расстояние от 2031120 до 2033476 = 2356 > 2017 .

Это упражнение заняло у меня минут 10 - 15.

Другое дело, что мне повезло, и я с первого раза полюбил число именно 1008.

Например, число 1002 не годится.

(5 Авг '17 13:30) kipot_l
1

А Ваше решение, Аллочка, я изо всех сил постараюсь "вычислить"!

(5 Авг '17 13:34) kipot_l

@kipot_l, Вы пишете: "А Ваше решение, Аллочка, я изо всех сил постараюсь "вычислить"!" Так мне не публиковать его пока?

(5 Авг '17 16:39) Аллочка Шакед

@Аллочка Шакед, лучше бы не публиковать... приоритет останется за Вами, если что. И я, и Виктор /falcao/ анализировали эту красивую задачу самостоятельно, не проводя поиск в Инете. А сами Вы не искали своё решение в Инете, его там нет? Вдруг мне удастся улучшить своё решение, используя Ваши весьма косвенные подсказки (!)... Что касается меня, то быть "первооткрывателем" в решении сложных олимпиадных задач приходилось только пару раз за всю жизнь. Это греет душу...

(5 Авг '17 18:53) kipot_l
2

@Аллочка Шакед, вот: волшебные подмножества чисел - 1250, 1458 и все остальные 2015 чисел.

1250*1458 = 1350^2.

Жду комплиментов!

Наверное, стоит дополнить решение и помянуть Вас, как организатора и вдохновителя наших побед?

Спасибо за красивую задачу!

(5 Авг '17 19:30) kipot_l
1

Если что, я за публикацию решения.

(5 Авг '17 20:19) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
2

Ну раз @falcao "за", тогда публикую:

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

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

ссылка

отвечен 6 Авг '17 0:11

1

@Аллочка Шакед, стало ещё интереснее. Придётся теперь сравнивать Ваше и моё решение (1250, 1458, ...) с точки зрения их общности и пригодности для различного количества чисел в исходном наборе... При каких количествах чисел будет изменяться решение, нет ли нехороших исключений и т.д. ... Ждём Вашего смешного рассказа.

(6 Авг '17 0:48) kipot_l

@falcao, @kipot_l, Смешной (сквозь слёзы) рассказ: Данная задача нагло скоммунизжена у товарища Сатылханова (жду от него кренделей): http://matol.kz/comments/2918/show Только вот товарищ Сатылханов не потрудился доработать её малость.

(6 Авг '17 1:33) Аллочка Шакед
1

@Аллочка Шакед, Вы из верблюжьих э-э-э... э. конфету "Каракум" слепили. Я-то думал, - пифагоровы тройки, задача Флавия...

Прощаю Вас.

Та-а-к, а нет ли третьего "красивого" решения? Надо посмотреть все "большие" квадраты, начиная типа с 1024...

(6 Авг '17 8:30) kipot_l
1

@Аллочка Шакед, задача Сатылханова имеет следующий вариант решения:

a = 3, c = 5, 3b + 5 и 5b + 3 не являются т.к. ни при каком c.

Наличие вариантов решения надо бы отмечать товарищам казахам.

(6 Авг '17 8:46) kipot_l
2

Ваши два решения очень близки. Фактически берётся пара $%(2a^2,2b^2)$% для которой суммы вида $%2a^2n+b^2$% и $%2b^2n+a^2$% не проходят по каким-нибудь небольшим модулям (3,4,5), а произведение $%ab$% больше чем $%500$%.

Если выписать табличку удвоенных квадратов от 512 и до $%2\cdot31^2=1922$%, то в ней ещё несколько таких пар будут очевидны. Например, можно спарить $%2\cdot25^2$% также $%2\cdot24^2$% или с $%2\cdot21^2$%. Или 1800 c $%2\cdot28^2$%

(6 Авг '17 9:18) knop
2

@Аллочка Шакед: фактически, у Вас та же идея, что у @kipot_l, только проверка чуть более лёгкая. По-моему, тут самое важное -- поверить в какой-то момент, что пример должен строиться из двух отдельных чисел и всего остального. А я смотрел, что происходит с "конфликтными" тройками, и пытался каким-то разумным способом всё разделить на три примерно одинаковые по численности группы. Это у меня не получилось.

(6 Авг '17 10:10) falcao
1

@falcao, мне как-то почти очевидно, что три больших группы почти невероятны. Есть некоторые шансы разделить на 1 группу из 1 элемента и две относительно больших группы.

(6 Авг '17 12:53) knop
1

@knop: сейчас это "задним числом" ясно, но я первоначально пытался брать остатки по какому-то модулю и распределять их на три группы. В таком виде не получалось.

(6 Авг '17 13:19) falcao
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,399
×1,114
×370
×211
×128

задан
3 Авг '17 16:18

показан
877 раз

обновлен
6 Авг '17 17:06

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru