Логические задачи : Дороги в Оптимайзии

	"Логические задачи" - это познавательно-развлекательный проект для непрокисших мозгов. Задачи на логику, нестандартное мышление. Не всегда самое очевидное решение - правильное. Но иногда всё оказывается проще, чем кажется на первый взгляд.
Задачи на логику и сообразительность
Главная \| О проекте \| Все задачи-1, 2, 3, 4, 5, 6, 7, 8 \| Добавить задачу

О сайте
Гостевая книга
ЧаВо

Пользователи
RSS

Задачи

Переливания и взвешивания

Задания на наблюдательность

требуется помощь

Чисто поржать

Данетки

Текущие:

  Неожиданный труп 8)
  открытый урок
  ДаНетка с хорошим концом
  Три мертвеца (для разнообразия 8)))
  Загадка от Леонардо да Винчи
  Дом
  Толстяк
  данетка - спасительная
  данетка - теплая
  данетка - холодная
  Жалюзи

Разгаданные недавно:

  Убийца

Справочная

Признаки делимости

Реклама

задача: Дороги в Оптимайзии

В стране Оптимайзии все города соединены дорогами с односторонним движением (каждый с каждым). Докажите, что есть город, из которого в любой другой можно проехать не более чем за две поездки.

Ответ

Решение задачи

Ваши ответы на задачу

ответов: 7

igv105 2011-12-13 20:08:16 пишет:

Назовем столицей множества городов такой город, из которого за 2 поездки можно попасть в любой другой город этого множества. Доказательство проведем по индукции. Для 2 городов условие выполняется. Пусть для любого множества из n-1 города всегда существует столица. Предположим, что для n городов столицы нет. Исключая по очереди каждый город, из n городов можно образовать n различных подмножеств из n-1 города, причем каждые два из этих подмножеств должны иметь разные столицы (из «двойной» столицы можно было бы за два хода попасть в любой город) это значит, что есть n разных столиц то есть каждый из городов – столица какого-то подмножества. Пронумеруем все города следующим образом, произвольному городу присвоим номер 1, столице подмножества, которое не содержит первого города, присвоим номер 2, столице подмножества, не содержащего k-того города, присвоим номер k+1. И так далее до города с номером n – единственного, в который, нельзя за два хода пройти из первого города. Рассмотрим все дороги, которыми, 1-й город соединен с остальными. Движение по дороге которая соединяет его с вторым городом направлено от 1-го ко второму(иначе второй был бы общей столицей), движение по дороге 1город-3город так же направлено от первого к 3-му (иначе из 3-го можно было бы через 1-й попасть во 2-ой за два хода и он был бы столицей) по всем следующим дорогам, движение должно быть направлено от 1-го к k-тому что бы k-ый не был столицей. Следовательно, движение по дороге от 1-го к n-му так же направлено от 1-го. Но в этом случае 1-й город является общей столицей, поскольку во все города из него можно попасть за 1 ход. Получили противоречие. Если рисовать схемы, то это решение совсем простое, честно.

Админ: красиво!

малыш 2011-10-14 09:21:15 пишет:

из любого города можно проехать в любой другой город за 2 поездки!!! Во первых городов не меньше 3(иначе бессмыслица получается)!!! В каждом городе как минимум 2 дороги, и обязательно хотябы по одной можно заехать в город и хотябы по одной выехать!!! допустим что в город, который нужно попасть не идет дороги, значит нужно найти город в который мы можем заехать из нашего города и из этого города можно добраться уже до конечного, куда нам нужно!!! при любых раскладах такие города есть!!! иначе были бы тупики

Админ: мало восклицательных знаков, не убедительно :)

я 2011-06-17 07:05:42 пишет:

в этой стране 4 города

Админ: почему?

Очевидность 2011-04-13 12:56:37 пишет:

Рассмотрим савокупность городов в стране-это граф. Вершины-города, ребра-дороги. Каждые 2 города соединены дорогой с односторонним движением. Из А вершины - выходит всего лишь одно ребро в другую вершину. В Б вершину - приходят n ребер (максимальное кол-во дорог) Если мы рассмотрим крайний случай: из А в Б вершину можно проехать не более чем за две поездки, значит А является тем самым "городом".

Reds on tour 2011-04-13 11:39:23 пишет:

Рассмотрим искомый город А: 1) Все дороги в другие города ведут ИЗ А (вернутся нельзя). Значит из А в любой другой доберешься за 1 поездку. Условию удовлетворяет. 2) Все дороги кроме одной ведут из А. Одна (скажем, из Б) - ведет в А. Тогда, чтобы попасть из А в Б, должно выполнять условие хотя бы одной дороги в Б. Если оно не выполняется, и все дороги ведут только из Б, следовательно Б - искомый город. 3) При равновесном варианте - 50% из, 50% в город, любой из городов страны будет соответствовать условию.

Кристина 2011-04-08 22:33:24 пишет:

если по пути не останавливаться в городах, то можно проехать за одну поездку... или если в этой стране всего два города

Админ: вопрос не об этом

Дмитрий 2011-04-06 11:00:58 пишет:

Что значит "односторонним движением (каждый с каждым)"? Каждый город соединен со всеми другими, но при этом направление дорог неизвестно?

Админ: именно так

Добавьте комментарий:

Обсуждаем:

Реклама

© 2009 - 201х Логические задачи

Задачи на логику и сообразительность

Задачи

Данетки

Справочная

Реклама

задача: Дороги в Оптимайзии

Ответ

Решение задачи

Ваши ответы на задачу

Обсуждаем:

Реклама