Бывает находит на нашу компашку стих головоломку решать какую-нибудь,
если кто притащит. Недавно вот добрый человек подкинул задачку. Типа
есть 8 шариков, выглядят одинаково. Из них один бракованный, весит не
столько же, сколько остальные. И есть весы без гирек, классические весы
с лабораторной по физике, с двумя чашечками. Надо за 3 взвешивания найти
бракованный шарик и определить, тяжелее он или легче остальных.
Мучаемся, значит, думаем. И тут Даша грустно так говорит: "Не могу я эту
задачку решить. Я как эти весы представляю, шарики все время с чашек
падают...". С кубиками решила моментально.
Статистика голосований по странам
Чтобы оставить комментарии, необходимо авторизоваться. За оскорбления и спам - бан.
92 комментария, показывать
сначала новые
сначала новыесначала старыесначала лучшиеновые - список
Jhon Silver• 21.12.12 18:24
Это же элементарно!))) Но в три захода не уложиться...
Кладем на каждую чашку весов по 4 шарика. Одна из чашек перевешивает, ее содержимое делим пополам и кладем на обе чашки весов. Если чашки уравновесились, то это не те шарики))) Берем вторую партию и ее пополам делим - по 2 шарика на чашку. И смотрим где перевесило - ту часть еще раз пополам и остается всего по одному шарику на каждой чашке. Берем тот что перевесил и сравниваем его с любым из отброшенных. Если он перевесил то это он! А если вес одинаковый то тот который оказался легче в предыдущем взвешивании.
+0–
ответить
Наташа• 01.11.10 21:39
Точь в точь такая же задача,думала тут решение найти(((Если завтра расскажут,как решать-выложу обязательно!
+0–
ответить
Ash390480394850349• 22.12.09 18:01
Гена, прочитай условие задачи еще раз и не путай людей. 2 взвешивания имеют 9 возможных исходов которыми ты предлагаеш выбрать один из 16 возможных ответов.
В твоей задаче нужно знать легче или тяжелее бракованный шарик.
+0–
ответить
Геннадий• 23.01.08 15:00
Умники! А решите-ка задачку на тех же условиях, но только шариков не 8, а 12. Или нет. Решите-ка ту же задачку за два взвешивания. Задача имеет решение в действительных числах.
Из истории. Эту задачу задавали кандидату на должность младшего египетского жреца, после чего его изолировали, чтобы исключить возможность подсказки, на трое суток. Он должен был решить ее в уме, а по истечении срока продемонстрировать решение. А вам слабо?
За 10 лет я задавал ее многим людям, никто не смог ее решить.
+0–
ответить
Сергей.• 18.01.08 20:59
User и Alexey <<a href="mailto:[email protected]">[email protected]</a>>, спасибо огромное! Великолепное решение в обоих случаях! Хотя вариант у User дает шанс на скорейшее решение алгоритма, при везении, конечно! Приятно увидеть здесь действительно умных людей. Потому как чуть было не забросил читать комментарии из-за избытка мата, пошлости и глупости тех, кто больше ни на что не способен. Но теперь снова стану с удовольствием заходить в обсуждение.
С благодарностью,
+0–
ответить
fedorq• 31.12.07 15:56
Ой. На самом деле эта задачка становится разумной с 13 шариками из которых один фальшивый (легче или тяжелее) и 3 взвешиваниями на чашечных весах. Она решаема.
+0–
ответить
Чертик• 23.12.07 17:01
to Eraser, Владимир, Андрей
ну приведите же решение за 2 хода! Настаиваю, что условия задачи корректны: 8 шариков, 3 хода и неизвестно, тяжелее или легче бракованный
+0–
ответить
тольок• 22.12.07 06:44
to Eraser: КГ/АМ
...вы не только читать не умеете, но и излагать собственные мысли. Вы страдаете дислексией и мысли отстают от выражения (синдром Буша), принятие информации из внешнего мира заблокировано. Вам не задачи задавать надо и излагать примитивные мысли, а тренировать внимание и пытаться осознавать внешнюю информацию. Не удивительно, что один ваш европейский коллега (хоть он неплохой теоретик) не понял решения именно потому, что вы ему о нем рассказали...
Ваша задача "абсолютнА НЕ корректна"... всей необходимой для ее решения информация нет. Вообще это не задача, а протоколы сионистких мудрецов, ну или сказка для маленьких детишек на ночь. Она вообще противоречива - мудрецы задали своим женам по одному вопросу(?)(каких?- на который ответ может быть Да/Нет??). После этого мудрецы ни с кем не общались и не получали никакой иной информации(?) ... а далее - такое событие как убийство не осталось бы незамеченным, так значит всЈ-таки получали-замечали?... задача примитивна и избита (задача о монахах с пятном на лбу(ориг.) и т.д.), к тому же и переврана и с ч_удацким, сразу дающим ответ, вопросом - по сути вы хотели сказать - каждый муж знает о жЈнах всех других, кроме своей. Кроме этого он знает, что все знают, что есть хотя бы одна неверная жена. Каждое утро он узнаЈт сколько было убито жЈн. Решение примитивно - если одна - то она будет убита в этот же день, если две - то через день будут убиты две и т.д. если 5 то известие о их убийстве будет известно на 5 утро...
+0–
ответить
Простой главный бухгалтер• 22.12.07 00:45
Спасибо автору за интересную задачу. Получили удовольсвие. Спасибо Userу за идеальный алгоритм.
+0–
ответить
Eraser• 22.12.07 00:25
Наверное начинаю стареть - почитал другие отзывы и ужаснулся.
На самом деле, "добрый человек" некорректно сформулировал задачу. Если заложить что один из шариков легче или тяжелее, то задача легко решается в два хода. На каждую чащечку кладется по три шарика. Если весы остаются в равновесии, то переходим к оставшимся двум - два хода. Если какая-то тройка весит меньше (больше) берем ее и взвешиваем два шарика. Весы в равновесии - бракован третий шарик, нет - какой-то из этих двух. Два хода.
Это задача простая, я лучше дам посложнее. Один мой европейский коллега, вообще-то он неплохой теоретик, не понял решения даже когда ему о нем рассказали.
В одной стране мудрецы одного города поехали на совещание. На обратном пути они узнали что по крайней мере одна из жен была неверна. По законам этой страны, муж обязан убить неверную жену чтобы не погубить свою репутацию. По возвращению домой, мудрецы задали своим женам по одному вопросу. После этого мудрецы ни с кем не общались и не получали никакой иной информации. Город был относительно небольшим и такое событие как убийство не осталось бы незамеченным. На пятый день, местная газета сообщила что N мудрецов убили своих неверных жен. Вопрос: сколько жен были неверными?
По условиям задачи, жены дают достовреную информацию обо всех женах, исключая самих себя для неверных жен (иначе это было бы самоубийством). По определению, мудрецы не прнимают неверных решений, т.е. верная жена не будет убита.
Задача абсолютна корректна, вся необходимая для ее решения информация есть.
+0–
ответить
тольок• 22.12.07 00:10
to Eraser:
...не надо так много курить да и не напрягайся - думать всЈ равно может только тольок.Не для тебя это... потому как вообще достаточно одного взвещивания - надо просто взвесить каждый шарик только один раз
+0–
ответить
тольок• 22.12.07 00:06
to Eraser
...не надо так много курить да и не напрягайся - думать всЈ равно может только тольок. Не для тебя это...
+0–
ответить
Eraser• 21.12.07 23:51
Классная история! Самое смешное в ней то, что бракованный шарик можно определить за два(!) взвешивания - это классическая задача. Думать над решением задачи с тремя взвешиванями может тольок ... Смеяться над чужой глупостью нехорошо, но раз люди сами этим так гордятся...
Как сказал один мой знакомый: "Писать книги хорошо, плохо то что написанная тобой книга может стать распиской в собственной глупости".
+0–
ответить
Пацан-хулиган• 21.12.07 22:10
Вот придурки!
Напоминаю, вечер пятницы. Что это значит?
Это значит, что шары надо не взвешивать, не катать, не лизать, а ЗАЛИВАТЬ! Чтоб потом не было обидно за бездарно убитый пятничный вечер.
+0–
ответить
User• 21.12.07 21:04
По-любому надо 3 взвешивания, в первых двух из которых совпадает одна пара.
12=34 -> сравниваем 12 и 56, если различаются - глюк в 56, иначе глюк в 78.
12<>34 -> опять сравниваем 12 и 56, если снова различаются - глюк в 12, иначе в 34.
Последнее взвешивание - берем один шарик из глючной пары и один из неглючной, если различаются - глючный шарик только что взвешивали, иначе это тот из пары, который оставили.
За 2 взвешивания ни при каких обстоятельствах задача не решается, т.к. мы не знаем, легче глюк или тяжелее. В принципе за 1 ход определяется глючная четверка, за 2 - пара, за 3 - шарик. Для 16 шариков нужно 4 взвешивания, для 32 5 и так далее.
+0–
ответить
:)• 21.12.07 19:17
Владимир + андрей
задача не решается за 2 взвешивания. Вам неизвестно, тяжелее бракованый шарик или легче остальных.
Програмист прав - если повезет - 2 взвешивания, если нет - 3. Я думаю, Владимир и андрей причисляют себя к числу везучих людей.
+0–
ответить
Сибиряк• 21.12.07 17:19
2 ГигаNT
>Пора, наверное, идти пиво пить.
Ну наконец-то первая здравая мысль среди всех сегодняшних сообщений :)
Одобряю и поддерживаю :)
+0–
ответить
ГигаNT• 21.12.07 16:59
/Нет, чашечки не различаю. Да и как их можно различить? Система абсолютно симметричная.
Точно. Чето я глючить начал. Пора, наверное, идти пиво пить.
+0–
ответить
Сибиряк• 21.12.07 16:24
2 ГигаNT
> Понял, в чем прикол алгоритма. Вы различаете чашечки весов.
Нет, чашечки не различаю. Да и как их можно различить? Система абсолютно симметричная.
+0–
ответить
ГигаNT• 21.12.07 16:14
/Хм... Ниже алгоритм приведен для 13. Однако 13 > 9
Сибиряк
Понял, в чем прикол алгоритма. Вы различаете чашечки весов. Наверное это правомерно, так как в условии задачи не сказано, что этого делать нельзя
+0–
ответить
программист• 21.12.07 15:48
to: Владимир + андрей
приведите решение ?
// решается за 2-3 хода - как повезет...
+0–
ответить
программист• 21.12.07 15:24
to: vto
ок спасибо... чет я пропарил по утру :)
но в любом случае это задачка не для детей...
+0–
ответить
Ассистент.• 21.12.07 15:23
Парами надо взвешивать.
На одну чашку шары №1 и №2, на другую №3 и №4.
Если весы уравнялись - все стандартные. Убираем, например, №1 и №2.
Сравниваем №3 и №4 с №5 и №6. Допустим весы уравнялись, значит №№1-6 эталонные. Сраниваем один из них с шаром №7. Весы уравнялись - бракованный №8, не уравнялись - №7. Так же брак можно поймать и на любом из предыдущих взвешиваний.
+0–
ответить
Стадо Дятлов• 21.12.07 15:09
Для деффачки-припевачкЫ: пойдем! У меня как раз хата свободна! Куда заехать за тобой, потрахушка?
+0–
ответить
Большой ПЈс• 21.12.07 14:54
Якс
Не играю в квесты, поэтому пронумеровал шарики, и тогда понял. Алгоритм работает, но как доперли что именно такая выборка?
+0–
ответить
Alexey• 21.12.07 14:35
касательно головоломки
кладем 3 и 3
если вес одинаковый 2-х взвешиваний достаточно найти неправильный шар из оставшихся двух путем сравнения с правильным (любым из шести)
если вес разный, берем 3 шара что тяжелее, добавляем один из 2-х правильных, кладем 2 и 2
если тяжелее пара с правильным, ответ очевиден, если тяжелее два других, находим среди них более тяжелый, если вес одинаков, неправильный - легкий среди оставшихся трех
кладем один из них на одну чашу, второй на другую, если вес равен, оставшийся шар искомый более легкий, или мы увидим, какой легче
+0–
ответить
ГигаNT• 21.12.07 13:56
/Я задачку с зЈрнами и мешочками тоже никак не мог решить.
А вот представил себе 5 банков, где хранятся золотые монеты, причЈм известно, что в каком то банке они фальшивые и весят легче(или больше) и надо за одно взвешивание на электронных весах определить фальшивые. И мнгновенно решил.
(для тех кто в танке: берЈм в каждом банке кредит, в первом банке одну монету, во втором две и т.д., всЈ вместе ложим на весы, смотрим на результат измерения, считаем, определяем)
Не, так не пойдет. Нужно точно знать, насколько легче или тяжелее. Тут нужно дейтвовать по другому. Прийти в банк и попросить кредит в миллион басов под залог квартиры стоимостью в 100 000 баксов. Где дадут, там и фальшивые.
+0–
ответить
ГигаNT• 21.12.07 13:52
/Хм... Ниже алгоритм приведен для 13. Однако 13 > 9
Попробовал разобратся в вашем алгоритме. Вроде все правильно. Понравилось.
+0–
ответить
Сибиряк• 21.12.07 13:44
2 Якс
Спасибо за алгоритм. Я как раз стал думать в направлении такого подхода, но теперь можно не напрягаться :)
Проверил - алгоритм действительно работает, так что тему про 12 шаров можно закрывать. Вот Мефодий-то обрадуется :)
+0–
ответить
1) 4 + 4. Одна кучка тяжелее, одна легче. В задаче сказано, что не отличается вес. Выбираем ту, что тяжелее
2) 2 + 2. Если вес одинаковый, то пиздец. Одного взвешивания не хватило. Если разный, значит мы угадали и бракованный шарик тяжелее.
3) 1 + 1. Выбираем из двух тот, что тяжелее.
Не хватает начальных условий.
+0–
ответить
Чупс&Гэг• 21.12.07 13:33
2 Чертик
Я задачку с зЈрнами и мешочками тоже никак не мог решить.
А вот представил себе 5 банков, где хранятся золотые монеты, причЈм известно, что в каком то банке они фальшивые и весят легче(или больше) и надо за одно взвешивание на электронных весах определить фальшивые. И мнгновенно решил.
(для тех кто в танке: берЈм в каждом банке кредит, в первом банке одну монету, во втором две и т.д., всЈ вместе ложим на весы, смотрим на результат измерения, считаем, определяем)
+0–
ответить
ГигаNT• 21.12.07 13:28
/Для n=3 задача решается за 2 взвешивания, а для n=2 задача вообще не решается
И правда. Но n=2 - очевидно особый случай, когда правиьность шаров определить невозможно принципиально. Его надо рассматривать отдельно.
+0–
ответить
Якс• 21.12.07 13:27
Для 12-ти решается... Даже в квестах такое есть.
(взято с htt p://questzone.ru/sol3/jce_2.shtml)
Вот оно, решение:
"3.6 Взвешивание 12 монет
Q: У Вас есть 12 монет, одна из которых фальшивая и она либо легче, либо тяжелее настоящей. Как с помощью трЈх взвешиваний балансировочных весах (которые показывают больше-меньше) определить фальшивую монету и то, легче она или тяжелей настоящей?
A: Решений много. Как мне кажется, приведенное здесь - одно из самых коротких. Обозначим монеты следующим образом: FAKE MIND CLOT. Взвешиваем одну четверку против другой (буквы обозначают монеты, входящие в каждую четверку):
MA DO - LIKE, ME TO - FIND, FAKE - COIN. Теперь совершенно просто найти фальшивую монету: к примеру, если результаты взвешивания были: слева легче, равно, слева легче, то фальшивой может быть только монета "A", которая легче других."
+0–
ответить
Сибиряк• 21.12.07 13:25
2 ГигаNT
> максимум шаров, для которой такая задача решается - 9
Хм... Ниже алгоритм приведен для 13. Однако 13 > 9
+0–
ответить
Сибиряк• 21.12.07 13:22
2 Мефодий
> Большое спасибо за алгоритмы. Я уже около года ищу способ
> для 12 шариков за 3 взвешивания, если неизвестно, тяжелее
> бракованный или легче.
За что спасибо-то? Приведенный алгоритм работает для 13 шариков, а для 12 точно не работет. И не понятно - есть ли другой алгоритм, который решит задачу для 12. Что-то мне подсказывает, что для 12 все-таки решить не удастся.
+0–
ответить
ГигаNT• 21.12.07 13:17
/Большое спасибо за алгоритмы. Я уже около года ищу способ для 12 шариков за 3 взвешивания, если неизвестно, тяжелее бракованный или легче.
Мефодий, а в рамках какого научного проекта вы решаете эту проблему? В каком заведении? Я тоже туда хочу, если платят нормально, естественно. А если серьезно, не занимайтесь херней, максимум шаров, для которой такая задача решается - 9.
+0–
ответить
Сибиряк• 21.12.07 13:14
2 ГигаNT
> Если они уравновешиваются, то вы имеете 8 правильных шаров.
> Если нет, то 5 оставшихся. Откуда 4?
Ну мы же сейчас обсуждаем задачу с 12 шарами, значит будет не 5 оставшихся, а только 4.
+0–
ответить
Сибиряк• 21.12.07 13:12
2 ГигаNT
> Тут кто-то хотел привести пример задачи, котрая решается
> для n шаров, но не решается для n-1? Плз.
Вот один из примеров:
Есть n шаров, один из бракованный и непонятно - легче он или тяжелее. Можно их взвешивать неограниченное число раз. (Других шаров у нас нет)
Для n=3 задача решается за 2 взвешивания, а для n=2 задача вообще не решается.
+0–
ответить
ГигаNT• 21.12.07 13:10
/Замечу, что для 12 шаров по достижении пункта 1.2 мы получим группу однозначно правильных шаров в количестве 4 штук. А для пункта 1.2 нам надо 5 правильных шаров, иначе алгоритм перестает работать.
Чета я не понял. При первом взвешивании вы кладете на весы 8 шаров по 4 на чашку. Если они уравновешиваются, то вы имеете 8 правильных шаров. Если нет, то 5 оставшихся. Откуда 4?
+0–
ответить
девочка-припевочка • 21.12.07 13:09
Ой, что-то я сегодня добрая... и настроение такое романтичное... Никто не хочет потрахаться?
+0–
ответить
Мефодий• 21.12.07 13:05
Сибиряк и vto
Большое спасибо за алгоритмы. Я уже около года ищу способ для 12 шариков за 3 взвешивания, если неизвестно, тяжелее бракованный или легче.
+0–
ответить
Нановася• 21.12.07 13:05
ВсЈ, обсуждалка закрыта.
Решения не существует, т.к. не указан размер шариков - сколько ораз надо взвешивать, если шарики настолько большие, что больше одного не помещаются на чашу весов? А если и один не помещается - тогда вопрос - а на хера вообще весы?
+0–
ответить
Сибиряк• 21.12.07 12:59
2 ГигаNT
> После первого же взвешивания вы определяете группу однозначно
> правильных шаров. Вот из них и можно взять один недостающий
> для пункта 1.2.
Замечу, что для 12 шаров по достижении пункта 1.2 мы получим группу однозначно правильных шаров в количестве 4 штук. А для пункта 1.2 нам надо 5 правильных шаров, иначе алгоритм перестает работать.
> Тут кто-то хотел привести пример задачи, котрая решается
> для n шаров, но не решается для n-1? Плз.
Пусть пока задача с 12 шарами будет таким примером :)
Я пока не вижу алгоритма ее решения ...
+0–
ответить
Показать ещё 42 комментария