---

Показать решение

---

Скрыть решение

Решение

а) Будем учитывать только тех пассажиров, которые находятся в автобусе, когда он едет от 7-й остановки до 8-й. Это будут в точности те пассажиры, которые едут от остановки с номером i7 до остановки с номером j8. Возьмём квадрат 7×7, строки которого занумерованы числами 1, ..., 7, а столбцы — числами 8, ..., 14. Если в автобусе есть пассажир, едущий от остановки с номером i7 до остановки с номером j8, то отметим в квадрате клетку, стоящую на пересечении i-й строки и j-го столбца. Количество отмеченных клеток по условию не больше 25, поэтому есть по крайней мере 24 = 4 ^. 6 непомеченные клетки. Докажем, что в указанном квадрате 7×7 можно выделить строки A₁, ..., A₄ и столбцы B₁, ..., B₄ так, что на пересечении строки A_i и столбца B_j стоит неотмеченная клетка. Сначала докажем, что можно выделить одну строку и один столбец так, что на их пересечении стоит неотмеченная клетка, а после их вычёркивания остаётся не менее 15 = 3 ^. 5 неотмеченных клеток. Если в каждом столбце и в каждой строке не более 5 неотмеченных клеток, то можно взять любую неотмеченную клетку и выделить содержащие её строку и столбец. Действительно, в этом случае выделенные строка и столбец содержат не более 9 неотмеченных клеток. Если в какой-то строке (столбце) стоит 6 неотмеченных клеток, то среди столбцов (строк), проходящих через неотмеченные клетки этой строки (столбца) найдётся столбец (строка), в котором стоит не более 4 отмеченных точек. Можно выделить эти строку и столбец. Если в какой-то строке (столбце) все клетки неотмеченные, то найдётся столбец (строка), в котором стоит не более 3 неотмеченных точек. Можно выделить эти строку и столбец. Аналогично можно доказать, что в полученном квадрате 6×6 можно выделить строку и столбец, на пересечении которых стоит неотмеченная клетка, так, чтобы после их вычёркивания осталось не менее 8 = 2 ^. 4 неотмеченных клеток. Затем в полученном квадрате 6×6 можно выделить строку и столбец, на пересечении которых стоит неотмеченная клетка, так, чтобы после их вычёркивания осталось не менее 3 = 1 ^. 3 неотмеченных клеток (нам достаточно, чтобы осталась одна неотмеченная клетка). б) Пусть от каждой остановки с номерами 1, 2, ..., 10 до каждой другой остановки с этими номерами едет ровно один пассажир, а дальше автобус едет пустым. Посчитаем, сколько пассажиров находится в автобусе, когда он едет от остановки с номером k до остановки с номером k + 1, где 1k9. Это будут в точности те пассажиры, которые вошли на остановках с номерами 1, 2, ..., k и выйдут на остановках с номерами k + 1, k + 2, ..., 10 = k + (10 - k). Всего таких пассажиров будет k(10 - k). Ясно, что k(10 - k)25 (больше всего пассажиров в автобусе будет, когда он едет от остановки 5 до остановки 6). Если нам задано 10 различных остановок, то остановки с номерами 11, 12, 13, 14 могут входить не более чем в 4 пары этих остановок; в пятую пару входят остановки с номерами 1, 2, ..., 10, а для любой такой пары остановок найдётся пассажир, который едет от одной остановки до другой.