Некоторое государство
От: ansi  
Дата: 25.04.05 12:16
Оценка:
В некотором государстве любой город соединен авиалиниями не более чем с тремя другими. Из любого города в любой другой можно долететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в государстве?
new RSDN@Home(1.1.4, 303) << new Message(); std::head::ear << "Iscaaro — Fold Your Hands And Pray";
Re: Некоторое государство
От: Oyster Украина https://github.com/devoyster
Дата: 25.04.05 12:21
Оценка:
Здравствуйте, ansi, Вы писали:

A>В некотором государстве любой город соединен авиалиниями не более чем с тремя другими. Из любого города в любой другой можно долететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в государстве?


6?
Re[2]: Можно и 7
От: Eugene Sh Россия  
Дата: 25.04.05 12:40
Оценка:
Города: 1,2,...,7
Линии: 1-2, 1-3, 1-4, 2-5, 3-6, 4-7, 5-6, 6-7, 5-7
Re[3]: И даже 8
От: Eugene Sh Россия  
Дата: 25.04.05 12:41
Оценка: 30 (2)
Здравствуйте, Eugene Sh, Вы писали:

ES>Города: 1,2,...,7

ES>Линии: 1-2, 1-3, 1-4, 2-5, 3-6, 4-7, 5-6, 6-7, 5-7

Добавляем город 8. И соединяем его с 2,3 и 4.
Re[4]: И даже 8
От: hemmul США  
Дата: 25.04.05 12:58
Оценка:
Здравствуйте, Eugene Sh, Вы писали:

ES>Здравствуйте, Eugene Sh, Вы писали:


ES>>Города: 1,2,...,7

ES>>Линии: 1-2, 1-3, 1-4, 2-5, 3-6, 4-7, 5-6, 6-7, 5-7

ES>Добавляем город 8. И соединяем его с 2,3 и 4.


а как тогда переедем из 5 в 8? меньше чем за 2 хопа не получается имхо...
а так, для семи получается так:
берём куб, и убераем одну вершину:
        o-.
    . / |\ \       * - вот её убрали...
  /     | \  \
o-------+--o   \
|       |   \    \
|       |     \    \
|       |       \  |
|       o----------o
|    . /        . /
|  /          /
o----------o

vox clamantis in deserto
Re[5]: И даже 8
От: G.I. O_Neil Россия  
Дата: 25.04.05 12:59
Оценка: 1 (1) +1
Здравствуйте, hemmul, Вы писали:

H>а как тогда переедем из 5 в 8? меньше чем за 2 хопа не получается имхо...

5-2, 2-8
Don't crash the ambulance, whatever you do!
ICQ#327823673
In her dealings with man Destiny never closed her accounts. (c) Oscar Wilde
Re: Некоторое государство
От: ZevS Россия  
Дата: 25.04.05 13:21
Оценка: -1
Здравствуйте, ansi, Вы писали:

A>В некотором государстве любой город соединен авиалиниями не более чем с тремя другими. Из любого города в любой другой можно долететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в государстве?


Бесконечное число городов: один в центре и сколько угодно по кольцу!
Re[2]: это была...
От: ZevS Россия  
Дата: 25.04.05 13:23
Оценка: :)
шутка
Re: Некоторое государство
От: tinytjan  
Дата: 25.04.05 14:14
Оценка:
Здравствуйте, ansi, Вы писали:

A>В некотором государстве любой город соединен авиалиниями не более чем с тремя другими. Из любого города в любой другой можно долететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в государстве?


Вот для восьми.
Верхняя граница 10 — показать несложно, а вот точно — хез
Re[2]: Некоторое государство
От: Аноним  
Дата: 25.04.05 20:03
Оценка: 10 (1)
Здравствуйте, tinytjan, Вы писали:

T>Здравствуйте, ansi, Вы писали:


A>>В некотором государстве любой город соединен авиалиниями не более чем с тремя другими. Из любого города в любой другой можно долететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в государстве?T>Вот для восьми.

T>Верхняя граница 10 — показать несложно, а вот точно — хез

Могу доказать, что городов не 9 (так что остается лишь проверить десятку).
Наблюдение: Если существует город, из которого выходят только 2 линии, то всего городов не более 7 (тот, из которого выходят 2 линии, еще два, в которые ведут эти линии, и еще из каждого из них может выйти не более 2 новых линий). Так что, если городов больше 7, то из каждого обязано выходить ровно 3 линии. Если городов 9, то посчитаем линии: из каждого города выходит по линии, итого 3*9 = 27 линий, но каждая линия посчитана дважды (как соединяющая А и Б и как соединяющая Б и А), поэтому не могло получиться 27 (на 2 не делится). Это доказывает тот простой факт, что в графе с 9 вершинами не может из каждой вершины выходить ровно 3 ребра.
Re: Некоторое государство
От: Аноним  
Дата: 25.04.05 20:16
Оценка:
Здравствуйте, ansi, Вы писали:

A>В некотором государстве любой город соединен авиалиниями не более чем с тремя другими. Из любого города в любой другой можно долететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в государстве?
Re: Некоторое государство
От: XUMEPA  
Дата: 25.04.05 20:22
Оценка: -1
Здравствуйте, ansi, Вы писали:

A>В некотором государстве любой город соединен авиалиниями не более чем с тремя другими. Из любого города в любой другой можно долететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в государстве?




Вобщем городов 6


/ 0\
/ | \
/ 0 \
/ / \ \
/ 0-0 \
0--/------\----0

MINIMUM

no comment
Re[3]: Некоторое государство
От: tinytjan  
Дата: 26.04.05 06:43
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, tinytjan, Вы писали:


T>>Здравствуйте, ansi, Вы писали:


T>>Верхняя граница 10 — показать несложно, а вот точно — хез

Для десяти надо всего лишь доказать что нельзя для следующего графа

так добавить связи чтобы выполнялось условие задачи.

А>Могу доказать, что городов не 9 (так что остается лишь проверить десятку).

А>Наблюдение: Если существует город, из которого выходят только 2 линии, то всего городов не более 7 (тот, из которого выходят 2 линии, еще два, в которые ведут эти линии, и еще из каждого из них может выйти не более 2 новых линий). Так что, если городов больше 7, то из каждого обязано выходить ровно 3 линии. Если городов 9, то посчитаем линии: из каждого города выходит по линии, итого 3*9 = 27 линий, но каждая линия посчитана дважды (как соединяющая А и Б и как соединяющая Б и А), поэтому не могло получиться 27 (на 2 не делится). Это доказывает тот простой факт, что в графе с 9 вершинами не может из каждой вершины выходить ровно 3 ребра.

На доказательство это не очень похоже, все-таки наблюдениями утверждения не доказываются.
Но ели я не ошибаюсь, случай для девяти может быть представлен как случай для 10 только без одной крайней вершины. Тогда надо доказать то же самое, что и для 10.
Re[4]: Некоторое государство
От: Eugene Sh Россия  
Дата: 26.04.05 10:50
Оценка:
Здравствуйте, tinytjan, Вы писали:

T>На доказательство это не очень похоже, все-таки наблюдениями утверждения не доказываются.


Да нет, это вполне нормальное доказательство.

Посмотри ещё раз:
1) Если городов 9, то не может случиться так, что из каждого из них выходит 3 линии. Это следует из того, что 27 — нечётное число.
Значит, есть город A, из которого выходит только 2 линии (или 1 — это ещё хуже)

2) Посмотрим, в какие города мы сможем долететь из города A за 2 перелёта.
Есть 2 города B1 и B2, в которые можно перелететь за 1 перелёт.
За 1 перелёт из города B1 мы можем попасть максимум в 3 города: A и ещё 2. Обозначим эти 2 города как C_1_1 и C_1_2.
Аналогично, для города B2 получаем ещё 2 города: C_2_1 и C_2_2.

3) Получается, что из города A не более, чем за 2 перелёта мы можем попасть только в города B1, B2, С_1_1, C_1_2, C_2_1 и C_2_2. То есть всего городов должно быть не больше 7. Противоречие.
Re[5]: Некоторое государство
От: tinytjan  
Дата: 26.04.05 11:10
Оценка:
Здравствуйте, Eugene Sh, Вы писали:

ES>3) Получается, что из города A не более, чем за 2 перелёта мы можем попасть только в города B1, B2, С_1_1, C_1_2, C_2_1 и C_2_2. То есть всего городов должно быть не больше 7. Противоречие.


Осталось 10
Re: Некоторое государство
От: gbear Россия  
Дата: 26.04.05 11:28
Оценка: 61 (5)
Здравствуйте, ansi, Вы писали:

A>В некотором государстве любой город соединен авиалиниями не более чем с тремя другими. Из любого города в любой другой можно долететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в государстве?


10

Имеем:

Точку начала пути. Три точки, в которые можем попасть, из данной точки. Шесть точек (т.к. один путь занят под путь из точки начала пути в заданную точку), в которые можем попасть из точки начала пути. Итого: 1+3+6 = 10. Больше быть не может, в силу условия достижимости.

Граф путей, например такой:

0|1,2,3
1|0,4,5
2|0,6,7
3|0,8,9
4|1,6,8
5|1,7,9
6|2,4,9
7|2,5,8
8|3,4,7
9|3,5,6

---
С уважением, Сиваков Константин.
Re[3]: а если серьезно
От: ZevS Россия  
Дата: 26.04.05 11:34
Оценка: :)
то наверно так —

Re[4]: Некоторое государство
От: gbear Россия  
Дата: 26.04.05 11:34
Оценка: +1
Здравствуйте, tinytjan, Вы писали:

T>Для десяти надо всего лишь доказать что нельзя для следующего графа

T>
T>так добавить связи чтобы выполнялось условие задачи.

Почему нельзя?! Очень даже можно... Например так


---
С уважением, Сиваков Константин
Re[4]: а если серьезно
От: Oyster Украина https://github.com/devoyster
Дата: 26.04.05 11:48
Оценка:
Здравствуйте, ZevS, Вы писали:

ZS>то наверно так -


ZS>


Тогда ещё "внутренние" вершины завязать квадратом...
Re[4]: а если серьезно
От: tinytjan  
Дата: 26.04.05 11:50
Оценка:
Здравствуйте, ZevS, Вы писали:

ZS>то наверно так -


ZS>

Вроде одной связи не хватает
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.