2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 задача по комбинаторике и теории множеств
Сообщение28.02.2020, 10:48 
Аватара пользователя


19/06/14
78
Уважаемые участники,

столкнуся с такой задачей.

На международной олимпиаде встретились 2018 участников.
Организаторы заметили, что:
1) среди любых трёх участников есть двое говорящих на одном языке
2) каждый с участников говорит максимально на пяти языках.
Доказать, что среди участников можно найти группу по крайней мере 203 человек,
которые говорят на одном языке.

Число сочетаний из 2018 по 3:
$C_{2018}^{3}=\frac{2018!}{3!2015!}=1367622816$, только я не уверен что это понадобится. Думаю, надо предположить что участники говорят на 5 языках, т.е. рассмотреть пять множеств и что-то делать с их пересечениями.
Буду признателен за подсказки!

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


02/05/19
396
Если бы каждый владел только одним языком, то можно было бы рассуждать просто: возьмём любых трёх участников $a$, $b$ и $c$, из них какие-то два — пусть $a$ и $b$ говорят на одном языке. Затем рассмотрим произвольного третьего участника $d$. Он либо говорит на одном языке с $a$ и $b$, либо на одном языке с $c$. Эту процедуру можно повторять многократно, увеличивая одну из двух групп.
Остаётся преодолеть сложность, связанную с многоязычием участников...

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


14/02/20
863
Предположим, что есть два участника А и Б, которые не говорят на одном языке. Будем подстраивать им в тройку каждого остального человека. Каждый оставшийся будет говорить на одном языке либо с А, либо с Б, при этом А и Б говорят максимум на 5 языках каждый. В итоге получается, что в худшем случае (А и Б говорят на 5 несовпадающих языках каждый, итого 10 языков), остальные участники говорят каждый на одном из этих 10 языков.

Опять же, в худшем случае эти языки распределены поровну 2016/10=201,6, но так быть не может, значит на одном из языков говорит по крайней мере 202 человека из оставшихся. А если добавить к ним либо А, либо Б, который говорит на этом языке, получится ровно 203.

Предположим далее, что нет таких двух участников А и Б, набор языков которых не совпадает. Значит, уже любая пара людей понимает друг друга. Значит, произвольного человека А поймет каждый из участников, а ведь А владеет в худшем случае 5 языками. Короче, в таком случае, людей, владеющих одним языком, будет намного больше, чем 203 :)

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

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



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

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


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

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