Question

В автобусе едут 34 пассажира. Автобус делает 9 остановок. Ни на одной из остановок новые пассажиры не входят. Докажите,что найдутся две остановки,на которых выйдет одинаковое количество пассажиров.

Answer 1

Если бы на каждой из девяти остановок выходили бы разное количество людей т. е. 1, 2, 3, 4, 5, 6, 7, 8, 9 то в автобусе должны были находится 45 пассажиров. Раз их меньше 45, то должны выйти одинаковое количество хотя бы на двух остановках.

Answer 2

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

В нашем случае, мы имеем 9 остановок и 34 пассажира, и мы хотим доказать, что найдутся две остановки, на которых выйдет одинаковое количество пассажиров.

Предположим обратное: на каждой остановке будет выходить разное количество пассажиров. Тогда на первой остановке выйдет какое-то количество пассажиров (не равное 0 и не равное 34). На второй остановке останется 34 - количество пассажиров, вышедших на первой остановке, и опять выйдет какое-то количество пассажиров (не равное 0 и не равное предыдущему остатку). Продолжая этот процесс для всех остановок, мы получим 9 различных остатков, которые могут быть равными числам от 1 до 33 (поскольку на первой и последней остановках не могут выйти все 34 пассажира).

Теперь мы имеем 9 остатков и 33 возможных числа (от 1 до 33), но у нас всего 9 остановок, что противоречит принципу Дирихле. Таким образом, наш предположенный сценарий невозможен, и обязательно найдутся две остановки, на которых выйдет одинаковое количество пассажиров.