В
Все
Б
Биология
Б
Беларуская мова
У
Українська мова
А
Алгебра
Р
Русский язык
О
ОБЖ
И
История
Ф
Физика
Қ
Қазақ тiлi
О
Окружающий мир
Э
Экономика
Н
Немецкий язык
Х
Химия
П
Право
П
Психология
Д
Другие предметы
Л
Литература
Г
География
Ф
Французский язык
М
Математика
М
Музыка
А
Английский язык
М
МХК
У
Українська література
И
Информатика
О
Обществознание
Г
Геометрия
liliya15nafikova
liliya15nafikova
24.03.2022 19:11 •  Алгебра

Вгруппе из 25 человек любые двое имеют общего знакомого. докажите, что из этой группы можно не менее, чем выбрать пару знакомых школьников. 60

Показать ответ
Ответ:
Balanshiki
Balanshiki
09.10.2020 06:18

Понятно, что нужно доказать для минимального числа попарных знакомств, ибо если все друг с другом знакомы, то число искомых пар будет очень велико. Минимум знакомств будет, если 24 человека знакомы  только с 25-м. Тогда любая пара из 24 будет иметь общего знакомого - 25-го. Итого здесь получается 24 пары знакомых - 1-й и 25-й, 2-й и 25-й 24-й и 25-й. Возникает одна проблема - 25-й ни с кем не имеет общего знакомого. Тогда  самое простое - попарно перезнакомить всех из 24-х. 1-го со 2-м, 3-го с 4-м 23-го с 24-м. Таких знакомств будет еще 12. И проблема 25-го решена. У него и любого из 24-х появился общий знакомый. Итого получилось минимум 36 пар знакомых.

0,0(0 оценок)
Популярные вопросы: Алгебра
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota Оформи подписку
logo
Начни делиться знаниями
Вход Регистрация
Что ты хочешь узнать?
Спроси ai-бота