Question

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

Answer 1

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