Решение желательно в течении 10 минут Про компанию из 19 человек известно, что какую бы тройку людей мы ни
взяли, в ней всегда найдутся двое знакомых. Человек считается общительным, если он знает хотя бы 9 человек. Докажите, что в этой компании хотя
бы 10 общительных человек.
Чтобы решить эту задачу, давайте разберемся с ее условием.
У нас есть компания из 19 человек. Отметим, что в любой тройке из этих людей найдутся двое знакомых.
Из этого условия можно сделать вывод, что у каждого человека в компании должно быть не менее двух знакомых. Если в какой-то тройке все трое человека уже знакомы друг с другом, то дополнительные знакомства уже не требуются. А если в тройке только двое знакомы друг с другом, то третий человек может быть знаком с любым из двоих первых. Таким образом, в любой тройке найдутся двое знакомых.
Из этого можно вывести следующее: если у кого-то в компании только два знакомых, то он обязательно знаком со всеми остальными людьми в компании. Представим, что в нашей компании есть человек, у которого меньше чем 9 знакомых (будем называть его "А").
Тогда "А" знаком с каждым из остальных 18 человек, и эти 18 человек знают друг друга. Но в тройке из любых трех человек есть двое знакомых, поэтому "А" должен быть знаком со всеми людьми, которых он прежде не знал. Из этого следует, что у "А" не может быть 2 знакомых.
Таким образом, мы доказали, что в компании из 19 человек должно быть хотя бы 10 общительных человек – тех, кто знает хотя бы 9 остальных людей.
Пожалуйста, если у вас есть дополнительные вопросы или что-то не понятно, не стесняйтесь задавать!