Сумма, делящая произведение

[Xenia1996]

а) Доказать, что можно построить сколь угодно большое конечное множество $S$ натуральных чисел так, чтобы для любых двух различных элементов $a, b \in S$ выполнялось $(a+b)|ab$.
б) Доказать, что не существует такого бесконечного множества.

[nnosipov]

Пункт б) тривиален. Пункт а) напомнил такую задачу: существуют ли 1998 различных натуральных чисел, произведение любых двух из которых делится на квадрат их разности. (Ответ: да.)

[Xenia1996]

nnosipov в сообщении #452255 писал(а):

Пункт а) напомнил такую задачу...

Эту?
Или эту

[nnosipov]

Xenia1996 в сообщении #452256 писал(а):

nnosipov в сообщении #452255 писал(а):

Пункт а) напомнил такую задачу...

Эту?
Или эту

Но это финал Всероссийской 1998 года, 11 класс. Интересно, кто у кого эту задачу позаимствовал.

[Xenia1996]

nnosipov в сообщении #452259 писал(а):

Но это финал Всероссийской 1998 года, 11 класс. Интересно, кто у кого эту задачу позаимствовал.

Скажем так, сегодняшнюю задачу я решила иначе, чем тогдашнюю (это - первая подсказка).

[nnosipov]

Всё, вспомнил. Эта задача с Турнира городов, сезон 1988/1989. Решается просто.

[Xenia1996]

nnosipov в сообщении #452266 писал(а):

Всё, вспомнил. Эта задача с Турнира городов, сезон 1988/1989. Решается просто.

Только моё решение кардинально разнится с их.

(Оффтоп)

У нас прям-таки анекдотичная ситуация возникла.

Цитата:

В одной компании все возможные анекдоты уже по нескольку раз перетравили и помнили их наизусть. И вот решили пронумеровать и называть только номер.

- 98.
- Ха-ха-ха!
- 14.
- Хахаха!
- 17.
- Что Вы, при дамах???

[nnosipov]

Не знаю как у них, а у меня возникло произведение всех сумм $i+j$, и всё получилось. А у Вас?

[Xenia1996]

nnosipov в сообщении #452272 писал(а):

Не знаю как у них, а у меня возникло произведение всех сумм $i+j$, и всё получилось. А у Вас?

Нужное множество из двух чисел построить просто. Пусть наши числа будут $x$ и $2x$. Тогда $3x|2x^2$, поэтому достаточно взять любое число, делящееся на 3. Скажем, множество $\{3, 6\}$ сгодится.
Теперь - из трёх. Пусть наши числа будут $x$, $2x$ и $4x$. Тогда $3x|2x^2$, а $5x|4x^2$. Стало быть, мы можем взять самое маленькое число 15, а остальные будут 30 и 60.

Теперь из $n$.
Рассмотрим последовательность $3, 5, 9, 17, \dots, 2^n+1$. Пусть $S_n$ - произведение первых $n$ членов этой последовательности.
Тогда множество $\{S_n, 2S_n, 4S_n, 8S_n, \dots, 2^{n-1}S_n\}$ и будет нашим множеством.
А если каждый из его элементов удвоить, то в пункте а) можно убрать слово "различных".

[nnosipov]

Тоже здорово. Приятно, когда есть много решений.

[Xenia1996]

Это я сильно скомкала, потому что торопилась. Сейчас подробнее всё выложу, с доказательствами.

[nnosipov]

Xenia1996 в сообщении #452282 писал(а):

Это я сильно скомкала, потому что торопилась. Сейчас подробнее всё выложу, с доказательствами.

По-моему, всё очевидно. Лучше придумайте ещё какую-нибудь разумную задачу, которую можно было бы решить ... эээ, тремя способами.

[Xenia1996]

Так вот, во множестве $\{S_n, 2S_n, 4S_n, 8S_n, \dots, 2^{n-1}S_n\}$ отношение любых двух различных элементов будет степенью двойки, не превышающей $2^{n-1}$. Пусть это будут числа $x$ и $2^mx$. Тогда должно выполняться $((2^m+1)x)|(2^mx^2)$.
А поскольку все числа в этом множестве делятся на $2^m+1$ при $m<n$, условие будет выполняться.
Условие будет выполняться и для множества $\{2S_n, 4S_n, 8S_n, 16S_n, \dots, 2^{n}S_n\}$, плюс ещё то, что любое число с себя самоё можно отъекатеринить. Ведь для $2x|x^2$ достаточно, чтобы число было чётным.

Я права?
Или непонятно написала?
Или ошиблась?

[nnosipov]

Понятно, но на запрос "любое число с себя самоё можно отъекатеринить" гугл выдал "Не найдено ни одного документа".

[Xenia1996]

nnosipov в сообщении #452294 писал(а):

Понятно, но на запрос "любое число с себя самоё можно отъекатеринить" гугл выдал "Не найдено ни одного документа".

Для любого элемента $a$ множества $\{2S_n, 4S_n, 8S_n, 16S_n, \dots, 2^{n}S_n\}$ выполняется $(a+a)|(a\cdot a)$. Так лучше?