2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Правду ли говорят девочки
Сообщение04.03.2019, 13:58 


29/06/10

53
Москва
На вечеринке было 15 девочек и 12 мальчиков.
Каждого мальчика знают не менее половины девочек.
Три подружки — Таня, Оксана и Полина — похвастались, что вместе они знают всех мальчиков.

Правду ли говорят девочки?
Всегда ли на вечеринке найдутся три девочки, которые вместе знают всех мальчиков?

 Профиль  
                  
 
 Re: Правду ли говорят девочки
Сообщение12.03.2019, 18:08 


06/06/18
9
Хм... Разобьём мальчиков на 2 группы по 6 человек. Мальчиков из первой группы знают только девочки под номерами 1-8, второй группы - 8-15. Такой граф удовлетворяет условию задачи и если Таня, Оксана и Полина из одной группы - то они не знают всех мальчиков. Более того, может существовать группа даже в 7 девочек, которые не знают всех. Может ли больше(13 девочек) - я не знаю пока. Интуитивно - нет.

 Профиль  
                  
 
 Re: Правду ли говорят девочки
Сообщение17.03.2019, 15:02 


29/06/10

53
Москва
JohnnyIpcom
Примеры, когда такие три девочки есть, и когда таких нет, привести не очень трудно.
Ответ на второй вопрос сложнее.

 Профиль  
                  
 
 Re: Правду ли говорят девочки
Сообщение21.03.2019, 14:47 


15/03/11
137
Предположим, что найдётся такое разбиение 15 девочек, что никакие 3 не знают всех мальчиков. Это значит, что любая тройка девочек не знает как минимум одного мальчика.

Всего троек девочек - $\frac{15\cdot14\cdot13}{3\cdot2\cdot1} = 455$

По принципу Дирихле, найдётся мальчик которого не знают $\frac{455}{12}=38$ троек девочек. Эти 38 троек образуют группу из не менее 8 девочек (Так как группа из семи девочек составляет $\frac{7\cdot6\cdot5}{3\cdot2\cdot1} = 35$ троек).

Получается, что одного мальчика не знает как минимум 8 девочек, а значит его знает меньше половины девочек. А это противоречит условию.

Значит Всегда найдутся три девочки, которые вместе знают всех мальчиков

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

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



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

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


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

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