2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Задача на графы (подсчет смежных пар)
Сообщение09.01.2017, 09:41 


08/09/08
40
Пожалуйста, подскажите идею решения следующей задачи:
В первый класс школы зачислены 90 детей. У каждого из них не менее 30 друзей среди остальных первоклассников. Докажите, что всех 90 человек можно так разбить на три класса по 30 человек, чтобы у каждого был хотя бы один друг в его классе.

 Профиль  
                  
 
 Re: Задача на графы (подсчет смежных пар)
Сообщение09.01.2017, 23:11 


08/09/08
40
Кажется, решил.

Рассмотрим дополнительный граф, т.е. граф состоящий из того же множества вершин, в котором вершины смежны тогда и только тогда когда в исходном графе вершины не смежны. Количество подграфов $K_{1,29}$ в дополнительном графе не превосходит величины $90C^{29}_{59}$.
Пусть имеется некоторое разбиение на три класса, фиксированный подграф $K_{1,29}$ "портит" разбиение, если все его вершины содержатся в каком-то одном классе. Если разбиение не испорченно ни одним подграфом, то оно "решает задачу". Таким образом заключаем, что максимальное количество "испорченных" разбиений не превосходит $270C^{29}_{59}$. Всего разбиений на три класса $C^{30}_{90} C^{30}_{60} C_{30}^{30}$. Очевидно, что $C^{30}_{90} C^{30}_{60} C_{30}^{30} > 270C^{29}_{59}$. Значит, нужное разбиение на классы существует.

Не ошибся ли я?

 Профиль  
                  
 
 Re: Задача на графы (подсчет смежных пар)
Сообщение10.01.2017, 15:47 


01/12/11

1047
Так как ограничения на количество друзей только снизу, то считаем, что каждый дружит с каждым, и задача решена.
Для всех остальных случаев надо сначала доказать существование предлагаемых связей.

Можно без ущерба для задачи количество учеников и их дружественные связи уменьшить в 10 раз.

 Профиль  
                  
 
 Re: Задача на графы (подсчет смежных пар)
Сообщение10.01.2017, 17:50 
Заслуженный участник


10/01/16
2315
sasha-parazit
А разве один подграф портит только три разбиения? А не $3\cdot C^{30}_{60}$?

-- 10.01.2017, 19:59 --

Но даже с учетом этого, вроде бы, получится...

 Профиль  
                  
 
 Re: Задача на графы (подсчет смежных пар)
Сообщение14.01.2017, 21:43 


08/09/08
40
Спасибо, DeBill.
Да, действительно, портит $3\cdot C^{30}_{60}$ разбиений. Но, все равно соответствующее неравенство $C^{30}_{90} C^{30}_{60} C_{30}^{30} > 270C^{29}_{59}C^{30}_{60}$ выполняется. Задача решена.

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

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



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

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


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

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