2014-06-08
В обществе, состоящем из 1982 человек, среди любых четырех человек можно выбрать по крайней мере одного, знакомого с остальными тремя. Каково минимально возможное количество людей, которые знакомы со всеми?
Решение:
Если незнакомых людей нет, то количество людей, которые знакомы со всеми, равно 1982. Пусть Л и В не знакомы друг с другом. Тогда все остальные люди между собой знакомы (если С не знаком с D, то в группе A, В, С, D никто не знаком с остальными тремя). Если А и В знакомы со всеми остальными, то 1980 человек знакомы со всеми. Если же А не знаком также и с С, где $C \neq B$, то и А, и В, и С знакомы со всеми остальными 1979 людьми (так как в любой группе A, В, С, D только D может быть знакомым с остальными тремя), которые к тому же знакомы между собой. Таким образом, минимальное количество людей, знакомых со всеми, равно 1979.