Скрыть решение
Решение
а) Будем учитывать только тех пассажиров, которые находятся в автобусе, когда
он едет от 7-й остановки до 8-й. Это будут в точности те пассажиры, которые
едут от остановки с номером
i
7 до остановки с номером
j
8. Возьмём
квадрат 7×7, строки которого занумерованы числами 1, ..., 7, а
столбцы — числами 8, ..., 14. Если в автобусе есть пассажир, едущий
от остановки с номером
i
7 до остановки с номером
j
8, то отметим в
квадрате клетку, стоящую на пересечении
i-й строки и
j-го столбца.
Количество отмеченных клеток по условию не больше 25, поэтому есть по крайней
мере
24 = 4
. 6 непомеченные клетки.
Докажем, что в указанном квадрате 7×7 можно выделить строки
A1, ...,
A4 и столбцы
B1, ...,
B4 так, что на пересечении
строки
Ai и столбца
Bj стоит неотмеченная клетка. Сначала докажем, что
можно выделить одну строку и один столбец так, что на их пересечении стоит
неотмеченная клетка, а после их вычёркивания остаётся не менее
15 = 3
. 5
неотмеченных клеток. Если в каждом столбце и в каждой строке не более 5
неотмеченных клеток, то можно взять любую неотмеченную клетку и выделить
содержащие её строку и столбец. Действительно, в этом случае выделенные строка
и столбец содержат не более 9 неотмеченных клеток. Если в какой-то строке
(столбце) стоит 6 неотмеченных клеток, то среди столбцов (строк), проходящих
через неотмеченные клетки этой строки (столбца) найдётся столбец (строка), в
котором стоит не более 4 отмеченных точек. Можно выделить эти строку и столбец.
Если в какой-то строке (столбце) все клетки неотмеченные, то найдётся столбец
(строка), в котором стоит не более 3 неотмеченных точек. Можно выделить эти
строку и столбец.
Аналогично можно доказать, что в полученном квадрате 6×6 можно выделить
строку и столбец, на пересечении которых стоит неотмеченная клетка, так, чтобы
после их вычёркивания осталось не менее
8 = 2
. 4 неотмеченных клеток. Затем
в полученном квадрате 6×6 можно выделить строку и столбец, на
пересечении которых стоит неотмеченная клетка, так, чтобы после их вычёркивания
осталось не менее
3 = 1
. 3 неотмеченных клеток (нам достаточно, чтобы
осталась одна неотмеченная клетка).
б) Пусть от каждой остановки с номерами 1, 2, ..., 10 до каждой другой
остановки с этими номерами едет ровно один пассажир, а дальше автобус едет
пустым. Посчитаем, сколько пассажиров находится в автобусе, когда он едет от
остановки с номером
k до остановки с номером
k + 1, где
1
k
9. Это
будут в точности те пассажиры, которые вошли на остановках с номерами 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, а для
любой такой пары остановок найдётся пассажир, который едет от одной остановки
до другой.