1000 городов, одностороннее движение.

[never-sleep]

В стране 1000 городов, любые два города соединены дорогой с односторонним движением. Докажите, что существует город, выехав из которого можно объехать все города побывав в каждом ровно один раз. Разрешается ехать только по указанным на дорогах направлениям.

Может от противного подумать. Пронумеруем все города. Пусть есть город номер один, откуда стартуем.
Допустим, нашелся город $k$ ($k=2\text{или}3...\text{или}1000$), такой что его нельхя соединить с $k-1$ или с $k+1$, тогда получаем противоречие, потому как любые два города можно соединить дорогой. Правильно ли это? Как-то слишком просто....

[venco]

Если я правильно понял ваше объяснение, то оно неправильно, ибо не гарантирует нужного направления.

[never-sleep]

venco в сообщении #901518 писал(а):

Если я правильно понял ваше объяснение, то оно неправильно, ибо не гарантирует нужного направления.

А как гарантировать направление? Три города могут быть соединены 3 способами $k-1\rightarrow k \rightarrow k+1$ или $k-1\rightarrow k \leftarrow k+1$ или $k-1 \leftarrow k \leftarrow k+1$
Как это можно все примерно учитывать?

[venco]

Индукцию нужно применять. Пусть есть путь через $k$ городов, возьмите ещё один город, и рассмотрите все варианты дорог между новым городом и остальными. В двух вариантах путь удлинняется тривиально, в остальных случаях это тоже можно сделать. Подумайте.

[never-sleep]

venco в сообщении #901527 писал(а):

Индукцию нужно применять. Пусть есть путь через $k$ городов, возьмите ещё один город, и рассмотрите все варианты дорог между новым городом и остальными. В двух вариантах путь удлинняется тривиально, в остальных случаях это тоже можно сделать. Подумайте.

Спасибо! Пусть есть путь $1\rightarrow 2 \rightarrow ... \rightarrow k$. Тогда $k+1$ город, по правилам соединить можно вот так $k+1 \rightarrow 1\rightarrow 2 \rightarrow ... \rightarrow k \rightarrow k+1$. База интуции -- три города $3 \rightarrow 1 \rightarrow 2 \rightarrow 3$. Верно? Можно ли это считать решением?

[venco]

Нет. Почему вы так уверены, что дорога между $1$ и $k+1$ идёт именно в $1$?

[never-sleep]

venco в сообщении #901529 писал(а):

Нет. Почему вы так уверены, что дорога между $1$ и $k+1$ идёт именно в $1$?

Потому как движение одностороннее, значит если дорога идет из $1$ в $k+1$ из односторонности движения, дорога должна "исходить" из $k+1$ и быть соединена с каждым из $k$ городов, а значит с $1$ в частности. Так будет правильно?

[venco]

Ничего не понял, но, похоже, неправильно.

[never-sleep]

venco в сообщении #901536 писал(а):

Ничего не понял, но, похоже, неправильно.

А как правильно тогда? Что примерно нужно сделать?

[Dan B-Yallay]

Вам же сказали: по индукции. Для 3 городов очевидно, что маршрут есть. Пусть теперь имеем $n$ городов, для которых сушествует путь

$$1\to 2\to ... \to n$$

Для города $n+1$ ищем пункт с наибольшим номером $k$, таким, что дорога ведет из $k$ в $n+1$. Дальше догадаетесь?

[never-sleep]

Dan B-Yallay в сообщении #901541 писал(а):

Вам же сказали: по индукции. Для 3 городов очевидно, что маршрут есть. Пусть теперь имеем $n$ городов, для которых сушествует путь

$$1\to 2\to ... \to n$$

Для города $n+1$ ищем пункт с наибольшим номером $k$, таким, что дорога ведет из $k$ в $n+1$. Дальше догадаетесь?

Спасибо. От противного попробую. Пусть этот наибольший $k<n$. Тогда путь из $n+1$ ведет в $n$ (по условию, так как каждый город соединен с каждым). Тогда нарушается односторонность движения, потому $k=n$. Верно ли это?

P.S. Теперь я понял -- почему меня не понимали до этого. Я думал почему-то что движение по городам круговое обязательно.

[venco]

Я и сейчас не понял.

[function]

Предлагаю свою идею. Назовём город центральным, если из него можно попасть в любой другой город не более, чем 2 дорогами. Пусть для $n-1$ городов всегда найдётся центральный --- $X$. Теперь добавим ещё один город $Y$. Допустим, что нам не повезло, и $Y\rightarrow X$. Выберем такой город $A$, чтобы $A\rightarrow Y$, если такового не оказалось, то $Y$ --- центральный. Положим нам опять не повезло: $A\rightarrow X$, не отчаиваясь, берём какой-нибудь город $B$. Здесь 2 варианта: 1) $B$ является промежуточным между $X$ и $A$ (что всегда возможно по индуктивному предположению, ибо $X$ --- центральный среди тех $n-1$ городов), либо 2) $X$ связывает (т. е. прямиковой дороги нет) $B$ и $A\rightarrow B$. Следовательно, $A$ --- центральный. Убедитесь в последнем самостоятельно.

[venco]

function в сообщении #901678 писал(а):

Предлагаю свою идею. Назовём город центральным

Это какая-то другая задача.
Я-то, как и Dan B-Yallay, решение знаю. Мы пытаемся добиться от ТС нормальной логики. Пока что-то не видно её.

[function]

venco в сообщении #901693 писал(а):

function в сообщении #901678 писал(а):

Предлагаю свою идею. Назовём город центральным

Это какая-то другая задача.
Я-то, как и Dan B-Yallay, решение знаю. Мы пытаемся добиться от ТС нормальной логики. Пока что-то не видно её.

Точно! Немного перепутал. Я недавно решал такую: В стране 1000 городов, любые два города соединены дорогой с односторонним движением. Докажите, что найдётся город, из которого можно попасть в любой другой не более, чем двумя дорогами. Вот сгоряча...

-- 29.08.2014, 16:30 --

Теперь насчёт этой задачи . Пусть существует маршрут: $1\rightarrow 2\rightarrow ...\rightarrow n$. Тогда существует такой город $i$, что из него можно попасть в город $n+1$ (подумайте, что будет, если это не так), причём $i$ выберем наибольшим из возможных. Откуда выходит, что $\exists n+1\rightarrow i+1$. Ну а дальше, я думаю, всё ясно.