Комментарии 70
Возникает вопрос: а почему у весов-разновесов только три взвешивания? Что их ограничивает? Возможно, это аркадные весы-разновесы, в которые нужно бросить монету, чтобы они взвешивали? =)
Можно добавить, на весы прорезь для монет, и сделать, что одно взвешивание стоит 4 монеты (копейки?). А первое взвешивание бесплатно. Так мы оправдаем искусственное ограничение задачи, оставив те же три взвешивания!
P.S. Тоже дальнозоркий. Задачу решил в уме, но с трудом. Спасибо!
Можно добавить, на весы прорезь для монет, и сделать, что одно взвешивание стоит 4 монеты (копейки?). А первое взвешивание бесплатно. Так мы оправдаем искусственное ограничение задачи, оставив те же три взвешивания!
P.S. Тоже дальнозоркий. Задачу решил в уме, но с трудом. Спасибо!
+2
Если Вы вспомните троичную систему счисления (троичную уравновешеную), то решается в уме без малейших затруднений.
0
Я не особо представляю, как троичная симметричная (уравновешенная) система счисления поможет решить эту задачу.
Если у вас есть такое оригинальное решение, не могли бы вы его показать? Разумеется, спрятав под спойлер.
Если у вас есть такое оригинальное решение, не могли бы вы его показать? Разумеется, спрятав под спойлер.
+2
совершенно верно. любое число монет. необходимо N взвешиваний для числа монет
0
прошу прощения, не сделал предпросмотр и хабр схавал половину комментария.
Необходимо N взвешиваний для монет 3 в степени N. Т.е. для 9 монет достаточно 2, от 10 до 27 достаточно 3 и т.д.
Необходимо N взвешиваний для монет 3 в степени N. Т.е. для 9 монет достаточно 2, от 10 до 27 достаточно 3 и т.д.
-1
Мне кажется, что это подходит только в случае, если известно, тяжелее или легче фальшивая монета. Не могли бы вы показать своё решение? Разумеется, спрятав его под спойлер.
+1
не правда ваша
в таком случае при N=3 получится 13 монет
покажите способ определения фальшивой монеты за 3 взвешивания для 13 монет
в таком случае при N=3 получится 13 монет
покажите способ определения фальшивой монеты за 3 взвешивания для 13 монет
+1
Пожалуйста:
Взвешиваем 4 + 4.
Вариант А, весы равновесны: имеем 8 нормальных монет и 1 фальшивую в куче из 5. Взвешиваем 3 нормальные монеты и 3 монеты из кучи с фальшивой. А1 — весы равновесны — имеем 11 нормальных монет и 2 фальшивые. Взвешивание нормальной и любой из оставшихся позволяет определить фальшивую. А2. Весы имеют отклонение. В группе из 3 монет из фальшивой кучи 1 фальшивая и мы знаем тяжелее или легче она. Взвешиваем 1 + 1 из фальшивой кучи, определяем фальшивую однозначно.
Конец варианта А.
Вариант Б, весы показали перевес. Имеем 5 нормальных монет (те которые не взвешивали), 4 Л/Н (легкие или нормальные) и 4 Т/Н (тяжелые или нормальные). Следим за движениями рук: взвешиваем 3 Л/Н + 1 Т/Н на одной чаше весов и 3 Н + 1 Л/Н на другой чаше весов. Т.е. мы поменяли по 1 монете с разных чаш и 3 Т/Н заменили на строго Н. Имеем 3 варианта:
Б1 — чаши имеют тот же перевес что был в предыдущем взвешивании. Значит мы взвешивали 3 Л/Н + Н и 4 Н. выбрать из 3 монет одну фальшивую зная что она легче не представляет труда. взвешиваем любые 2 монеты из тройки, та что легче, та фальшивая. если вес одинаковый, то фальшивая третья.
Б2 — чаши равновесны. Т.к. при взвешивании 3 Т/Н были заменены на Н, фальшивая монета тяжелее и находится по аналогии Б1.
Б3 — чаши имеют другой перевес. значит одна из монет которую мы поменяли на чашах фальшивая. Мы не можем однозначно определить легче она или тяжелее. Взвешиваем одну из двух с любой нормальной и либо весы равны и фальшивая третья, либо весы не равны но мы знаем нормальную монету.
Взвешиваем 4 + 4.
Вариант А, весы равновесны: имеем 8 нормальных монет и 1 фальшивую в куче из 5. Взвешиваем 3 нормальные монеты и 3 монеты из кучи с фальшивой. А1 — весы равновесны — имеем 11 нормальных монет и 2 фальшивые. Взвешивание нормальной и любой из оставшихся позволяет определить фальшивую. А2. Весы имеют отклонение. В группе из 3 монет из фальшивой кучи 1 фальшивая и мы знаем тяжелее или легче она. Взвешиваем 1 + 1 из фальшивой кучи, определяем фальшивую однозначно.
Конец варианта А.
Вариант Б, весы показали перевес. Имеем 5 нормальных монет (те которые не взвешивали), 4 Л/Н (легкие или нормальные) и 4 Т/Н (тяжелые или нормальные). Следим за движениями рук: взвешиваем 3 Л/Н + 1 Т/Н на одной чаше весов и 3 Н + 1 Л/Н на другой чаше весов. Т.е. мы поменяли по 1 монете с разных чаш и 3 Т/Н заменили на строго Н. Имеем 3 варианта:
Б1 — чаши имеют тот же перевес что был в предыдущем взвешивании. Значит мы взвешивали 3 Л/Н + Н и 4 Н. выбрать из 3 монет одну фальшивую зная что она легче не представляет труда. взвешиваем любые 2 монеты из тройки, та что легче, та фальшивая. если вес одинаковый, то фальшивая третья.
Б2 — чаши равновесны. Т.к. при взвешивании 3 Т/Н были заменены на Н, фальшивая монета тяжелее и находится по аналогии Б1.
Б3 — чаши имеют другой перевес. значит одна из монет которую мы поменяли на чашах фальшивая. Мы не можем однозначно определить легче она или тяжелее. Взвешиваем одну из двух с любой нормальной и либо весы равны и фальшивая третья, либо весы не равны но мы знаем нормальную монету.
-1
Это вы погорячились. Пусть 9 монет — какое первое взвешивание?
+2
Ограничение чисто математическое. Гораздо логичнее другая постановка той же задачи — найти фальшивую монету за наименьшее количество взвешиваний (в худшем случае). Путем не сложной логической цепочки можно додуматься, что меньше, чем за 3 взвешивания это сделать точно не получится (каждое взвешивание может дать 3 различных исхода. 2 взвешивание даст 9 различных исходов, чего не хватит для определения одной из 12 монет).
0
Хм… максимальное число монет для взвешиваний = (3^n)/2, где 3 — система счислений, n — число взвешиваний, 2 — число вероятностей веса монеты. Т.е. игра на 14 монет при 3-х взвешиваний имеет логичное решение, если заранее известно, что монета тяжелее или легче.
0
А зачем тут эксимер?
+9
«Разумеется, в статье есть математическая умышленная ошибка,»
Ну, это очевидно же, что: «Как и 17 лет назад,» =)
Ну, это очевидно же, что: «Как и 17 лет назад,» =)
0
Мне вот всегда было интересно, что трудного в этой задачи? Особенно для программистов, если они знакомы с теорией информации.
И кстати, за три взвешивания можно гарантировано вычислить фальшивую монету из пачки до 27 монет.
И кстати, за три взвешивания можно гарантировано вычислить фальшивую монету из пачки до 27 монет.
-4
Четыре дна после повторной(!) операции — и нагружать зрение работой на компьютере… Не бережете вы себя!
По своему опыту — от фемтоласика отходил неделю стараясь не нагружать зрение вообще.
По своему опыту — от фемтоласика отходил неделю стараясь не нагружать зрение вообще.
+1
Спасибо за правильный комментарий; В самом деле я в основном глазею в окно, все заготовки для игры были сделаны заранее. С операцией все было сложнее, когда восстановится зрение — я опишу квест более подробно в разделе здоровье гика.
Что касается умышленной ошибки - она здесь
Вариант игры с двумя монетами не имеет решения ни за какое количество взвешиваний.
+1
Буду ждать статью. Особенно хорошо будет упомянуть различия ласика и фемтоласика, а еще добавить полезный совет — не смотреть на ютубе как выглядит операция — со стороны это гораздо страшнее выглядит чем «от первого лица».
Безумная идея — сделать для окулуса игру показывающую как собственно это все видится, со всеми положенным затемнениями, мутностями и спецэффектами.
Безумная идея — сделать для окулуса игру показывающую как собственно это все видится, со всеми положенным затемнениями, мутностями и спецэффектами.
+2
Добрый день
Не могу не поделится ссылкой.
Не могу не поделится ссылкой.
0
Одно из двух:
Вес фальшивки дб определён
Взвешиваний дб больше
Вес фальшивки дб определён
Взвешиваний дб больше
-1
5 + 5 + 2 = 12
2 + 2 + 1 = 5
1 + 1 = 2
это же школьная задача. если повезет — два взвешивания
2 + 2 + 1 = 5
1 + 1 = 2
это же школьная задача. если повезет — два взвешивания
0
Спасибо интересно, если будет время хотелось бы увидеть под Android.
+1
20 лет назад я был сильно близорук -7 vs -14
Я дико извиняюсь, но почему «vs»? У вас глаза дрались между собой? Или это общепринятое сокращение при указании зрения на оба глаза?
+4
Крайне просто решается задача. Итак, 12 монет, весом в известную(?) сторону отличается только одна, 3 раза можно взвесить.
1. 6 / 6 — отсекаем сразу половину
2. 3 / 3 — отсекаем половину от оставшегося
3. 1 / 1 — либо одна перевесит, либо фальшивую не взвесили; в любом случае, решение однозначно найдено
Исхожу из предположения, что известно, тяжелее или легче фальшивая монета в сравнении с настоящей. В условиях как-то неоднозначно сказано.
Если неизвестно, то в третьем шаге при перевешивании одной монеты надо угадать.
1. 6 / 6 — отсекаем сразу половину
2. 3 / 3 — отсекаем половину от оставшегося
3. 1 / 1 — либо одна перевесит, либо фальшивую не взвесили; в любом случае, решение однозначно найдено
Исхожу из предположения, что известно, тяжелее или легче фальшивая монета в сравнении с настоящей. В условиях как-то неоднозначно сказано.
Если неизвестно, то в третьем шаге при перевешивании одной монеты надо угадать.
-2
то есть либо легче, либо тяжелее прочих.
Ох уж эта непонятность, да?.. Мне кажется вы просто не старались понять. Как и большинство здесь отписавшихся.
+2
НЛО прилетело и опубликовало эту надпись здесь
Любая сложная задача имеет простое, легкое для понимания неправильное решение. © Артур Блох
В условиях сказано вполне однозначно: «либо легче, либо тяжелее прочих».
В условиях сказано вполне однозначно: «либо легче, либо тяжелее прочих».
Вариант решения
Шаг 1. Три монеты на одной чашке, три монеты на другой.
Шаг 2. Оставшиеся шесть монет снова делим на две тройки и взвешиваем их.
В результате первых двух шагов мы узнаём тройку монет, в которой есть фальшивая, а также тяжелее она или легче остальных.
Шаг 3. Из найденной тройки откладываем одну монету в сторонку, оставшиеся две сравниваем на весах. Поскольку мы уже знаем характеристики фальшивой монеты (тяжелее/легче), по весам её легко определить. Если взвешенные монеты весят одинаково, то фальшивая монета — та, что в сторонке.
Шаг 2. Оставшиеся шесть монет снова делим на две тройки и взвешиваем их.
В результате первых двух шагов мы узнаём тройку монет, в которой есть фальшивая, а также тяжелее она или легче остальных.
Шаг 3. Из найденной тройки откладываем одну монету в сторонку, оставшиеся две сравниваем на весах. Поскольку мы уже знаем характеристики фальшивой монеты (тяжелее/легче), по весам её легко определить. Если взвешенные монеты весят одинаково, то фальшивая монета — та, что в сторонке.
+2
Как вы узнаете, тяжелее фальшивая монета или легче после шага 2?
Вот есть у вас результат первых двух взвешиваний:
Как вы из этого сможете сделать вывод, должна ли фальшивая монета быть тяжелее или легче?
Вот есть у вас результат первых двух взвешиваний:
- Две чаши весов в равновесии
- Правая чаша весов ниже левой
Как вы из этого сможете сделать вывод, должна ли фальшивая монета быть тяжелее или легче?
+2
Как можно узнать на какой чаше весов фальшивка на шаге 2(1)?
+1
По этому решению если неизвестно то на всех этапах не ясно какую группу оставлять. На первом мы вполне можем отсечь рабочий вариант, где нет фальшивки. Как и на втором.
0
Вспомнил, у меня же есть видео!
+2
Ну спрячьте под спойлер! Меня тут уже пару часов ломает, чтобы решение не рассказать, и люди сами решали. А вы взяли и… Эх вы…
0
Прости меня, но все-таки видео само не запустится? Оно не хуже спойлера…
0
Согласен. Но и текст «сам не читается». Смысл в том, что видя спойлер, ты сначала читаешь его название, к примеру «Осторожно, решение!». Видео же можно запустить и не зная, что там решение (вы, кстати, об этом и не написали). В результате хабравчанен может включить ваше видео лишь для того, чтобы посмотреть на то, как работает ваше приложение, а получит решение, которое возможно и не хотел пока видеть.
0
После второго шага вполне может получиться что две эти кучки будут равны и значит что одна из трех отложенных фальшивая. И у нас остается одно взвешивание чтобы из трех монет найти одну верную. Что, не зная легче\тяжелее, невозможно.
0
Не торопитесь, у Вас есть информация с первого взвешивания — она и пригодится в этом случае — главное, правильно положить монеты на правую и левую чашки!
+1
Итого у нас есть три неизвестные монеты и 9 известных. Обозначим как 1-2-3, известные как Х.
Возьмем взвешивание ХХ1 и ХХ2.
1. Если оно равно, то фальшивая монета 3. Но если не равны, то опять таки незнание о весе не даёт нам понимание 1 или 2 фальшивая без дополнительного взвешивания, типа ХХХ и ХХ1.
2. Если не равно, то см. пункт 1.
Мешать монеты по типу Х12 и ХХ3, тоже смысла нет ибо имея худший вариант получим не знание 1 или 2.
Я может заблуждаюсь где-то, просьба прислать в личку решение, если оно всё-таки есть.
Возьмем взвешивание ХХ1 и ХХ2.
1. Если оно равно, то фальшивая монета 3. Но если не равны, то опять таки незнание о весе не даёт нам понимание 1 или 2 фальшивая без дополнительного взвешивания, типа ХХХ и ХХ1.
2. Если не равно, то см. пункт 1.
Мешать монеты по типу Х12 и ХХ3, тоже смысла нет ибо имея худший вариант получим не знание 1 или 2.
Я может заблуждаюсь где-то, просьба прислать в личку решение, если оно всё-таки есть.
0
Решение
В третьем взвешивании положите левую монету на ПРАВУЮ чашку весов и одну из прав монет к ней рядом. На левую — две настоящие; Рассмотрите ТРИ варианта взвешивания — и сравните с ПЕРВЫМ взвешиванием. Если чашки разновесны, но знак поменялся, решение очевидно. Перекинутая монета фальшива. Если не поменялся — ответ еще очевиднее. А если равенство, совсем еще вообще очевиднее.
0
Как-то со звездочками туговато :-) Маловато дают даже за верное решение :-)
+1
Это перевод, реклама ЭКСИМЕР или автор во время написания поста прозрел?
+1
Это отзыв, среди нашего брата много очкариков, им важна любая информация. По поводу эксимера — в 1999 году у него не было конкурентов в Москве и результат — 14 лет хорошего зрения после операции я считаю успешным. А вот с нижегородским офисом все гораздо сложнее и мой совет — не пользуйтесь провинцией. Впрочем, возможно я неправ — мое мнение может измениться через месяц.
Прозрею — все расскажу: ух.
Прозрею — все расскажу: ух.
0
т.е. вы мой комментарий не видите и отвечаете наугад?
0
Комментарий Ваш я хорошо увеличил и вижу (догадываюсь); а вот имя не вижу — другой фонт-шрифт, плохо масштабируется.
0
Хм… тогда строчка про «никуда не присылайте» неуместна. А какое у вас сейчас зрение?
0
Сегодня чуть лучше- я распознал Ваш ник. Мое зрение невозможно опередить количественно — полная анизотропия до схода отеков внутри глаза.
0
А это вообще не вредно напрягать зрение в такой период? Вы не пробовали скринридеры (не уверен в названии) и аналогичые приблуды для браузера, которые зачитывают нужный текст?
0
>Все замечания по ошибкам в статье никуда не присылайте.
Патентовать не будете, это же уже в public domain? Можно использовать?
Патентовать не будете, это же уже в public domain? Можно использовать?
+2
Что ж вы по-модному, голосовым вводом не набрали статью и код!
0
Как-то была я в одной фирме на собеседовании на позицию тестировщика. После стандартного вопроса про взвешивание бильярдных что ли шаров за минимальное количество заходов. А потом мне задали такую задачку: «Есть грубо говоря 100 коробок с компьютерными мышками, по 100 мышек в коробке. Но одна коробка содержит в себе бракованные мышки. за одно взвешивание надо обнаружить, какая именно.»
Я с ней самостоятельно не справилась, предложенное собеседующим решение меня не устроило, и вообще все внутри меня бунтовало против этой идиотской задачи.))
Я с ней самостоятельно не справилась, предложенное собеседующим решение меня не устроило, и вообще все внутри меня бунтовало против этой идиотской задачи.))
0
1) Известно ли, тяжелее или легче?
2) Известно ли, насколько?
3) По-прежнему весы Фемиды или те, которые позволяют узнать вес?
4) Если весы Фемиды, то есть ли в наличии гирьки?
Т.е. примерно понятно, как решать, но хотелось бы полную формулировку.
2) Известно ли, насколько?
3) По-прежнему весы Фемиды или те, которые позволяют узнать вес?
4) Если весы Фемиды, то есть ли в наличии гирьки?
Т.е. примерно понятно, как решать, но хотелось бы полную формулировку.
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Слепой программист и фальшивая монета