Олимпиадная задача о дорогах и шлагбаумах для 30 автомобилей

Ответ:нигде не будут задержаны машины с номерами 14, 23 и 24.

Пустьa_n— дорога, выходящая из пунктаA_n,$\alpha_{n}^{}$— угол, который образует дорогаa_nс прямойMN,P_mn— перекрёсток дорогa_nиa_m.

(1) Если машинаa_mзадерживается на перекрёсткеP_nm, то угол$\alpha_{n}^{}$ближе к90^o, чем угол$\alpha_{m}^{}$(дорогаa_nкруче, чем дорогаa_m).

(2) Пустьm<n. Тогда дорогиa_mиa_nпересекаются, если$\alpha_{m}^{}$<$\alpha_{n}^{}$, и не пересекаются, если$\alpha_{m}^{}$$\ge$$\alpha_{n}^{}$.

(3) Если все дороги, пересекающиеa_n, менее круты, чем дорогаa_n, то машинаa_nнигде не задержится. Это следует из (1).

(4) Пустьa_m— самая крутая из дорог, пересекающихa_n. Еслиa_mкручеa_n, тоa_mне может быть задержана раньше перекрёсткаP_nm. Действительно, предположим, что машинаa_mзадерживается на перекрёсткеP_qm, лежащем на отрезкеA_mP_mn. Тогда согласно (1) дорогаa_qкруче дорогиa_m, а значит, по условию она не может пересекатьa_n. Покажем, что это невозможно. Рассмотрим сначала случай, когда точкаA_qлежит вне отрезкаA_nA_m. Прямаяa_qпересекает сторонуA_mP_nmтреугольникаA_mP_nmA_nи не пересекает сторонуA_mA_n, поэтому она пересекает сторонуP_nmA_n, а этого не может быть. Рассмотрим теперь случай, когда точкаA_qлежит внутри отрезкаA_nA_m. Пусть сначалаn<q<m. Дорогиa_nиa_m,a_qиa_mпересекаются, а дорогиa_qиa_nне пересекаются. Поэтому из (2) следует, что$\alpha_{q}^{}$$\le$$\alpha_{n}^{}$<$\alpha_{m}^{}$. Угол$\alpha_{m}^{}$ближе к90^o, чем угол$\alpha_{n}^{}$, поэтому неравенство$\alpha_{n}^{}$<$\alpha_{m}^{}$возможно лишь при$\alpha_{n}^{}$< 90^o. Но тогда из неравенства$\alpha_{q}^{}$$\le$$\alpha_{n}^{}$следует, что дорогаa_qне более крута, чем дорогаa_n, что противоречит условию. Случайn>q>mрассматривается аналогично.

(5) Если машинаa_nпроходит через все перекрёстки, то все дороги, пересекающиеa_n, менее круты, чем дорогаa_n; это следует из (4) и (1).

Итак, из (3) и (5) следует, что машинаa_nпроходит через все перекрёстки тогда и только тогда, когда все дороги, пересекающиеa_n, менее круты, чем дорогаa_n. Теперь уже легко получить требуемый результат.