Царь зверей Лев объявил турнир по игре в волейбол. Набралось несколько
волейбольных команд, состоящих из разных зверей. На турнире каждая
команда играет с каждой. Докажите, что после каждой игры найдутся две
команды, сыгравшие к этому моменту одинаковое число матчей.

Ответ:

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

Предположим, что после каждой игры ни у каких двух команд не будет одинакового числа побед. Посмотрим на количество побед каждой команды. Всего имеется (п) команд.

каждая команда может выиграть от 0 до (n-1) матчей (поскольку она не может выиграть у самой себя). Если ни у двух команд нет одинакового числа побед, то у каждой команды число побед будет уникальным.

Но у нас всего (п) команд и (п) возможных чисел побед. По принципу Дирихле, если мы разделим (п) команд на (n-1) возможных чисел побед, то найдутся две команды, у которых одинаковое число побед. Таким образом, мы приходим к противоречию.

Следовательно, наши первоначальные предположения

неверны, и найдутся две команды, сыгравшие к

этому моменту одинаковое число матчей.