Question

В компании, состоящей из 2n+1 человека, для любого n человек требуется один человек, знакомый с каждым из них.Докажите, что в этой компании есть человек, который знает все​

Answer 1

Ответ:

Очевидно, что есть двое знакомых, и если есть k попарно знакомых (где   k ≤ n),  то по условию найдётся отличный от них человек, знакомый со всеми этими k людьми. Отсюда следует, что найдутся  n + 1  попарно знакомых: A1, ..., An+1. Рассмотрим остальных n человек. По условию существует отличный от них человек Ai, знающий их всех. Но тогда Ai знаком со всеми.

Answer 2

Задача

В данной задаче требуется доказать, что в компании, состоящей из 2n+1 человека, найдется человек, который знает всех остальных.

Доказательство

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

Рассмотрим два случая:

Случай 1: Предположим, что среди 2n+1 человека есть человек, который знаком с большинством людей в компании. Пусть этот человек знаком с k человеками, где k > n. Тогда остается n+1 человек, которые не знакомы с этим человеком. Но по условию задачи, для каждого из этих n+1 человека требуется другой человек, знакомый с ним. Это противоречит тому, что у нас осталось только n человек. Следовательно, в этом случае нашелся человек, который знает всех остальных.

Случай 2: Предположим, что среди 2n+1 человека нет такого человека, который знаком с большинством людей в компании. Тогда каждый человек знаком с не более чем n людьми. Рассмотрим одного из этих людей. У него есть n+1 знакомых, но по условию задачи, для каждого из этих n+1 человека требуется другой человек, знакомый с ним. Это противоречит тому, что у нас осталось только n человек. Следовательно, и в этом случае нашелся человек, который знает всех остальных.

Таким образом, в любом случае в компании, состоящей из 2n+1 человека, найдется человек, который знает всех остальных.

Примечание

Доказательство данной задачи основано на логическом рассуждении и не требует использования внешних источников.