Задача
а) В группе из четырёх человек, говорящих на разных языках, любые трое могут общаться (возможно, один переводит двум другим).
Доказать, что их можно разбить на пары, в каждой из которых имеется общий язык.
б) То же для группы из 100 человек.
в) То же для группы из 102 человек.
Решение
а) Рассмотрим граф с четырьмя вершинами A, B, C, D, соответствующими людям, и соединим ребрами людей, знающих общий язык. Условие означает, что каждая тройка вершин соединена хотя бы двумя рёбрами. А доказать нужно, что есть два ребра без общих вершин. Пусть это неверно.
Первый способ. Если в тройке (A, B, C) проведены рёбра AB и AC, то рёбер BD и CD нет. Но тогда в тройке (B, C, D) не больше одного ребра. Противоречие.
Второй способ. Всего есть 4 тройки. Каждое ребро входит в две тройки. Следовательно, рёбер не менее 4·2 : 2 = 4. С другой стороны, каждому ребру соответствует отсутствующее "противоположное" ребро. Следовательно, рёбер не более трёх. Противоречие. в) Отделим двух человек, говорящих на одном языке, а остальных разобьём на четвёрки. Согласно а) каждую четвёрку можно разбить на две пары с общим языком.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь