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 пар знакомых.

Answer 2

Это задача о графе знакомств, и для её решения можно воспользоваться принципом Дирихле, также известным как принцип ящиков и шаров. По сути, принцип Дирихле утверждает, что если n объектов размещены в m контейнерах, и n > m, то как минимум в одном из контейнеров будет больше одного объекта.

В данной задаче:

- Есть 25 человек (школьников). - Любые двое из них имеют общего знакомого.

Мы можем рассматривать каждого школьника как вершину в графе, а знакомство между школьниками как ребро между соответствующими вершинами. Условие задачи гарантирует, что в графе нет изолированных вершин (каждый имеет хотя бы одного знакомого).

Теперь мы хотим выбрать пару знакомых школьников. Мы можем это сделать следующим образом: выберем одного из 25 школьников (25 способов), а затем выберем его знакомого из его соседей (у него, как минимум, один сосед). Поскольку у каждого школьника есть хотя бы один знакомый, то у нас всегда есть способ выбрать пару знакомых школьников.

Таким образом, можно выбрать пару знакомых школьников не менее, чем 25 способами (по количеству школьников). В этом смысле задача решена.

Тем не менее, если вы хотите доказать, что есть не менее 36 способов выбрать пару знакомых школьников, то это также верно. Выбор каждого школьника даст вам одну пару знакомых, но также вы можете выбрать другой школьник, который имеет общего знакомого с предыдущим (поскольку "любые двое имеют общего знакомого"). Это будет дополнительными парами знакомых. И так далее, пока вы не выберете 36 пар знакомых.