Разделы 
Дополнительно
Задача по математике - 10452
2023-02-17 
Вдоль параллельных границ некоторой территории, имеющей форму квадрата со стороной 10 км, проложены автострады. На территории размещены 4 наблюдательных поста. Требуется построить подъездные дороги из отрезков, параллельных сторонам квадрата, так, чтобы из каждого наблюдательного поста можно было добраться на велосипеде до каждой автострады (по автостраде ездить на велосипеде воспрещается).
Доказать, что независимо от того, где расположены наблюдательные посты, всегда можно построить подъездные пути общей протяженностью не более 25 км (при некоторых расположениях наблюдательных постов меньшая протяженность подъездных путей может оказаться недостаточной).
Решение:
Предположим, что автострады проложены по северной и южной границам территории. Обозначим наблюдательные посты в том порядке, в каком мы встретили бы их, двигаясь с запада на восток, $А_{1}, А_{2}, A_{3}, A_{4}$. Пусть $a_{1}, a_{2}, a_{3}, a_{4}$ - расстояния от соответствующих наблюдательных постов до западной границы территории. Среди чисел $а_{1}, а_{2}, а_{3}, а_{4}$ могут быть равные. В общем случае они удовлетворяют неравенству $a_{1} \leq a_{2} \leq a_{3} \leq a_{4}$.
Если $a_{3} - a_{2} \leq 5$ км, то проведем одну подъездную дорогу от северной автострады до южной так, чтобы она проходила между наблюдательными постами $A_{2}$ и $А_{3}$, или, если $а_{2} = а_{3}$, по меридиану, на котором лежат оба наблюдательных поста. Затем соединим все посты с построенной дорогой подъездными путями, идущими с запада на восток или с востока на запад (рис. a). Длина дороги, соединяющей северную автостраду с южной, равна 10 км. Общая длина подъездных путей, ведущих к дороге от наблюдательных постов $A_{1}$ и $A_{4}$, не превышает 10 км, поскольку $a_{4} - a_{1} \leq 10$ км. По предположению длина подъездных путей, ведущих к дороге от наблюдательных постов $А_{2}$ и $А_{3}$, не превышает 5 км. Таким образом, общая протяженность всех подъездных дорог в рассматриваемом случае не превышает 25 км.
Если $а_{3} - a_{2} \geq 5$ км, то проведем по одной дороге, идущей с севера на юг между наблюдательными постами $А_{1}, A_{2}$ и $А_{3}, A_{4}$. Если $a_{1} = a_{2}$ или $а_{3} = a_{4}$, то соответствующую дорогу проведем по меридиану, на котором лежат оба поста. Если же хотя бы одно из равенств нарушено, то соединим посты с проходящей между ними дорогой подъездными путями, идущими с запада на восток или с востока на запад (рис. 6). Общая протяженность подъездных дорог в этом случае составляет
$20 + a_{2} - a_{1} + a_{4} - a_{3} = 20 + (a_{4} - a_{1}) - (a_{3} - a_{2}) \leq 20 + 10 - 5 = 25$ км.
Таким образом, и при $а_{3} - a_{2} \geq 5$ км общая протяженность подъездных путей не превышает 25 км.
Покажем, что меньшая протяженность подъездных дорог оказывается недостаточной при некотором расположении наблюдательных постов, например, в том случае, если посты размещены на границах территории и отстоят от юго-западного, северо-западного, северо-восточного и юго-восточного углов к северу, востоку, югу и западу соответственно на 2,5 км. Обозначим посты в указанной последовательности $А_{1}, A_{2}, A_{4}, A_{3}$.
Кратчайшая схема подъездных путей может состоять не более чем из двух несвязанных (то есть отдельных) частей, поскольку если бы она содержала не менее трех несвязанных частей, то общая протяженность дорог, идущих с севера на юг, составила бы не менее 30 км.
Если схема подъездных дорог состоит из двух несвязанных частей, то общая протяженность дорог, идущих с севера на юг, составляет 20 км. Каждая из связанных частей на схеме подъездных дорог содержит не менее двух наблюдательных постов. Если из поста $А_{1}$, следуя по подъездным дорогам, можно попасть на пост $А_{3}$ или $A_{4}$, то сумма участков дорог, идущих с запада на восток (или с востока на запад), не меньше чем 7,5 км. Аналогичное утверждение справедливо и в том случае, если из поста $A_{4}$ можно попасть на пост $A_{2}$. Если же из поста $А_{1}$ по подъездным дорогам можно добраться лишь до поста $А_{2}$, а из поста $A_{3}$ - лишь до поста $A_{4}$, то схема подъездных путей должна содержать не менее двух участков, идущих с запада на восток, протяженностью до 2,5 км.
Наконец, предположим, что схема подъездных путей связна и позволяет из любого наблюдательного поста попасть на любой другой пост. Рассмотрим путь, ведущий из $А_{1}$ в $A_{4}$. Нас будет интересовать та точка, откуда можно впервые свернуть на пост $A_{2}$ или $А_{3}$. Если, двигаясь от $А_{1}$ мы сначала можем свернуть на $A_{2}$ (рис. а), то «вертикальные» отрезки путей, ведущих из $A_{1}$ в $A_{2}$ и из $A_{4}$ в $A_{3}$, не имеют общих точек. Протяженность каждого из них составляет не менее 7,5 км. Протяженность той части подъездных путей, которые позволяют попасть из $А_{1}$ в $А_{4}$, по горизонтали не меньше 10 км. Следовательно, общая протяженность подъездных путей не меньше 25 км.
Если же, следуя из $А_{1}$ в $A_{4}$, мы можем сначала свернуть на наблюдательный пост $A_{3}$ (рис.б), то «горизонтальные» участки путей, ведущие из $A_{1}$ в $А_{3}$ и из $A_{4}$ в $A_{2}$, не имеют общих точек, а их общая протяженность не меньше 15 км. Поскольку с северной автострады на южную нельзя попасть, если протяженность дороги меньше 10 км, то общая длина подъездных путей и в этом случае не меньше, чем 25 км.
Тем самым утверждение задачи полностью доказано.
Вдоль параллельных границ некоторой территории, имеющей форму квадрата со стороной 10 км, проложены автострады. На территории размещены 4 наблюдательных поста. Требуется построить подъездные дороги из отрезков, параллельных сторонам квадрата, так, чтобы из каждого наблюдательного поста можно было добраться на велосипеде до каждой автострады (по автостраде ездить на велосипеде воспрещается).
Доказать, что независимо от того, где расположены наблюдательные посты, всегда можно построить подъездные пути общей протяженностью не более 25 км (при некоторых расположениях наблюдательных постов меньшая протяженность подъездных путей может оказаться недостаточной).
Решение:
Предположим, что автострады проложены по северной и южной границам территории. Обозначим наблюдательные посты в том порядке, в каком мы встретили бы их, двигаясь с запада на восток, $А_{1}, А_{2}, A_{3}, A_{4}$. Пусть $a_{1}, a_{2}, a_{3}, a_{4}$ - расстояния от соответствующих наблюдательных постов до западной границы территории. Среди чисел $а_{1}, а_{2}, а_{3}, а_{4}$ могут быть равные. В общем случае они удовлетворяют неравенству $a_{1} \leq a_{2} \leq a_{3} \leq a_{4}$.
Если $a_{3} - a_{2} \leq 5$ км, то проведем одну подъездную дорогу от северной автострады до южной так, чтобы она проходила между наблюдательными постами $A_{2}$ и $А_{3}$, или, если $а_{2} = а_{3}$, по меридиану, на котором лежат оба наблюдательных поста. Затем соединим все посты с построенной дорогой подъездными путями, идущими с запада на восток или с востока на запад (рис. a). Длина дороги, соединяющей северную автостраду с южной, равна 10 км. Общая длина подъездных путей, ведущих к дороге от наблюдательных постов $A_{1}$ и $A_{4}$, не превышает 10 км, поскольку $a_{4} - a_{1} \leq 10$ км. По предположению длина подъездных путей, ведущих к дороге от наблюдательных постов $А_{2}$ и $А_{3}$, не превышает 5 км. Таким образом, общая протяженность всех подъездных дорог в рассматриваемом случае не превышает 25 км.
Если $а_{3} - a_{2} \geq 5$ км, то проведем по одной дороге, идущей с севера на юг между наблюдательными постами $А_{1}, A_{2}$ и $А_{3}, A_{4}$. Если $a_{1} = a_{2}$ или $а_{3} = a_{4}$, то соответствующую дорогу проведем по меридиану, на котором лежат оба поста. Если же хотя бы одно из равенств нарушено, то соединим посты с проходящей между ними дорогой подъездными путями, идущими с запада на восток или с востока на запад (рис. 6). Общая протяженность подъездных дорог в этом случае составляет
$20 + a_{2} - a_{1} + a_{4} - a_{3} = 20 + (a_{4} - a_{1}) - (a_{3} - a_{2}) \leq 20 + 10 - 5 = 25$ км.
Таким образом, и при $а_{3} - a_{2} \geq 5$ км общая протяженность подъездных путей не превышает 25 км.
Покажем, что меньшая протяженность подъездных дорог оказывается недостаточной при некотором расположении наблюдательных постов, например, в том случае, если посты размещены на границах территории и отстоят от юго-западного, северо-западного, северо-восточного и юго-восточного углов к северу, востоку, югу и западу соответственно на 2,5 км. Обозначим посты в указанной последовательности $А_{1}, A_{2}, A_{4}, A_{3}$.
Кратчайшая схема подъездных путей может состоять не более чем из двух несвязанных (то есть отдельных) частей, поскольку если бы она содержала не менее трех несвязанных частей, то общая протяженность дорог, идущих с севера на юг, составила бы не менее 30 км.
Если схема подъездных дорог состоит из двух несвязанных частей, то общая протяженность дорог, идущих с севера на юг, составляет 20 км. Каждая из связанных частей на схеме подъездных дорог содержит не менее двух наблюдательных постов. Если из поста $А_{1}$, следуя по подъездным дорогам, можно попасть на пост $А_{3}$ или $A_{4}$, то сумма участков дорог, идущих с запада на восток (или с востока на запад), не меньше чем 7,5 км. Аналогичное утверждение справедливо и в том случае, если из поста $A_{4}$ можно попасть на пост $A_{2}$. Если же из поста $А_{1}$ по подъездным дорогам можно добраться лишь до поста $А_{2}$, а из поста $A_{3}$ - лишь до поста $A_{4}$, то схема подъездных путей должна содержать не менее двух участков, идущих с запада на восток, протяженностью до 2,5 км.
Наконец, предположим, что схема подъездных путей связна и позволяет из любого наблюдательного поста попасть на любой другой пост. Рассмотрим путь, ведущий из $А_{1}$ в $A_{4}$. Нас будет интересовать та точка, откуда можно впервые свернуть на пост $A_{2}$ или $А_{3}$. Если, двигаясь от $А_{1}$ мы сначала можем свернуть на $A_{2}$ (рис. а), то «вертикальные» отрезки путей, ведущих из $A_{1}$ в $A_{2}$ и из $A_{4}$ в $A_{3}$, не имеют общих точек. Протяженность каждого из них составляет не менее 7,5 км. Протяженность той части подъездных путей, которые позволяют попасть из $А_{1}$ в $А_{4}$, по горизонтали не меньше 10 км. Следовательно, общая протяженность подъездных путей не меньше 25 км.
Если же, следуя из $А_{1}$ в $A_{4}$, мы можем сначала свернуть на наблюдательный пост $A_{3}$ (рис.б), то «горизонтальные» участки путей, ведущие из $A_{1}$ в $А_{3}$ и из $A_{4}$ в $A_{2}$, не имеют общих точек, а их общая протяженность не меньше 15 км. Поскольку с северной автострады на южную нельзя попасть, если протяженность дороги меньше 10 км, то общая длина подъездных путей и в этом случае не меньше, чем 25 км.
Тем самым утверждение задачи полностью доказано.
