Задача 1.2. Лабиринт с поворотными барьерами

Как барьер поворачивает шарик

Начнём с одной клетки: без этого не нарисовать ни одного пути. Барьер стоит по диагонали клетки, и шарик отскакивает от него, как от зеркала, — остаётся по ту же сторону барьера, с которой прилетел. Чтобы не путаться, запишем правило для обоих барьеров сразу (оно же на рисунке ниже):

• барьер «/»: вправо → вверх, влево → вниз, вверх → вправо, вниз → влево;
• барьер «\»: вправо → вниз, влево → вверх, вверх → влево, вниз → вправо.

Запись «вправо → вверх» значит: шарик летел вправо, а после удара летит вверх.

После удара барьер поворачивается на $90^\circ$ вокруг своего центра. В какую сторону — неважно: и так, и так «/» становится «\», а «\» — «/». Значит, после двух ударов барьер стоит так же, как в начале, после трёх — снова повёрнут. Для конечного рисунка достаточно знать, чётное или нечётное число раз ударили по каждому барьеру. А во время движения важно другое: если шарик вернётся к барьеру, по которому уже ударил, тот стоит уже по-другому и отправит шарик в другую сторону.

Пункт а): ведём шарик от барьера к барьеру

Назовём клетки, как в «морском бое»: столбцы — буквами А, Б, В, Г, Д, Е, Ж, З слева направо (последняя — буква «З», восьмой столбец), строки — числами от $1$ до $6$ сверху вниз. Шарик на рис.1 стоит в А1 и летит вправо.

Ещё договоримся о времени. Переход шарика в соседнюю клетку назовём ходом; все ходы длятся одинаково. Момент $0$ — старт, а в момент $n$ шарик сделал ровно $n$ ходов. По моментам удобно сверять путь с рисунком и с моделью.

Между барьерами шарик катится по прямой, поэтому достаточно найти ближайший барьер на его пути. После каждого удара сразу поворачиваем этот барьер:

• А1 → Г1: «\» отправляет шарик вниз, Г1 становится «/»;
• Г1 → Г5: «\» — вправо, Г5 становится «/»;
• Г5 → Е5: «/» — вверх, Е5 становится «\»;
• Е5 → Е2: «\» — влево, Е2 становится «/»;
• Е2 → Б2: «/» — вниз, Б2 становится «\»;
• Б2 → Б6: «\» — вправо, Б6 становится «/»;
• Б6 → Г6: «/» — вверх, Г6 становится «\».

Теперь шарик второй раз приходит в Г5 — здесь легко ошибиться. На рис.1 там «\», но после первого удара барьер уже «/», поэтому шарик, летевший вверх, поворачивает вправо, а Г5 снова становится «\». Через Д5 шарик второй раз приходит в Е5: там уже «\», шарик поворачивает вниз, Е5 снова становится «/». Шарик попадает в Е6. Это нижняя строка: дальше шарик докатывается до нижней стенки и останавливается у неё, оставаясь в клетке Е6.

Всего шарик прошёл $3 + 4 + 2 + 3 + 4 + 4 + 2 + 1 + 2 + 1 = 26$ клеток и ударился о барьеры $9$ раз. Значит, в центр Е6 он пришёл в момент $26$. Затем осталось пройти ещё половину клетки до нижней стенки; новых барьеров на этом участке нет. В модели маленьких шариков-точек остановка происходит в момент $26{,}5$.

Пункт а): какие барьеры повернулись

Для конечного рисунка не нужно помнить весь путь: достаточно сосчитать удары по каждому барьеру и применить правило из шага 1 — нечётное число ударов поворачивает барьер, чётное возвращает его на место.

Итак, в конце шарик стоит в Е6 у нижней стенки, пять барьеров повёрнуты, а Г5 и Е5 стоят как на рис.1.

Пункт б): общие часы и где встречаются шарики

Теперь шариков два, и они мешают друг другу: могут столкнуться, а барьер, повёрнутый одним шариком, повёрнут и для другого. Поэтому нельзя сначала провести до конца серый шарик, а потом белый. Двигаем их одновременно, по общим часам: за один ход каждый шарик проходит одну клетку — скорости одинаковые и не меняются. В момент $n$ каждый движущийся шарик сделал $n$ ходов.

Где шарики могут столкнуться? Либо в центре клетки, куда оба пришли в один и тот же момент, либо по дороге между центрами. Но по дороге встретиться можно, только двигаясь навстречу друг другу по одному отрезку, — значит, перед этим шарики стояли в соседних клетках. Покажем, что так не бывает. Раскрасим лабиринт, как шахматную доску. Серый шарик стартует в Г1, белый — в З1 (столбец З, восьмой), и это клетки одного цвета. За каждый ход каждый шарик переходит в соседнюю клетку и поэтому меняет цвет. Значит, пока оба движутся, они в каждый момент стоят на клетках одного цвета, а соседние клетки — разного цвета. Шарики могут встретиться только в центре клетки, и в таблице достаточно следить, не пришли ли оба в одну клетку.

Первые пять моментов. Серый: Г1 → Г2 («/», теперь влево) → В2 («/», теперь вниз) → В3 («\», теперь вправо) → Г3 → Д3. Белый: З1 → Ж1 («/», теперь вниз) → Ж2 → Ж3 («/», теперь влево) → Е3 → Д3. В момент $5$ оба приходят в Д3 и сталкиваются: серый летит обратно влево, белый — вправо.

Пункт б): таблица до самого конца

Продолжим так же. В таблице записано, где шарик оказался в каждый момент; «→ влево» — куда он летит после удара о барьер или после столкновения шариков (в таблице столкновение для краткости названо встречей). В остальных строках шарик летит в прежнем направлении.

В трёх местах нужна внимательность. В момент $7$ шарики возвращаются к барьерам В3 и Ж3, которые сами повернули в момент $3$. В момент $11$ шарики сталкиваются под прямым углом: серый летел вправо, белый — вниз; по условию направления меняются на противоположные, поэтому серый летит влево, белый — вверх. В момент $17$ шарики после третьего столкновения снова попадают в Б6 и Б4 — к барьерам, которые повернулись в момент $15$.

В момент $18$ оба шарика приходят в центры клеток левого столбца. Они летят влево ещё половину клетки и одновременно останавливаются у левой стенки в момент $18{,}5$ (в модели шариков-точек). На этих последних коротких участках шарики уже не встретятся и не заденут барьеров. Значит, до самого конца ни один шарик не стоит, пока другой движется, и довод про цвета из шага 4 верен для всей таблицы.

Пункт б): конечное состояние

Сосчитаем по таблице удары по каждому барьеру.

• Один удар: Ж1, Г2, В2, Ж4, В6. Все они были «/» и стали «\».
• Два удара: В3, Ж3, Д4, В5, Б6, Б4 — стоят как в начале.
• Ни одного: Б3 — к нему шарики не подходили.

Конечное состояние: серый шарик в А6, белый — в А4, оба у левой стенки. Повёрнуты ровно пять барьеров — Ж1, Г2, В2, Ж4 и В6, остальные семь стоят как на рис.2.