"Логические задачи" - это познавательно-развлекательный проект для непрокисших мозгов. Задачи на логику, нестандартное мышление. Не всегда самое очевидное решение - правильное. Но иногда всё оказывается проще, чем кажется на первый взгляд.

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




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

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

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





запомнить меня
Зарегистрироваться


Задачи



Данетки


Текущие:

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

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

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


Справочная



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


Реклама






задача: Метро

Задачу прислал: Админ


Сложность: средняяВ городе Нью-Васюки 40 линий метро. Любые две линии пересекаются в единственной точке, образуя станцию – переход с одной линии на другую. При этом любая станция является пересечением ровно двух линий. При каком наибольшем k любые k станций метро можно закрыть на ремонт и при этом от любой работающей станции можно будет доехать до любой другой работающей (закрытие станции закрывает переход, но не работу соответствующих линий метро)?



Ответ





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





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


ответов: 10

KoKos 2017-11-20 04:09:06 пишет:
Кстати, Админ - жуткая тарабарщина Вадима на самом деле является совершенно верным математическим решением, если что. :) Без привычки читается с трудом, конечно, но менее верной от этого не становится.

jonson-72 2017-11-10 14:54:41 пишет:
ВКБЗ, твоего ника не упоминалось.

KoKos 2017-11-10 14:49:30 пишет:
jonson-72, а она и есть "только для грамотных". :)) "При каком наибольшем k любые k" - означает, что нельзя привязывать ответ к какому-либо конкретному выбору станций (другом прорабом). Если так понятнее - один игрок фиксирует k, а второй в пределах єтого k выбирает - естественно, стараясь как можно сильнее насолить первому. :) И всех делов-то.

jonson-72 2017-11-10 12:15:31 пишет:
ДАНО: 40 линий дают 780 станций (39 + 38 + ... + 1).
– АДМИН, и снова не вполне конкретное Условие, – непонятно Кто и По Какому Принципу закрывает станции метро на ремонт.
....Поэтому лично я не вижу, чем Ответ k = 778 (две оставшиеся станции находятся на одной линии) – НАИБОЛЕЕ благоприятный расклад (прораб ремонтников – наш друг:), – _хуже_ Ответа k = 75 – НАИМЕНЕЕ благоприятный расклад (прораб ремонтников – наш враг, или просто мизантроп:), – Условию, в данной формулировке, он НЕ противоречит: это ведь _реальная_предельная_цифра.

п.с. Мне кажется, при _случайном_ выборе, с точки зрения Теории Вероятностей ОБЕ ситуации очень и очень маловероятны, так что Задачу можно было бы и усложнить - сделав её "только для грамотных"...:).

(Цифра 75 – это количество станций, на одну меньшее, чем суммарное кол-во станций на двух линиях метро, пересекающихся в точке станции, которую злой прораб решил заблокировать.)

Вадим 2017-11-08 08:51:18 пишет:
Пусть A = a(i), i=1,..,40 - множество всех линий метро.
B = b(i,j), где i=1,..,39; j=i+1,..,40 - множество всех станций. Мощность этого множества 780.
Нам надо найти два подмножества множества B - C = c(i1,j1) и D = d(i2,j2), таких что:
1) для любого c(i1,j1) и любого d(i2,j2): i1<>i2, i1<>j2, j1<>i2, j1<>j2 (То есть нет такой станции из С, которая лежит на той же линии метро, что и станция из D);
2) сумма их мощностей максимальна.
Другими словами - это два подмножества станций, внутри которых человек может кататься на метро с невозможностью добраться до какой-либо станции второго подмножества (условие 1).
Пусть мощность области значений i1,j1 = x, где x = 2..38 (должно быть задействовано как минимум 2 линии метро). Тогда мощность области значений i2,j2 = 40-x. Найдем максимальное возможное кол-во станций (пар линий метро) в каждом подмножестве:
С: x! / (2!(x-2)!)
D: (40-x)! / (2!(40-x-2)!)
Согласно условию 2, их сумма должна быть максимальна:
0,5*x*(x-1)+0,5*(40-x)(39-x) -> max, где x=2..38
x^2-40x+780 -> max, где x=2..38
Максимум будет при x=2 или x=38. Сумма мощностей подмножеств 4-80+780=704. 780(всего станций)-704=76. То есть минимальное число закрытых станций, при которых возможен расклад, что с некоторой открытой станции нельзя добраться до другйо открытой - 76. Тогда 76-1 = 75 - это максимальное число станций, при котором мы в любом случае сможем добраться от одной открытой станции до другой.
Ответ 75.

KoKos 2017-11-05 02:50:07 пишет:
Можно, но это ничего особо не меняет - если мы полностью закроем все станции салатовой линии, например, то мы все равно продолжим преспокойно попадать с "Оранжево-Зеленово" на "Оранжево-Синево", ибо салатовая пересадка нам для этого не нужна - оранжевые поезда будут продолжать ходить мимо закрытой станции.

А n*(n-1)/2-1 - это уж слишком. 8)) Это закрыты ВСЕ станции, кроме одной, а по условию нам надо хотя бы две работающих. :)

R-2 2017-11-05 02:27:20 пишет:
И всеже, можнно ли закрыть 39 станций на одной линии? Тогда k = n*(n-1)/2-1.

KoKos 2017-11-05 02:25:22 пишет:
Можно. Вот примерно так: каждая линия пересекает каждую ровно один раз, ни в одной станции не пересекаются более двух линий. В этом примере станция "Оранжево-Салатово" выведена на ремонт, но это никак не мешает по оранжевой линии попадать со станции "Оранжево-Зеленово" на станцию "Оранжево-Синево". :)

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


R-2 2017-11-04 15:58:34 пишет:
koKos,а можно картинку? Потому что я ничего не понимаю. "При этом любая станция является пересечением ровно двух линий." Мой ответ: 1. Или 40, если можно закрывать линии.

KoKos 2017-11-03 11:51:11 пишет:
Похоже, что k=2*38-1=75 - если нам "повезет" с выбором любых станций, то 76ю мы можем полностью изолировать две линии, между которыми останется работающая пересадка, недоступная с других станций.

Меньшим количеством "дырок" достичь полной изоляции, мне кажется, нельзя, но строго это доказать я пока не готов. :))

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

Комментарий:

Пожалуйста, введите символы с картинки:
(подтверждение не требуется для зарегистрированных пользователей)



 





Обсуждаем

  Задача Кот ученый и мышка в норках:
K2 : [скрыто]
Задача Ириски из кармана:
K2 : [скрыто]
Задача Многопараллелепипедов:
K2 : [скрыто]
Задача Какой высоты стол:
K2 : [скрыто]
Задача Кирпич на пружинке:
Вася : [скрыто]
ivana2000: А нельзя ли по подробней?
Данетка Биометрические паспорта:
Сергей : [задал вопрос] -[нет]
Задача про животных:
Барсик Мяу : [решил задачу]
Задача Какой высоты стол:
R-2 : [скрыто]
Админ: можно взять среднеквадратичное или золотое сечение.
R-2 : [скрыто]
Админ: слабоватое обоснование
Задача Три подозреваемых:
Виталий : [скрыто]
Задача Какой высоты стол:
Виталий : [скрыто]
Задача 123456789:
не представился : [скрыто]
Админ: задачи добавляем по ссылке "добавить задачу". Ладно, сам перенесу :)
Задача Три подозреваемых:
Ирина : [скрыто]
Задача Какой высоты стол:
не представился : [скрыто]
Админ: неее
Задача Кирпич на пружинке:
ivana2000 : [скрыто]



Реклама



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