 106 | Trianon | 6/26/2001 1:34:03 AM | Салли --> (104)
Встречный вопрос!
Почему-то все акцентируют, что, легче монета или тяжелее - неизвестно.
Какое значение мог бы иметь факт знания, в какую сторону отличается вес "неправильной" монеты?
|
 105 | Циник | 6/25/2001 8:18:10 PM | Салли --> (104) Эта задачка уже рассматривалась как-то тут, в другой конфе с логическими задачами. Первым тогда предложил правильное решение, кажется, Le...
|
| 104 | Салли | 6/25/2001 1:36:50 PM | (складывает обрывки проводов в дырявое ведро и забрасывает все в шахту. Туда же летят перегоревшие лампочки)
А теперь задачка для девочек, без проводов. Но и мальчики могут порешать, на пляже где-нибудь…
Есть 12 монет, одна из них имеет отличный от остальных вес, но неизвестно(!), тяжелее она остальных или легче. Есть весы-уточки ( такие вот - ***V*** - без шкалы, без гирь). Требуется за 3 взвешивания найти эту монету.
Ответы пишите лучше мне на почту, а потом я решение здесь латиницей набью, чтобы ответ раньше задачи в глаза не бросался
|
 103 | Trianon | 3/15/2001 6:59:01 PM | Циник --> (102) - Здесь рассматриваются логические задачи или лингвистические?
Логические.
Каков вопрос - таков ответ.
...
Заметь, я не протестую против твоего решения. Просто его описание было, как бы ты выразился, "совершенно некорректно".
|
| 102 | Циник | 3/15/2001 6:23:29 PM | ±MNNN Нелюбимый Кот --> (100) Мало ли, что изящное. Ты парень доверчивый, ошибку можешь и не заметить... :)
Trianon --> (101) "Как-то плохо звучит слово "нумерация"" - Здесь рассматриваются логические задачи или лингвистические?
|
| 101 | Trianon | 3/15/2001 5:11:59 PM | Циник --> (99) Как-то плохо звучит слово "нумерация", если оную повторяют несколько раз с разных сторон, и ни одну (кроме последней) в конечном итоге не используют. Я бы назвал этот процесс не нумерацией, а распределением по группам. Это - подсказка. :-)
|
| 100 | ±MNNN Нелюбимый Кот | 3/15/2001 4:52:56 PM | Циник --> (97)
Отбрось сомнения, оно есть. Изящное очень. Могу положить все четыре лапы и хвост впридачу. Я даже в верном направлении думал - но - увы и ах - недодумал... :о)))))))
|
| 99 | Циник | 3/15/2001 4:29:42 PM | Trianon --> (98) Для этого на стороне В провода нумеруются по новой, но так, чтобы уже выявленные четные провода оставались четными. Провода, имеющие 1 во втором разряде, соединяются между собой, после чего - бегом на сторону А. Там снимаем ранее поставленное соединение и уже в новой, данной на стороне В, нумерации получаем второй разряд. Нумеруем снова, замыкаем в соответствии с 3-м разрядом новой нумерации и т.д.
Для N=10 надо в общем случае пробежаться 4 раза.
|
| 98 | Trianon | 3/15/2001 3:40:04 PM | Циник --> (97) А можно поподробнее?
с первым шагом все ясно. Нумеруешь провода на стороне А. Замыкаешь нечетные нс стороне А. На Стороне В ты получаешь два пучка проводов с четными и с нечетными номерами стороны А.
Как ты будешь определять на стороне В - какие провода имеют единицу во втором разряде номера стороны А?
|
| 97 | Циник | 3/15/2001 2:34:13 PM | Trianon --> (96) Ну хорошо, если можно работать с тестером только на одной стороне кабеля, то решение с небольшими изменениями тоже проходит:
соединяются между собой проводки, имеющие единицу в 1-м разряде, а затем на другом конце кабеля выявляется, какие проводки между собой соединены. На это, правла, потребуется несколько больше проб, поскольку надо еще выявить первый из замкнутых проводков. точно так же выявмит 2-й разряд и т.д.
Впрочем, в уточненной постановке задача решается проще; решение предложенное Котом проходит. При его решении для N=10 требуется действительно 3 перехода.
А вот относительно того, что имеется решение с тремя переходами для произвольного N, - у меня имеются серьезные сомнения...
|
| 96 | Trianon | 3/15/2001 1:53:24 PM | Циник --> (95)
Возможно, я недостаточно четко сформулировал условие. Попытаюсь пояснить, что я имел в виду.
1. "В первую очередь учесть сильный критерий, а затем слабый" означает, что если оценки сложности решений по сильному критерию совпадают, то сравниваются оценки по следующему (слабому) критерию. Если они отличаются - все более слабые критерии просто не берут в расчет.
Конечно, это лишь одна из возможных функций цены решения. И даже, возможно, не самая практичная. Предложи другую - и попробуем поглядеть на задачу под другим углом. Тем более, что задач, мягко говоря, "негусто" :-)
2. В принципе - достаточно найти решение. Любое.
Но если есть несколько - то я указал критерии, по которым я стал бы эти решения сравнивать.
Что касается доказательства удовлетворения критерию - замечательно, если оно есть, и ничего страшного если его нету. В конце концов, я же не объявлял вознаграждений, не устанавливал призовой фонд и т.п.
По поводу решения - увы, не пойдет. Нарушение в п.4. Разрешалось проверять любые две точки на замыкание на любой из сторон. Но не между сторонами. Проводок от тестера - лопнет, пока ты будешь бежать из одного конца кабеля в другой.
На самом деле, это красивое решение, но от другой задачи - когда есть еще один контрольный провод. Возможно, стоит порешать и ее.
Но, в любом случае, спасибо за участие!
|
| 95 | Циник | 3/15/2001 12:33:13 PM | Trianon --> (83) Задача поставлена совершенно некорректно:
1. Что значит "В первую очередь минимизировать то, во вторую - это, а в третью - вон то"? А если имеется решение с большим выишрышем по третьему критерию, но с небольшим проигрышем по первому? В задачах такого рода обычно стоит один вопрос/критерий.
2. Что значит вообще "минимизировать", "найти минимум"? Найти какое-то решение и при этом доказать, что всякое другое решение будет хуже?
Вот одно из решений, при котором число перемещений очень медленно (как логарифм) растет с числом проводов.
1. Пронумеровать все N проводков на конце кабеля, представив номер в двоичной системе.
2. Соединить между собой на конце кабеля все проводки, имеющие в своем двоичном номере 1 в 1-м разряде.
3. Соединить контакт тестера с соедининными проводками.
4. Перебежать с тестером к противоположному концу кабеля и проверить там у всех проводов наличие наличие контакта. Номера проводов, у которых имеется контакт, имеют в своем двоичном предствалении 1 в 1-м разряде, остальные - 0.
5. Повторить пп. 1-4 для остальных разрядов, считая, что значение 1-го (а впоследствии также и 2-го, 3-го и т.д.) разряда уже установлено. Перед проведением теста на наличие контакта ранее установленные соединения проводков надо, разумеется, снять.
В итоге концы проводов, имеющие одинаковые номера на разных концах кабеля, будут соответствовать друг другу.
Для случая N=10 (так же как и для N=11, 12,...,16) потребуется 4 перемещения (2 туда, 2 обратно).
|
| 94 | ±MNNN Нелюбимый Кот | 3/7/2001 2:06:23 PM | Trianon --> (93)
С факториалом R!=N я похоже погорячился... :о))) Идея всё так же - три проводка идентифицирутся легко... Задача сводится к последовательному уменьшению количества проводов в пучке до 3х... За каждый проход происходит разбиение одного пучка на группы 1,2,3,...,R с последующей идентификацией каждой группы. Количество групп m - количество членов в сумме арифметической прогрессии с результатом суммы в N. Это равно m=(2*N/(R+1))-1. Ну и все факториалы в (88) на такое безобразие заменить надо... :о)
-----------------------------
Trianon --> (92)
Ну можно за три прохода определить, согласен... :о)
|
| 93 | Trianon | 3/7/2001 11:18:21 AM | ±MNNN Нелюбимый Кот --> (88)
Я попытался применить твой способ, и понял... что ничего не понял.
Допустим N=120. R! = N ==> R = 5.
А что дальше делать?
|
| 92 | Trianon | 3/7/2001 10:59:47 AM | ±MNNN Нелюбимый Кот --> (91)... Если там есть логическая дырка - я её найду.. ;о)
Не нашел...
|
| 91 | ±MNNN Нелюбимый Кот | 3/6/2001 4:44:54 PM | Trianon --> (90)
Ну здрасти, так неинтересно... :о))) Не описывать-то... Если не хо всем писать - скинь его мне тогда по Отельской почте... :о))) Заодно и проверим... Если там есть логическая дырка - я её найду.. ;о)
|
| 90 | Trianon | 3/6/2001 3:15:38 PM | ±MNNN Нелюбимый Кот --> (88) Сейчас начну занудствовать.
Пробник представляет из себя именно то, что ты думал. "Батарейку" и "лампочку", которая строго одинаково горит независимо от того, включили ее через два провода жгута или через все 100000 последовательно.
Провода представлют из себя то, что ты описал: Провода идеальные - сопротивление провода нулевое, проводимость изоляции нулевая, емкость между проводниками нулевая, взаимная индукция отсутствует.
Перемещение представляет из себя именно то, что ты описал. Из А в В. Либо из В в А. За тем исключением, что строго вдоль жгута идти нельзя (в кабельный канал не пролезть)... так что пальчиками наощупь проводки не проследить. Жгут может лежать в траншее, а двигаться придется, допустим, на троллейбусе пару остановок. :))
±MNNN Нелюбимый Кот --> (89) Нет. Я имел в виду именно ТРИ максимум для любого N и ДВА для 3, 6, 10, 15, 21, 28 и т.д. проводков.
Мое решение НЕрекурсивное. Описывать пока не хочу по двум причинам. а) вдруг еще кто порешать захочет и б) вдруг я наврал.... ща буду проверять.
|
| 89 | ±MNNN Нелюбимый Кот | 3/6/2001 2:22:18 PM | Trianon --> (87) ±MNNN Нелюбимый Кот --> (88)
Так... Я, кажется, стормозил... Под тремя перемещениями видимо имелось ввиду решение для 10 проводов в жгуте... Для случая N над полагать число перемещений в решении (87) будет равно i, где N=(i*i+i)/2. Порядок(i) = sqrt(N) *квадратный корень из N*... Моя схема (88) круче... Факториал, однако... ;о))))
-------------
Кстати, под перемещением я лично понимаю переход от конца А в конец B. Обратный переход - это второе перемещение. :о)
|
| 88 | ±MNNN Нелюбимый Кот | 3/6/2001 2:08:25 PM | Trianon --> (87)
Гм... Интересно... Распиши тогда, что из себя представляет тот самый пробник. Пока я лично представлял себе его как лампочку с батарейкой. В качестве проводов рассматривались только провода проложенного жгута, в начальный момент нигде не замкнутые... :о) Потому как очень интересно, как за три прохода вдоль провода можно идентифицировать все проводки, если, скажем в жгуте их N=100000. :о)
---------------
Лучшее решение которое у меня сейчас есть - это последовательное разбитие всего жгута на комбинации (кусты) по кол-ву проводов: 1,2,3,...,R, где R!=N и идентификация после перехода каждого куста. Далее операция рекурсивно повторяется для подкустов. Порядок количества переходов m определяется из следующего соотношения:
((...((2)!)!...)!)!=N
|{---- m раз ----}|
Количество замыканий и проб тоже можно оценить. :о) Но честно говоря, лениво... :о)))
|
 87 | Trianon | 3/6/2001 12:02:58 PM | ±MNNN Нелюбимый Кот --> (86)
Само собой, если N = 2 - задача неразрешима, а если N < 2 - вырожена. Так что считаем N > 2.
Я вроде нашел решение, позволяющее за три перемещения выполнить задачу в общем случае, и за два перемещения - в частном, когда N=(i*i+i)/2, где i - целое число.
Десять - совершенно случайно :)) как раз тот самый частный случай: 10 = (4*4+4)/2
|
| 86 | ±MNNN Нелюбимый Кот | 3/5/2001 12:23:23 AM | Trianon --> (83)
Для N (N>2) проводков существует решение, позволяющее за (N-1) перемещение себя однозначно идентифицировать все проводки. Если надо - могу расписать, но оно тривиально - строится единая цепь, за каждое перемещение идентифицируется один сегмент и подключается следующий неизвестный... Порядок количества замыканий - N, количества проб - N!
Вопрос в том, можно ли эту схему оптимизировать... Подумаем...
|
| 85 | ±MNNN Нелюбимый Кот | 3/5/2001 12:02:01 AM | Trianon --> (83)
Для 2х проводков задача решения не имеет - не получится с помощью указанных инструментов идентифицировать конкретный проводок... :о)
|
| 84 | ALEX_B | 3/4/2001 11:57:34 PM | Trianon --> (82) для (69) как и (63) у меня есть лишь свои варианты :) возможно верные а возможно есть в природе еще более верные :))) Так что пока без ответа :))
|
| 83 | Trianon | 3/4/2001 9:45:05 AM | Нелогично... Ок. Вот практическая задача, которую я попробую сформулировать возможно более строго.
Из точки A точку B проложен жгут проводов.
Допустим, 10 штук (кто хочет, пусть решает для N).
Затратив минимум времени, нужно установить соответствие (т. е. какой проводок на стороне B является проводком 1, 2...N на стороне A) имея в руках примитивный пробник, т.е. прибор, позволяющий определить, замкнуты ли два проводка или нет. Разрешено бегать из A в B и наоборот, замыкать/размыкать любые проводки на любой из сторон, проверять любые две точки на замыкание на любой из сторон. Но поскольку расстояние от A до B довольно велико, то в первую очередь надо минимизировать число перемещений себя туда сюда. В вторую - число замыканий/размыканий. В третью - число проб.
Заранее предупреждаю, что ответа у меня сейчас нет, так что я буду ломать голову наравне со всеми.
|
| 82 | Trianon | 3/4/2001 9:16:22 AM | ALEX_B --> (68) Правильный ответ будет оглашен?
Что-то мне эта задача напомнила сборку "калашникова".
|
|
|