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