Задача 67595
|
|
 |
Условие
а) В тридевятом царстве $n$ городов. Иван-царевич строит дороги по одной (сначала дорог нет). Каждый раз он выбирает два города, не соединённых напрямую дорогой, расстояние между которыми наименьшее, и соединяет их прямолинейной дорогой. Строительство заканчивается, когда становится возможным проехать из любого города в любой (напрямую или через другие города). Обязательно ли никакие две построенные дороги не будут пересекаться вне городов?б) Тот же вопрос, если каждый раз выбираются два ближайших друг к другу города, между которыми невозможен проезд (даже через другие города).
Решение
а) Не обязательно. При расположении городов, как на рисунке справа, сначала будут проведены стороны квадрата (в каком-то порядке), потом обе его диагонали, а затем последняя дорога.
Тогда это либо диагонали выпуклого четырёхугольника $ABCD$ (первый случай), либо $A,B,C,D$ лежат на одной прямой (второй случай). Перед проведением дороги $BD$ города $B$ и $D$ не были связаны никаким путём. Тогда хотя бы от одного из них (пусть $D$) нельзя было доехать до дороги $AC$. То, что вместо дороги $BD$ не была проведена ни одна из дорог $AD$, $CD$, означает, что $AD \geqslant BD$, $CD \geqslant BD$. Перед проведением дороги $AC$ города $A$ и $C$ тоже не были связаны путём. Тогда хотя бы один из них (пусть $C$) не был соединён с $B$. То, что вместо дороги $AC$ не была проведена дорога $BC$, означает, что $BC \geqslant AC$. Значит, $BC + AD \geqslant AC + BD$. Но, как известно, в четырёхугольнике сумма двух противоположных сторон меньше суммы диагоналей, поэтому в первом случае сразу получаем противоречие.
Во втором случае, так как $AC$ и $BD$ пересекаются и $AD \geqslant BD$, $CD \geqslant BD$, то города $A$ и $C$ лежат вне отрезка $BD$ и по разные стороны от него. Но тогда неравенство $BC \geqslant AC$ невозможно, так как $B$ лежит внутри отрезка $AC$.
Ответ
а) Не обязательно.б) Обязательно.
Замечания
В пункте а) имеется контрпример и всего с четырьмя городами: четырехугольник $ABCD$ с $AD=CD>BD>AC>AB=BC$.В пункте б) случай, когда $ABCD$ — выпуклый четырёхугольник, можно разобрать немного иначе. Пусть проведены его диагонали $AC$ и $BD$. У этого четырёхугольника есть неострый угол, будем считать, что это угол $B$. Тогда $AC>AB$, $AC>BC$. В момент проведения диагонали $AC$ города $A$ и $C$ не были связаны путём, поэтому какой-то из них не был связан с $B$ — пусть, например, $A$. Тогда перед этим уже была либо проведена дорога $AB$, либо $A$ и $B$ были соединены путём. Но поскольку $A$ и $C$ сейчас по-прежнему не соединены путём, то перед этим должен была быть также проведена либо дорога $BC$, либо путь, соединяющий $B$ и $C$. Но тогда $A$ и $C$ уже связаны путём, противоречие.
