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

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

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

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

Поиск на сайте

запомнить меня

Задачи

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

Теорвер, комбинаторика

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

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

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

Детские с подковыркой

Данетки

Текущие:

  Мой любимый грех (с)
  Математика в архитектуре
  Не сыпь мне соль на рану
  «Геометрическая»
  Высказывание Ломоносова
  Наверное, не про яблоки
  Комерция
  Везде градусы
  Вагончик тронется, вагончик тронется..
  Спасибо медикам и католикам))
  Специальная купюра
  Студенческая смекалка
  Эллипс vs Круг
  Современные технологии. Немецкий стандарт.
  Спортивная
  философская
  Про газету
  печатная монета
  Купюра евро
  Древние изобретения
  Биометрические паспорта
  Новый глава
  В далеком созвездии тау Кита... 8)))
  Огородное
  Средневековое строительство
  Жестокое наказание
  Их нравы - 4
  Европейский стандарт

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

  этот модный тандыр
  Из Что-Где-Когда
  Может ли такое быть?
  Что изображено?
  Да на тебе пахать надо!

Справочная

Признаки делимости
Площади фигур

Реклама

Версия для смартфонов

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

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


+ 1 -

Ответ

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

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

ответов: 9

KoKos 2016-05-26 01:06:38 пишет:

Забавная. :)) Ну, возьмем в нашей Оптимайзии совершенно произвольный город А. Он делит всю страну на две части: все города, куда можно проехать из А (так и назовем Изайзия :) за одну поездку, и все остальные города - из которых, согласно условию, можно за одну поездку добраться в А (эту часть назовем Вайзия). Так вот, что мы имеем? Изайзия может быть какой угодно, хоть пустой - нас интересует только Вайзия. ;) Вайзия - это ровно такая же Оптимайзия, только чутка поменьше, как минимум на один город (сам А). Согласно предположению где-то в Вайзии существует город АА, из которого можно за две поездки добраться в любой другой город Вайзии. Также из него за одну поездку можно добраться в А - по построению, и за две поездки в любой город Изайзии - транзитом через А. Итого из города АА в Вайзии можно добраться за две поездки в любой город всей Оптимайзии... Но существует ли он? 8) Выбираем в Вайзии абсолютно произвольный город Б. ;))) Ровно тем же макаком теперь задача сводится к поиску нужного города в области Вбейзия, которая опять такая же Оптимайзия но уже не менее, чем на два города меньше. И так далее, пока очередная область Взюйзия не окажется пустой (и тогда город Зю есть искомый).

Tov Kronsteen 2016-05-25 18:12:04 пишет:

Допустим, нет города из которого можно попасть в любой другой в два переезда. Тогда для произвольного города А существует город С, в который из А за 1 или 2 переезда не попасть. У А число друзей(городов в которые из него можно попасть в 1 переезд) - N. Ни из одного из них нельзя попасть в С за один переезд(и из самого А тоже), иначе это противоречило бы условию. Тогда из С можно попасть во все N городов-друзей А, так как все города связаны напрямую однополосной дорогой. Плюс, по той же причине из С можно попасть в А. Значит число друзей С минимум N+1. Но для С можно найти такой город D, в который из него нельзя попасть в два хода, иначе из него можно попасть во все города. Но тогда число друзей D - N+2. И для него тоже можно найти такой город. Выходит рано или поздно найдётся город с количеством друзей равном количеству городов. Приходим к противоречию.

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 пишет:

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

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

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

Обсуждаем

Задача Разрезанный треугольник:
http://lprobs.ru/img/yes.gif : [скрыто]
Гостевая книга:
не представился : Это было в 1913 году. Одиннадцатилетняя девочка, пансионерка Московской Ржевской гимназии очень прос...
Задача Гора.:
Xuzke : [скрыто]
Гостевая книга:
не представился : В школе все казалось правильным. Из математики следует физика, из физики следует химия, из химии сле...
R-2 : Ты решил: Ну, и наконец, то решение, которое тут видимо предполагается в идеале, я не буду говори...
Так, по старой памяти заглянул :) : R-2, условие неплохо бы конкретизировать. ;)) А то так вариантов может быть масса, хотя все обладают...
Задача 4 хода:
колд : [скрыто]
Задача Кот и мышка:
Дмитрий : [скрыто]
Задача Черная Жемчужина:
mskfirst : [скрыто]
Задача Квадратный торт:
не представился : [скрыто]
Задача Задача с ведрами: 9 и 4 = 6.:
ИносОйЧанбин : [скрыто]
Дкгк7 : [скрыто]
Задача Геометрическая 3:
не представился : [скрыто]
Алексей : [скрыто]
Гостевая книга:
R-2 : Дано: листочек бумаги и ручка. На листочке написаны три нуля. О О О Задача: «как из трёх нулей...

Реклама

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

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

Поиск на сайте

Задачи

Данетки

Справочная

Реклама

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

Ответ

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

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

Обсуждаем

Реклама