Вгруппе 100 человек и каждый член этой группы знаком с 67 людьми из этой группы(если x знаком с y, то и y знаком с x). докажите, что найдутся 4 человека в группе знающие друг друга.
Рассмотрим любого человека, назовём его А, он с кем-то знаком, его назовём Б, вместе А и Б знают хотя бы 66+66=132 человека. за исключением друг друга, но людей в группе, не считая А и Б, всего 98, значит есть хотя бы 34 человека, которые знакомы одновременно и с А, и с Б. Выберем любого из них, назовём его С, людей, которые знаю и А, и Б хотя бы 34, значит тех, кто не знает хотя бы одного из них не больше 66, у С есть 67 знакомых, значит хотя бы один из них знает и А, и Б, назовём его Д. Нетрудно убедиться, что в группе АБСД все знают всех.
Рассмотрим любого человека, назовём его А, он с кем-то знаком, его назовём Б, вместе А и Б знают хотя бы 66+66=132 человека. за исключением друг друга, но людей в группе, не считая А и Б, всего 98, значит есть хотя бы 34 человека, которые знакомы одновременно и с А, и с Б. Выберем любого из них, назовём его С, людей, которые знаю и А, и Б хотя бы 34, значит тех, кто не знает хотя бы одного из них не больше 66, у С есть 67 знакомых, значит хотя бы один из них знает и А, и Б, назовём его Д. Нетрудно убедиться, что в группе АБСД все знают всех.