Question

докажите, что среди любых 9 человек найдутся трое, знакомых друг с другом, либо найдутся 4 человека, не знакомых друг с другом.

Answer 1

Знакомых-3 из 9:= 9-3=6; 6:9= 0,6%. Что они знакомы. И по такой же схеме следующее

Answer 2

Для доказательства данного утверждения воспользуемся принципом Дирихле (или принципом ящиков).

Предположим, что у нас есть 9 человек. Рассмотрим одного из них. Этот человек знаком с 8 остальными, так как в группе всего 9 человек. Теперь рассмотрим двух человек, которых он знает (допустим, это А и В).

1. Если А и В знакомы друг с другом, то у нас получается тройка людей (исходный человек, А и В), которые все знакомы друг с другом.

2. Если А и В не знакомы друг с другом, то каждый из них знаком с 7 остальными людьми из группы, так как изначально было 9 человек, и мы уже рассмотрели 3 человека. Теперь рассмотрим третьего человека, который тоже знаком с 7 людьми из оставшихся 6. Если он знаком с одним из А или В, то у нас снова образуется тройка людей, которые все знакомы друг с другом. Если он не знаком с А и В, то у нас образуется четверка людей (исходный человек, А, В и третий человек), которые все не знакомы друг с другом.

Таким образом, в любой группе из 9 человек найдутся либо трое, знакомых друг с другом, либо 4 человека, не знакомых друг с другом. Это доказывает наше утверждение.