Задача 11.5

Відповідь: Задача не має числової відповіді

Перелік задач

Відповідь: Задача не має числової відповіді

Рішення:
Розглянемо дводольний граф, первую долю якого складають дівчата (13 вершин), а другу – пари хлопчиків (21 вершина).

Будемо з’єднувати вершини ребром, якщо відповідна дівчинка познайомилася із відповідною парою хлопчиків в одному місяці.

Зазначимо, що із кожної вершини першої долі виходить не менше п’яти ребер. Дійсно, нехай деяка дівчинка познайомилася із a, b і c хлопчиками у першому, другому і третьому місяці відповідно (очевидно, що a + b + c = 7).

Тоді відповідна вершина графу поєднана із

ребрами (ми скористалися нерівністю між середнім арифметичним і середнім квадратичним для трьох чисел).

Таким чином, у графі загалом проведено не менше 13 * 5 = 65 ребер. За принципом Діріхле знайдеться вершина з другої долі, із якої виходить не менше чотирьох ребер. Це означає, що знайшлася така пара хлопчиків і такі чотири дівчинки, що кожна із дівчаток познайомилася із обома хлопчиками в одному місяці. Але оскільки місяців три, то для якихось двох дівчаток це сталося в одному місяці.