Question

в компании N человек и докажите что есть два человека у которых одинаковое количество знакомых в этой компании

Answer 1

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

Answer 2

Это классическая задача из теории графов, которая известна как "теорема о дружбе". Для доказательства этого утверждения, мы можем использовать принцип ящиков Дирихле (или принцип Дирихле). Этот принцип гласит, что если N + 1 или более объектов распределены по N ящикам, то в одном из ящиков обязательно окажется хотя бы два объекта.

Давайте представим, что каждый человек в компании представляет собой "ящик", и количество знакомых у каждого человека будет являться "объектами". Если бы у каждого человека в компании было уникальное количество знакомых, это бы означало, что каждый человек в компании представлял бы собой разный "ящик" с уникальным количеством "объектов" (знакомых).

Теперь, если общее количество людей в компании N превышает количество возможных уникальных количеств знакомых, т.е. N + 1 или более, принцип Дирихле гарантирует, что какой-то из "ящиков" (человек) содержит хотя бы два "объекта" (людей) с одинаковым количеством знакомых.

Таким образом, у нас есть два человека в компании с одинаковым количеством знакомых.