В конкурсе «Мисс мира» участвуют 100 девушек. Известно, что среди любых 12 из них найдутся двое, которые знакомы между собой. Докажите, что как бы ни раздали участницам номера (не…
В конкурсе «Мисс мира» участвуют 100 девушек. Известно, что среди любых 12 из них найдутся двое, которые знакомы между собой. Докажите, что как бы ни раздали участницам номера (не обязательно от 1 до 100), найдутся две знакомые девушки, номера которых начинаются с одинаковой цифры.
Давайте разберем задачу по шагам и попробуем понять, как ее решить.
Условие:
- В конкурсе участвуют 100 девушек. Обозначим их участников как множество \( V \), где \( |V| = 100 \).
- Известно, что среди любых 12 девушек найдутся двое, которые знакомы (то есть есть ребро между ними в некоем графе знакомств).
- Нужно доказать, что независимо от того, как участницы получили номера, существует пара знакомых девушек, номера которых начинаются с одной и той же цифры.
Шаг 1. Интерпретация условий
Пусть у нас есть граф \( G = (V, E) \), где вершины — девушки, а ребра — знакомства между ними.
Условие: В любой подграф из 12 вершин есть хотя бы одно ребро. Или, другими словами:
В графе \( G \), любой набор из 12 вершин содержит хотя бы одно ребро.
Это означает, что:
Граф не содержит независимых множеств из 12 вершин. (то есть, в любой группе из 12 вершин есть хотя бы одно ребро).
Шаг 2. Связь с понятием «независимое множество»
В теории графов важное понятие — независимое множество — это множество вершин, между которыми нет ребер.
Значит, из условия следует:
Максимальное размер независимого множества в графе \( G \) — это не более 11 вершин.
Потому что, если бы было независимое множество из 12 вершин, это бы противоречило условию.
Например:
\[ \alpha(G) \leq 11 \]
где \( \alpha(G) \) — размер максимального независимого множества.
Шаг 3. Связь с темой о номерах и цифрах
Задача говорит о раздаче номеров, в которых есть цифры от 0 до 9.
Требуется доказать: найдутся две знакомые девушки, номера которых начинаются с одинаковой цифры.
Это сводится к следующему:
- Есть всего 10 возможных первых цифр номера: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
- Девушек 100, номера можно предположить, что они могут начинаться с любой цифры.
Шаг 4. Использование понятий о распределении
Итак, наша задача: показать, что среди девушек, начинающихся с одной цифры, обязательно найдутся две, которые знакомы, то есть между ними есть ребро.
Шаг 5. Попытка построения противоположного варианта
Подумаем от противного:
Предположим, что нет, таких двух знакомых девушек, номера которых начинаются с одинаковой цифры.
Что это означает?
- Для каждой цифры (от 0 до 9) — максимум одна девушка, которая с ней связана знакомством с другой девушкой, начинающейся с той же цифры.
- Если бы имелось больше, чем одна девушка с одинаковой цифрой, и между ними не было бы знакомства, это было бы противоречием.
Но поскольку 100 девушек, а всего 10 цифр, то по принципу «з fiziсш » (переходящему в сжатую логическую раздачу через теорию множеств):
- Более того, если предположить, что в каждой группе с одинаковой первой цифрой нет знакомых между ними, то все знакомства между девушками, номерами которых начинаются с одинаковых цифр, отсутствуют.
Шаг 6. Распределение девушек по цифрам и свойства графа
Разделим девушек по первой цифре их номера:
- Пусть \( A_i \) — множество девушек, номера которых начинаются с цифры \( i \).
Общее число девушек:
\[ |A_0| + |A_1| + \dots + |A_9| = 100 \]
Поскольку мы предполагаем, что нет двух знакомых девушек, начинающихся с одинаковой цифры, то:
- В каждой группе \( A_i \), не может быть двух девушек, которые знакомы, потому что тогда они будут сведением к тому, что среди них есть знакомство, а кто-то из них, вероятно, более того, могут быть в одной группе.
Но это противоречит тому, что в графе не должно существовать ребра между двумя девушками с одинаковой первой цифрой.
Шаг 7. Вывод из тактики по количеству групп
Поскольку в каждой группе \( A_i \):
- есть либо одна девушка, либо никто,
- и среди них не должно быть знакомых (ребер),
то при этом:
- В каждой группе выше одного по количеству девушки, обязательно должно быть не менее двух (чтобы подтвердить знакомство, и чтобы сразу исключить это противоречие).
Но если в каждой группе хотя бы по одной девушке, то:
\[ \sum_{i=0}^9 |A_i| = 100 \]
Следовательно:
- По принципу «Расселла» или «принципа пулемета», одна из групп содержит не менее чем \(\lceil \frac{100}{10} \rceil = 10\) девушек.
Итоговая идея
Исходим из ситуации, что между любыми двумя девушками из одной группы есть знакомство, иначе выполнение задания не возможна.
А если так, то:
- Вариант ухудшается в случае максимально возможного количества групп с меньшей численностью, но ведь у них должно быть много групп, (не более 10), — только тогда между двумя девушками с одинаковой первой цифрой обязательно есть знакомство.
Ключевое утверждение
Если в каждой группе \(A_i\):
- среднее число девушек ≥ 10 (так как всего 100 девушек и 10 групп),
- то в одной из групп обязательно должно быть более одной девушки, и, судя по условию, между каждой парой из них — есть знакомство.
И, значит, найдутся две девушки с одинаковой первой цифрой номера, которые знакомы.
Общий вывод
Если бы не было таких двух знакомых девушек с одинаковой первой цифрой, это означало бы, что в каждой группе максимум одна девушка, и, в таком случае, у нас было бы не более 10 девушек с разными первыми цифрами.
Но мы имеем 100 девушек, следовательно, по принципу «порции распределения», обязательно найдется хотя бы одна цифра, под которую попадает не менее 10 девушек, и, по условию, среди этих 10 девушек — 2 или более — знакомы.
То есть, доказано, что обязательно существуют две знакомые девушки, номера которых начинаются с одинаковой цифры.
Итог:
По условию, а также по принципу распределения, среди девушек с одинаковой первой цифрой обязательно найдутся две знакомые.
Если нужно, могу подготовить более формальную формулировку или пояснение!
