2014 dxdy logo

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

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





Начать новую тему Ответить на тему
 
 Дружный класс
Сообщение14.11.2017, 11:28 
Аватара пользователя


01/12/11
5911
В классе 25 человек. Известно, что среди любых трех из них есть двое друзей. Может ли оказаться так, что у каждого из учеников -
не более 12 друзей?

 Профиль  
                  
 
 Re: Дружный класс
Сообщение14.11.2017, 12:31 


15/03/11
132
Разделим класс на две группы. В первой 13 человек. Во второй - 12.

В первой и второй группе каждый дружит с каждым. При этом ученики из разных групп не дружат.

Все условия выполняются.

 Профиль  
                  
 
 Re: Дружный класс
Сообщение14.11.2017, 16:34 
Аватара пользователя


01/12/11
5911
zhekas
Большое спасибо!
Можно даже менее абстрактно - не просто на две группы по 12 и 13, а представить, что в классе 12 мальчиков и 13 девочек. Все мальчики дружат друг с другом и не дружат с девочками, а все девочки дружат друг с дружкой и не дружат с мальчиками. Так и задумывалась задача.
А вот не более 11 друзей у каждого быть, кстати, не может. Знаете, почему?

 Профиль  
                  
 
 Re: Дружный класс
Сообщение14.11.2017, 17:55 


15/03/11
132
Ktina в сообщении #1265257 писал(а):
zhekas
А вот не более 11 друзей у каждого быть, кстати, не может. Знаете, почему?


Возьмём одного ученика - $a$. Он дружит максимум с 11 учениками (множество $A$). Из оставшихся 13-и выберем ещё одного $b$. Он тоже дружит максимум с одинадцатью учениками (множество $B$). Объединение $a \cup A \cup b \cup B $ даёт максимум $1+11+1+11=24$ ученика. Таким образом остаётся как минимум один ученик $c$, который не дружит ни с $a$ ни с $b$. Тройка $a,b,c$ не удовлетворяет условию задачи.

 Профиль  
                  
 
 Re: Дружный класс
Сообщение14.11.2017, 18:08 
Заслуженный участник
Аватара пользователя


09/09/14
4407
zhekas в сообщении #1265287 писал(а):
Из оставшихся 13-и выберем ещё одного $b$. Он тоже дружит максимум с одинадцатью $B$. Объединение $a \cup A \cup b \cup B $ даёт максимум $1+11+1+11=24$ ученика.
Почему $A$ и $B$ не пересекаются? Теперь ведь нет оснований считать, что в $A$ каждый дружит с каждым.

 Профиль  
                  
 
 Re: Дружный класс
Сообщение14.11.2017, 18:14 


15/03/11
132
grizzly в сообщении #1265289 писал(а):
Почему $A$ и $B$ не пересекаются? Теперь ведь нет оснований считать, что в $A$ каждый дружит с каждым.


А кто сказал, что $A$ и $B$ не пересекаются? Они вполне могут пересекаться. Но если они пересекаются, то объединение даёт меньше 24 учеников. И, следовательно, на роль $c$ у нас остаётся выбор из большего количества учеников.

 Профиль  
                  
 
 Re: Дружный класс
Сообщение14.11.2017, 18:16 
Заслуженный участник
Аватара пользователя


09/09/14
4407
zhekas
Да, точно.

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

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



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

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


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

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