Тема: Логические загадки - 6

[Mrrl›]

 Другая задача по сходной тематике (одна свободная задача в этой теме еще есть):

На плоской планете построен бесконечный город, состоящий из одинаковых квадратных кварталов, разделенных прямолинейными улицами. В этом городе заблудился дядя Вася. Он бродит по улицам, но вглубь кварталов не заходит. На поиски отправили трех милиционеров. Они могут двигаться по улицам с скоростью, не превышающей некоторой максимальной, которая одинакова для всех и про которую известно, что она больше скорости дяди Васи, но неизвестно, насколько. Как только милиционер окажется на одной улице с дядей Васей, он может позвать его и тот сам придет - на этом поиски будут закончены. Могут ли они его найти и как?

               

               

[aborgen›]

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

Задача из серии доказательств из курса матанализа, что такое-то множество является счетным(где надо занумеровать элементы). Как я только не извращался в своё время

               

               

[Mrrl›]

При таком алгоритме дядя Вася во-первых, легко проникнет в "просмотренную" зону: сначала, когда доин из углов смещается из (N,N) в (N+1,N+1), он прчется в точке (N+1/2,K), где K>N - тогда граница полубесконечного участка пройдет мимо него, а потом он перемещается в точку (N,K+1/2) и ждет, пока угло не переместится в (K+1,K+1). Правда, в процессе ему придется скрываться от М, пробегающих мимо.
Во-вторых, от может спокойно пойти зигзагами по диагонали, и его никогда не догонят. Тем более, что время работы алгоритма для М пропорционально N^2 для области N*N

               

               

[aborgen›]

Проникнуть внутрь не удастся, потому что если он попытается проникнуть внутрь, то он окажется между двумя соседними просматриваемыми улицами, и М просто может пробежать таким образом, чтобы просмотреть переулки, где Вася мог засесть.
А вот по поводу того, что Вася убежит - да, верно...

               

               

[Mrrl›]

Все равно сомневаюсь. Итак, M1 находится в точке (-A,-A) и нас пока не интересует. M2 находится в точке (B,B). M3 предполагает его сменить и встать в точке (B+1,B+1). Каким должен быть его маршрут, чтобы гарантировать, что дяди Васи нет во вновь захваченной зоне, и что он не проник туда во время маневров?

               

               

[aborgen›]

Мда, не совсем точно выходит, придется проверять после каждого недиагонального смещения, тогда нормально.

               

               

[Maeglor›]

Первое что приходит в голову Милиционерам нужно выстроится в ряд заняв 3 перекрестка в линию, после этого подождать время, достаточное дяде Васе для пересечения одного квартала (чтобы исключить возможность нахождения Васи в промежутке между переулками) Затем М1 и М2 начинают двигаться по улице мимо стоячего М3 до следующих перекрестков. М2 очевидно доходит до следующего перекр. когда М1=М3. М2 и М3 ждут положенное время пока М1 доходит до М2 и даже чуть-чуть дальше него.  далее М2 статичен М1 и М3 двигаются на следующие позиции. И так далее. Очевидно что Вася не сможет пересечь незамеченным милицейскую гребенку, правда сама гребенка будет двигаться со скоростью 3/4 Васиной и его в худшем случае просто не догонит.

Да и способ этот годится если Миллиционеры хотя-бы знают в какую сторону идти.

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

Но этот способ годится только если извесно предельное начальное расстояние между ментами и Васей.

А вообще для общего случая задачка неразрешима. Я наверное смог-бы даже это доказать.

А про луну до меня сейчас доперло. Астороном на луне может позвонить другу, живущему с ним на одной широте и попросить его взять угол  какой-нибудь близкой планеты. А затем, когда по его расчетам луна повернется настолько, что он окажется в том относительном времени, в котором делал измерения его друг, и получит совсем другое значение(засчет смещения луны по орбите земли на угол равный разнице в долготе между ним и его другом).

               

               

[Mrrl›]

Дядя Вася находится в таком состоянии, что вполне может устроиться у ближайшего киоска и проспать ближайшую пару тысячелетий. Или блуждать между двумя перекрестками. Так что "подождать время, достаточное дяде Васе для пересечения одного квартала" не получится.
  Ну и конечно, задача разрешима, даже если начальное расстояние и скорость неизвестны.
  Собственно, два из трех кусочков решения уже упоминались. Надо только понять, какие это, и свести вместе и додумать третий.

  Про Луну - не очень понимаю. Звонит он другу, спрашивает "Где Марс?" Тот отвечает "в двух минутах к западу от Антареса". Астроном смотрит на небо и говорит "Ага, по-моему там же". Через 1/4 лунных суток Марс улетает довольно далеко, при этом отклоняется от расчетной траектории, выполняя суточные колебания. И какой же был смысл в звонке?

               

               

[Арвинд›]

Напоминаю, что одновременно можно разгадывать до трех логических загадок.

Первая есть, хоть и в заглохшем состоянии.
Кидаю вторую. Мне ее загадали как очень сложно, а по-моему - ...
Но раз ничего столько времени не появляется, то давайте попробуем хотя бы этим реанимировать тему.

Итак, очередная задача на взвешивание.
Дано девять мешков с золотыми монетами.
Известно, что во всех мешках все монеты настоящие,
и только в одном - фальшивые.
Настоящие монеты весят 9 г, фальшивые - 10.
Необходимо указать, в каком мешке находятся фальшивые монеты,
за минимальное число взвешиваний.

Есть варианты:
1. Весы показывают точный вес одного груза.
2. Рычажные весы.

               

               

[Снорри›]

С рычажными - 2 взвешивания.
1.
слева - по 1 монете из мешков 1, 2 и 3
справа - по 1 монете из мешков 4, 5 и 6
Если какая-то чашка легче - дальше работаем с мешками, из которых взяли монеты для этой чашки.
Если равновесие - дальше работаем с мешками 7, 8 и 9.
В любом случае, остается только три мешка (А, Б и В).

2.
Слева - 1 монета из мешка А
Справа - 1 монета из мешка Б
Если какая-то монета легче - фальшивые монеты в мешке, из которого взяли эту монету, иначе - в мешке В.

               

               

[Арвинд›]

Цитата из: kidd 79ый on 04-10-2005, 14:37:53
С рычажными - 2 взвешивания.


Да, это просто.
Интересно было бы усложнить условия так, чтобы все равно двух взвешиваний хватало.
Но - если 10 мешков, то, кажется, за два взвешивания нельзя. Или?
Еще вариант - если мы не знаем, тяжелее фальшивая монета или легче?

Ну и с градуированными весами - как? Там тоже нетрудно совсем.

               

               

[Снорри›]

10 мешков - 2 взвешиваний не хватит, ИМХО, потому что:
1 взвешивание - не более трех групп (две чашки+невзвешиваемая групп).
За n взвешиваний можно, соответственно, обработать 3ⁿ мешков.
То есть три взвешивания - уже 27 мешков (три группы по 9 мешков, после первого взвешивания остается 9 мешков и два взвешивания, а это мы уже умеем).

Если неизвестно, легче или тяжелее фальшивка - уже сложнее, это я уже не потяну .

С весами, которые показывают вес (если фальшивка на 1 грамм меньше), кажется, можно вообще 1 взвешиванием обойтись

               

               

[Арвинд›]

Цитата из: kidd 79ый on 04-10-2005, 17:08:37
С весами, которые показывают вес (если фальшивка на 1 грамм меньше), кажется, можно вообще 1 взвешиванием обойтись

Да. Именно это казалось моему знакомому очень сложным 
Рассказывай.

               

               

[Снорри›]

Ну, пусть еще кто-нибудь подумает
Я тебе пока в приватку напишу.

               

               

[Mrrl›]

А можно ли определить за одно взвешивание и обойтись при этом меньше, чем 45 монетами?
вариант 1) Весы магазинные (с 2 чашками), но показывают вес с точностью до 1 грамма.
вариант 2) весы пружинные с 1 чашкой

               

               

[Mrrl›]

Упрощенный вариант про дядю Васю.
Он в очередной раз напился и заблудился в городе, но на этот раз город одномерный - в нем одна бесконечно длинная улица. Да плюс еще туман с утра - куда он пошел и далеко ли ушел, не видно.
  А в отделении милиции только один милиционер, способный стоять на ногах. Известно, что он двигается быстрее дяди Васи, но неизвестно, насколько. Сможет ли он его найти?

               

               

[Арвинд›]

Mrrl, там можно 9 монет из 45 выкинуть, вообще не задумываясь.  

В возможных расширениях задачи я думал о весах магазинных, но ничего красивого с ними не склалось.

Вот еще такой вопрос: мы помним задачу про К одинаковых монет с одной фальшивой - причем неизвестно,
легче она или тяжелее. Для взвешиваний на рычажных весах можно посчитать зависимость числа взвешиваний от К. А теперь у нас есть мешки. Можно ли найти какие-то лучшие решения по сравнению с отдельными монетами?
Варианты:
- Если мы знаем, в какую сторону и на сколько процентов по весу отличается фальшивая монета?
- Если не знаем, в какую сторону, но знаем, на сколько процентов?
- Если знаем только, в какую сторону?
- Если ничего этого не знаем?

Признаться, я на этот вопрос не отвечал. Было б интересно, если в какой-то из возможных
формулировок окажется нетривиальное по сравнению с одиночными монетами решение.

               

               

[Mrrl›]

Да, почему-то мне показалось, что мешков 10. Тогда было бы 45. Про магазинные весы с 10 решать проще, а вот если мешков 9... 21 монета?

               

               

[Maeglor›]

Ну 36 монет это очевидно.

И с одной чашкой пожалуй меньше не будет.

А вот магазинные весы...

20 монет.

Мент не найдет Дядю Васю. Единственный способ для него осматривать всю улицу это двигаться вперед-нзад увеличивая диапазон поиска на dх. В этом случае скорость порсмотра улицы падает порпорционально квадрату просмотренного расстояния. Так что если дядя вася идет со всех ног от участка найти его мент сможет лишь правильно выбрав направление поиска.




               

               

[Mrrl›]

20? Не верю. Не забывайте, что у магазинных весов нуль на краю шкалы, а не посередине.

Каждый раз увеличивать диапазон на dx - не единственный способ. Можно увеличивать его сразу в 10 раз. Но и в этом случае д.Вася может убежать.
Хотя решение есть.