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