2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Заманчивое подмножество
Сообщение27.04.2012, 19:31 
Аватара пользователя


01/12/11

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

 Профиль  
                  
 
 Re: Заманчивое подмножество
Сообщение27.04.2012, 21:24 
Заслуженный участник


18/01/12
933
Ответ: 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).

 Профиль  
                  
 
 Re: Заманчивое подмножество
Сообщение27.04.2012, 21:30 
Аватара пользователя


01/12/11

8634
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 числами. Йа кретинко?

 Профиль  
                  
 
 Re: Заманчивое подмножество
Сообщение28.04.2012, 03:48 
Заслуженный участник


18/01/12
933
Ktina в сообщении #564694 писал(а):
Меня не покидает ощущение, что этот пример — единственный.

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

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

Изображение


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

 Профиль  
                  
 
 Re: Заманчивое подмножество
Сообщение28.04.2012, 12:04 
Заблокирован


16/06/09

1547

(Оффтоп)

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

(Оффтоп)

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

 Профиль  
                  
 
 Re: Заманчивое подмножество
Сообщение28.04.2012, 12:22 
Аватара пользователя


01/12/11

8634
hippie в сообщении #564773 писал(а):
Ktina в сообщении #564694 писал(а):
Меня не покидает ощущение, что этот пример — единственный.

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

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


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group