Логические задачи : Метро

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

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

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

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

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

Задачи

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

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

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

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

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

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

Данетки

Текущие:

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

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

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

Справочная

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

Реклама

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

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

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

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


+ 2 -

Ответ

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

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

ответов: 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ю мы можем полностью изолировать две линии, между которыми останется работающая пересадка, недоступная с других станций.

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

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

Обсуждаем

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

Реклама

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

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

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

Задачи

Данетки

Справочная

Реклама

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

Ответ

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

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

Обсуждаем

Реклама