Заманчивое подмножество

[Ktina]

Назовём подмножество $P$ множества $S=\{0, 1, 2, 3, \dots ,29\}$ заманчивым, если для любых целых (не обязательно натуральных) $n$ и $m$ и любых двух (не обязательно различных) элементов $a, b\in P$ выполняется $a+b+30n\ne m^2+m$.
Какой наибольшей мощностью может обладать заманчивое подмножество?

[hippie]

Ответ: 10.

Пример множества: {2, 5, 8, 11, 14, 17, 20, 23, 26, 29}.

Минимальность:
В множество не могут входить числа: 0, 1, 3, 6, 10, 13, 15, 16, 18, 21, 25, 28;
а также входит не более чем по одному числу из пар: (2; 4), (7; 19), (8; 12), (9; 11), (14; 22), (17; 19), (23, 27), (24; 26).

[Ktina]

hippie в сообщении #564687 писал(а):

Ответ: 10.

Пример множества: {2, 5, 8, 11, 14, 17, 20, 23, 26, 29}.

Меня не покидает ощущение, что этот пример - единственный. У меня получился этот же пример. Видимо, сие связано с остатками по модулю 3.

-- 27.04.2012, 20:38 --

hippie в сообщении #564687 писал(а):

Минимальность:
В множество не могут входить числа: 0, 1, 3, 6, 10, 13, 15, 16, 18, 21, 25, 28;
а также входит не более чем по одному числу из пар: (2; 4), (7; 19), (8; 12), (9; 11), (14; 22), (17; 19), (23, 27), (24; 26).

На пары я несколько раз разбивала, потому что не сразу дошло, что можно 10 чисел в это множество поместить.
Вот какие были разбиения:

(2, 4), (5, 7), (9, 17), (12, 14), (19, 23), (20, 22), (24, 26), (27, 29);

(2, 24), (4, 8), (5, 7), (9, 11), (12, 14), (17, 19), (20, 22), (23, 27)
и ещё несколько из той же оперы.

И лишь потом сообразила, что там нечётное количество нечётных чисел, поэтому на 9 пар не разобьёшь. Тогда пришлось найти пример с 10 числами. Йа кретинко?

[hippie]

Ktina в сообщении #564694 писал(а):

Меня не покидает ощущение, что этот пример — единственный.

Правильное ощущение .

Перебор удобно делать с помощью картинки (здесь отрезками соединены пары чисел, которые не могут одновременно попасть в Множество)

4 выбивает не менее 5 чисел (2; 8; 22; 26 и хотя бы одно из чисел пары (12; 14)). Следовательно, 4 не может входить в Максимальное Множество.
12 или 24 выбивает 4 числа, отличных от 4. Следовательно, с учётом ранее выброшенной четвёрки, ни 12 ни 24 не могут входить в Максимальное Множество.
Из оставшегося шестиэлементного множества 22 выбивает 3 элемента. И, следовательно, также не входит в Максимальное Множество.
Таким образом из чётных чисел можно выбрать только одно пятиэлементное подмножество, удовлетворяющее условию. Аналогично — из нечётных.

[temp03]

(Оффтоп)

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

(Оффтоп)

Кстати, для меня самое сексуальное - это подмножество ЗУ женских участниц форума

[Ktina]

hippie в сообщении #564773 писал(а):

Ktina в сообщении #564694 писал(а):

Меня не покидает ощущение, что этот пример — единственный.

Правильное ощущение .

Перебор удобно делать с помощью картинки (здесь отрезками соединены пары чисел, которые не могут одновременно попасть в Множество)

Вот это красотень! Огромное спасибо за чудесный и грамотный разбор!