В поиске неравномощных множеств

[Ktina]

Пусть $M$ - подмножество множества $\{1, 2, \dots , n\}$ с наибольшим возможным числом элементов такое, что для любых $x<y<z\in\ M$ число $z$ не делится нацело на $x+y$

Пусть $N$ - подмножество множества $\{1, 2, \dots , n\}$ с наибольшим возможным числом элементов такое, что для любых $x<y<z\in\ N$ выполняется $x+y\ne z$

Существует ли такое натуральное $n>3$, при котором $M$ неравномощно $N$?

[hippie]

Ответ: Нет. $\text{card}(M) = \text{card}(N) = [\frac{n}{2}]+1.$

Поскольку множество $M$ удовлетворяет и второму условию, то $\text{card}(M)\le\text{card}(N)$ (иначе в качестве множества $N$ можно взять $M$).

Пусть $N=\{a_1, a_2, \dots, a_k\}$ (числа упорядочены по возрастанию).
Тогда множества $N’=\{a_1, a_2, \dots, a_{k-1}\}$ и $N''=\{a_k-a_1, a_k-a_2, \dots, a_k-a_{k-1}\}$ пересекаются не более, чем по одному элементу ($\frac{a_k}2$). Таким образом $N\cup N'' = N’\cup N'' \cup\{a_k\}$ содержит не менее $2(k-1)$ элементов. В то же время $N\cup N'' \subset \{1, 2, \dots, n\}$. Следовательно $2(k-1)\le n.$
Таким образом $\text{card}(N)=k\le [\frac{n}{2}]+1$.

Множество $\{[\frac{n+1}{2}], [\frac{n+3}{2}], \dots, n\}$ удовлетворяет обоим условиям и содержит $[\frac{n}{2}]+1$ элементов.

Следовательно $[\frac{n}{2}]+1\le\text{card}(M)\le\text{card}(N)\le [\frac{n}{2}]+1.$