Дано: n человек в компании.
Найти: Доказать, что в любой компании найдутся два человека, имеющие одинаковое число друзей.
Решение:
1. Каждый человек в компании может иметь от 0 до n-1 друзей, где n — общее количество людей.
2. Если один человек имеет 0 друзей, это значит, что он не дружит ни с кем. В этом случае остальные n-1 человек могут иметь от 1 до n-1 друзей.
3. Обозначим количество друзей каждого человека как d_i для i от 1 до n.
4. Если один человек имеет n-1 друзей, это означает, что он дружит со всеми остальными людьми в компании. В этом случае, ни один другой человек не может иметь 0 друзей, так как он дружит с этим человеком.
5. Таким образом, возможные значения d_i (число друзей) могут быть в диапазоне от 0 до n-1, но если один человек имеет 0 друзей, остальные n-1 могут иметь только значения от 1 до n-1.
6. Следовательно, если в компании n человек, то возможные различные значения числа друзей будут:
- 0 (если хотя бы один человек не дружит ни с кем),
- 1, 2, ..., n-1 (если все остальные дружат).
7. У нас 2 возможных сценария:
- Если хотя бы один человек имеет 0 друзей, то оставшиеся n-1 могут иметь значения от 1 до n-1, что дает n-1 различных значений. Однако у нас n человек, что гарантирует, что хотя бы два человека будут иметь одинаковое количество друзей.
- Если ни один человек не имеет 0 друзей, то все n человек имеют от 1 до n-1 друзей. Это также приводит к тому, что два человека будут иметь одинаковое количество друзей, так как имеется только n-1 различных значений.
8. В любом случае, по принципу Дирихле, среди n человек найдутся как минимум два человека с одинаковым числом друзей.
Ответ: Да, в любой компании найдутся два человека, имеющие одинаковое число друзей.