Ещё одна красивая задача.

[niktoinikak]

В некоторой стране между 2-мя любыми городами имеется непосредственное железнодорожное сообщение, но толькo в одном направлении. Доказать, что существует город, в который из любого другого можно попасть, проезжая не более чем через один промежуточный город

Comments

[lilac2012]

Спасибо. Сейчас немного не до этого - сами видели и поучаствовали. Я уже не отвечаю даже вменяемым. Но если отвечать, надо делать это как lenkakot, которой я безмерно благодарна. Я бы не смогла - нет её эрудиции.
---------------------
О задаче. Допустим, в стране есть только 2 города А и В. Из А в В попасть можно, из В в А нельзя. В условии не сказано, что городов должно быть больше 2. Есть только намёк: любые 2 города. Ну пусть и будут любыми за неимением прочих. И поскольку "попасть" из А в А тоже нельзя, мне кажется, нужно всё же как-то переформулировать условие.
Решение кажется очевидным, а писать лень. На картинку бы взглянула, если вам не хлопотно.

[grisha51]

Картинку я не могу нарисовать, но могу описать. Как уже сказано, действуем по индукции. Т е для некоторого n утверждение верно, т е существует
Город А, в который можно сразу попасть из некоторых других городов - назовём их его соседями . А из любого не соседа можно сразу попасть в один из соседей. Эти города назовём далёкими.
Вот и вся картинка. Она у меня она рисуется в воображении как кольцо соседей вокруг А и облака далёких сверху, из каждого из которых ведёт стрелка вниз в один из соседей.
Ну и шаг индукции - смотрим что происходит если добавить ещё один город Б. Если он сосед - всё ОК. Если из него можно попасть в один из соседей, т е он далёкий - тоже ОК. Если нет, из А и соседей из него ведут стрелки, а из любого из далёких мы попадаем в один из соседей и из этого соседа - в Б. т е Б тогда удовлетворяет утверждению - индукция проведена.

[lilac2012]

Да, красиво. Спасибо! Только сейчас смогла прочитать. Поток дерьма сократился. Не ожидала, что столько мрази набежит. Вот один для примера - https://lilac2012.livejournal.com/1409739.html?thread=14470859#t14470859
Только не отвечайте ради бога, не то опять по новой начнётся.

[grisha51]

"А в В попасть можно, из В в А нельзя. В условии не сказано, что городов должно быть больше 2. Есть только намёк: любые 2 города. Ну пусть и будут любыми за неимением прочих. И поскольку "попасть" из А в А тоже нельзя, мне кажется, нужно всё же как-то переформулировать условие"

Тут у меня нет слов. Что Вы такое говорите, о чём?! Особенно меня поражает заявление что не сказано что городов д б больше 2. Ну не сказано. Так сказано, что не меньше 2(иначе бессмысленно заявление, что есть сообщение, причём только в одну сторону). А когда их ровно 2 ситуация предельно ясна - из одного из городов прямо попадаем в другой, что и требовалось. В чём Вы видите неясность условия мне непонятно. Впрочем, м б Вы разьясните :-)