|
|
 |
Условие
Автобусный маршрут содержит 14 остановок (считая две конечные). В автобусе
одновременно могут ехать не более 25 пассажиров. Доказать, что во время
поездки автобуса из одного конца в другой
a) найдутся восемь таких различных остановок A1, B1, A2, B2, A3, B3, A4, B4, что ни один пассажир не едет от A1 до B1, ни один пассажир не едет от A2 до B2, ни один пассажир не едет от A3 до B3 и ни один пассажир не едет от A4 до B4;
б) может оказаться, что пассажиры едут таким образом, что не существует десяти различных остановок A1, B1, A2, B2, A3, B3, A4, B4, A5, B5, которые обладали бы аналогичными свойствами.
Решение
а) Будем учитывать только тех пассажиров, которые находятся в автобусе, когда он едет от 7-й остановки до 8-й. Это будут в точности те пассажиры, которые едут от остановки с номером i ≤ 7 до остановки с номером j ≥ 8. Возьмём квадрат 7×7, строки которого занумерованы числами 1, ..., 7, а столбцы — числами 8, ..., 14. Если в автобусе есть пассажир, едущий от остановки с номером i до остановки с номером j, то отметим в квадрате клетку, стоящую на пересечении i-й строки и j-го столбца. Количество отмеченных клеток по условию не больше 25, поэтому есть по крайней мере 24 неотмеченные клетки. Докажем, что в указанном квадрате 7×7 можно выделить строки
A1, ..., A4 и столбцы B1, ..., B4 так, что на пересечении строки Ai и столбца Bj стоит неотмеченная клетка.
Проведём в этом квадрате главную диагональ и параллельные ей диагонали разобьем на пары: каждая пара состоит из диагоналей, лежащих по разные стороны от главной, и содержит в совокупности 7 клеток. У нас получилось 7 групп по 7 клеток. Так как всего неотмеченных клеток больше 7·3 = 21, то какая-то группа содержит не меньше четырёх неотмеченных клеток. Они и задают искомые четыре пары строк и столбцов.
б) Пусть от каждой остановки с номерами 1, 2, ..., 10 до каждой другой остановки с этими номерами едет ровно один пассажир, а дальше автобус идет пустым. Посчитаем, сколько пассажиров находится в автобусе, когда он едет от остановки с номером k до остановки с номером
k + 1, где 1 ≤ k ≤ 9. Это в точности те пассажиры, которые вошли на остановках с номерами 1, 2, ..., k и выйдут на остановках с номерами
k + 1, k + 2, ..., 10. Всего таких пассажиров k(10 – k) ≤ 25.
Если нам задано пять пар различных остановок, то остановки с номерами 11, 12, 13, 14 могут входить не более чем в четыре пары; в пятую пару входят остановки с номерами 1, 2, ..., 10, и по построению найдётся пассажир, который едет от одной из них до другой.
