Взвешивание монет

Решение задач на определение фальшивой монеты взвешиванием 2.0

Взвешивание монет

Наиболее распространенные из таких задач — определение количества взвешиваний для выявления фальшивой монеты, если: 1) неизвестно какая она по весу; 2) известно, что она легче/тяжелее остальных. Или обратная задача: можно ли за определенное количество взвешиваний выявить фальшивую из заданного количества монет.

1. Давайте сначала разберемся с 2 вариантом, который является частным случаем варианта 1

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

N >= log3A,

где N — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону; A — количество монет. Которая выведена на основании опытов (за 1 взвешивание можно найти одну фальшивую из 3-х монет, за 2 — из 9, за 3 — из 27 и т.д.

) Сам алгоритм решения простой, и я покажу его на примерах 1) Пусть у нас есть 26 монет.

Нужно найти одну, которая легче/тяжелее Первым действием буде разделение монет на три группы, в двух из которых число монет будет одинаковым, важно только что бы в третьей группе — остатке — было меньше монет, чем в каждой из двух других групп. То есть частое округляется к большему натуральному числу. То есть

A = 2 * B + C,

где A — количество монет; B — частное от деления количества монет на 3, натуральное число, округленное в большую сторону; C — остаток. По условию задачи 26/3 = 8.666(6), 26 = 2 * 9 + 8, При первом взвешивании будут сравниваться две группы: правая (ПГ) — 9 монет и левая (ЛГ) — 9 монет.

Далее у нас возможны два варианта: 1) фальшивая монета в левой/правой группе (9 монет) 2) фальшивая монета в остатке (8 монет) для 1 варианта следующее деление на группы будет — 9 = 2 * 3 + 3; для 2 варианта — 8 = 2 * 3 + 2 Ну и за одно взвешивание можно определить какая из 2 или 3 монет легче/тяжелее Этот же результат я приведу в таблице

№ взвешиванияЧисло монетЛГПГОстаток
126998
28332
29333
32110
33111

по формуле — log326 =2.9656 — соответственно количество взвешиваний — 3.

еще пример:

число монет- 71. По формуле log371 =3.8800 — количество взвешиваний — 4. Проверяем

№ взвешиванияЧисло монетЛГПГОстаток
171242423
223887
224888
37331
38332
42110
43111

Ну с алгоритм решения этих задач, я думаю, понятен.

2. Теперь перейдем к задачам, в которых не известно легче монета или тяжелее

В данном случае я предлагаю такое первое действие: разделить монеты на четыре группы, три — с максимально одинаковым количеством монет, а в четвертой группе — остаток. Причем в остатке должны быть 1 или 2 монеты. То есть при делении на 3 частное округляется до меньшего натурального числа.

A = 3 * B + C,

где A — количество монет; B — частное от деления количества монет на 3, натуральное число, округленное в меньшую сторону; C — остаток. Например, для 58-ми монет — это будет 58 = 3 * 19 + 1, для 23 = 3 * 7 + 2, для 15 = 3 * 5 + 0 и т. д.

Далее выполняем два взвешивания: 1) первая и вторая группы; 2) первая и третья группы; и анализируем результат. Здесь возможны четыре варианта:1, 2, 3 — это первая, вторая или третья группа отличаются по весу от двух остальных, или они равны, тогда нам повезло, так как фальшивая — в остатке.

Так же два взвешивания помогают определить определить тяжелее фальшивая монета или легче. Кстати, если в остатке две монеты, то нужно выполнить еще 2 взвешивания для определения фальшивой монеты. Теперь у нас есть задача: определить одну фальшивую монету из группы, которая легче/тяжелее.

Что касается формулы, то она примет следующий вид

N >= log3B + 2,

где N — максимально необходимое количество взвешиваний, натуральное число; B — количество монет в группе после второго взвешивания. А если учесть, что B = A/3, где A — количество всех монет, тогда получим:

Итог:

1) если известно, что фальшивая монета легче/тяжелее, тогда максимальное число взвешиваний определяется по формуле:

N >= log3A

2) если не известно, какая фальшивая, тогда максимальное число взвешиваний определяется по формуле:

Взвешивание монет на электронных весах — ответ выложен

Взвешивание монет
ru_golovolomkathaere
Имеется десять кошельков, в одном из которых одинаковые фальшивые монеты. Вес фальшивых монет немного отличается, но вручную это определить нельзя. Вес обычной монеты известен.Есть точные электронные весы.

Можно ли определить за одно взвешивание кошелёк с фальшивыми монетами, если вес фальшивых монет тоже известен?Сколько нужно взвешиваний, если вес фальшивой монеты точно неизвестен?Бонус: зависит ли ответ от того, одна чаша у весов или две? (то есть весы показывают точную разницу между двумя чашами).Обоснование последнему ответу я точное сам не делал, так что мне самому интересно.

Правильные ответы: gul_kiev, illuziy_nini, ndochp, sam0pal, minamoto_ru, jim_h, ur_pa.

Наиболее полный и интересный ответ — gul_kiev.
Правильный ответ по третьему вопросу достаточно прост, извините, кто не совсем понял формулировку, я уточнил.ru_golovolomkacountrclockwise
Ответов: 8Баллов: 12.5

Ответившие правильно: thaere, gul_kiev, ndochp, ur_pa, sa_chernomor, ctapnep, illuziy_nini, minamoto_ru

Чтоб мне зря не печатать, копирую один из ответов:

Первая — смесь бочонков 123.Вторая — смесь бочонков 456.Таким образом определяем тройку — XYZ.Третья экспертиза — X.Четвёртая экспертиза — Y.В худшем случае 4.

Можно показать, что нет деления, при котором худший случай будет лучше чем 4. 9 больше чем 2**3.

Если каждая экспертиза определяет в какой группе бочонков яд есть или нет, то группа с размером большим, чем 2**N, разбивается на две группы, и одна из них больше чем 2**(N-1).

Итак после первой экспертизы возможен вариант, что яд в группе из 5, после второй — из 3, после третьей — из 2.

Page 3

ru_golovolomkaminamoto_ru
Как, имея три числа A,B,C, совершить преобразование в A=B,B=C,C=A, не используя дополнительных переменных за минимальное число преобразований?Доказательства, что количество преобразований действительно минимально, не требуется.

Верные ответы: gul_kievvit0ld, ur_pa, jim_h, sam0pal, ndochp, illuziy_nini.

Page 4

ru_golovolomkacountrclockwise
В этих головоломках все слова в крылатом высказывании (пословице, поговорке, широко известной фразы) заменены на наукообразные их определения. В результате и получился псевдонаучный бред… бред профессора.

Например: Условием выживания биологической особи является ее перемещение по криволинейной замкнутой траектории. Ответ : Хочешь жить — умей вертеться.В общем, нужно отгадать фразу, зашифрованную таким «научным» способом.

  1. Соответствие длительности процесса жизнедеятельности и процесса обучаемости человеческого индивидуума, означающее неизбежное завершение жизненного цикла в состоянии пониженного интеллектуального развития.

  2. Неполное соответствие окружающей среды празднику Солнца у языческих народов Древней Руси для самца млекопитающего семейства кошачьих.

  3. Нетранспортабельность выражения благодарности
  4. Способность живого организма переносить болевые ощущения и прочие раздражители в совокупности с процессом производства товаров и услуг позволяют привести окружающее пространство в порошкообразное состояние.

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

  6. О травматическом опыте пребывания неполовозрелых граждан в окружении избыточного количества лиц преклонного возраста
  7. Возможность изготовления традиционного элемента одежды европейской культуры при помощи сбора скрученых шерстяных или шелковых волокон на всем ареале обитания человека.
  8. Радикальная хирургическая операция для индивидуумов, адекватно воспроизводящих прошедшие события
  9. Опасность перевода в бодрствующее состояние агрессивных факторов окружающей среды во время их пониженной шумовой активности
  10. Рекурсивный опус о взаимоотношениях лица духовного звания и млекопитающего отряда волчьих, вызванных незаконным переходом собственности первого ко второму путем тайного поглощения.

Ответы, разумеется, приветствуются, но не обязательны — баллы не выставляются, это иммено «развлекалка». Комменты открыты для всех

Page 5

ru_golovolomkacountrclockwise
Ответивших: 7
Ответов: 8 (2 ответа у ur_pa)
Баллов: 14.3 (бонус 4 для ur_pa)

Задачка была предложена как двухнедельная — кто ж знал, что вы все такие крутые. Всем бонус +2. ur_pa дополнительный бонус +4 за два различных доказательства.

Итого: всем 16.3, ur_pa 20.3.

Ответившие правильно: ctapnep, gul_kiev, jim_h, ndochp, sam0pal, thaere, ur_pa

Большинство ответов — через математическую индукцию.

Примеры ответов:

ctapnep

Предположим, что самолет 2-местный. Тогда вероятность 1/2. Очевидно.

Предположим, что 3-местный…

старушка может сесть на своё место (1 вариант), на место священника (1 вариант) и на место 2-го пассажира и… тогда задача сведется к 2-м местам и 2-й пассажир в виде вздорной старушки.

То есть та-же вероятность в 1/2, плюс по 1 варианту с каждой стороны. Что даёт всё те-же 1/2 общей вероятности.

Ну и так далее для любого количества мест.

Итого — вероятность сесть на своё место — 1/2.

sam0pal — опасно близко к методу Капицы-Иоффе 🙂

Пусть для определенности пассажиры имеют билеты с номерами с 1 по n и стоят в очереди по своим номерам (старушка, конечно, первая). С вероятностью 1/n она займет любое место. Если она заняла не свое место, то пассажир чьё место она заняла сам превращается в эту старушку. Тогда вероятность считается по формуле :V(n) = 1/n * (1 + V(n-1) + V(n-2) + … + V(2))V(2) = 1/2

По индукции легко доказать что V(n) = 1/2

ur_pa (второе доказательство)

Убедимся, что следующие утверждения верны:.Утверждение 1. Пока место первого пассажира и место последнего пассажира ещё свободны, вероятность очередного пассажира сесть на место первого равна вероятности сесть на место последнего.

Первый пассажир не знает своего места, и для него своё первое и последнее — неразличимы и равновероятны.Если пассажир зрает своё место, и оно свободно — то наш пассажир не первый.

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

Для пассажира, чьё место занято, места первое и последнее — неразличимы и равновероятны.

Утверждение 2. Кроме первого пассажира, никто не может сесть на чужое место, если своё собственное свободно.

Следует из условия.Утверждение 3. Если один из первых N-1 пассажиров садится на место первого, то последний пассажир сядет на своё место.Следует из утверждения 2. Как только кто-то садится на место первого, больше ни у кого из сидящих нет билета на свободное место. Множество занятых мест совпадает с множеством мест, указанных в билетах сидящих.

У стоящих остались билеты только на свободные места и каждый сядет на своё место, включая последнего.Утверждение 4. Если один из первых N-1 пассажиров садится на место последнего, то последний пассажир не сядет на своё место.Читателю — в качестве упражнения.Утверждение 5.

Если проводится серия испытаний, в каждом из которых исходы А и В равновероятны, а все последующие исходы приводят к повторным испытаниям, пока не выпадет А или В, и известно что серия рано или поздно закончится, то вероятности результатов А и В совпадают.Доказывается простой индукцией по числу испытаний.

Впрочем, вполне сойдёт за очевидное — как если бросать честную кость либо до первой единицы, либо до первой шестёрки, то вероятность закончить на шестёрке равна вероятности закончить на единице.

Доказательство утвержденияюМы имеем N-1 попытку, каждая из которых с равной вероятностью может привести к тому, что либо место первого пассажира либо место последнего будет занято. То из этих двух событий, которое произойдёт первым, определяет конечный результат — сядет ли последний пассажир на своё место. Ясно, что после N-1 шагов результат уже будет известен.

Так как вероятности обоих исходов при каждом испытании одинаковы, вероятности обоих конечных исходов также одинаковы. Если место первого будет занято раньше, чем место последнего, последний сядет на своё место. Если место последнего будет занято раньше, чем место первого, то последний не сядет на своё место.

Итак, с вероятностью 50% последний пассажир сядет на своё место

ndochp (Спасибо за численную демонстрацию)

Очевидно, что для священник сядет на свое место, если на момент его выбора среди оставшихся билетов (1) все будут обеспечены свободными местами.

А для этого есть два успешных исхода: или старушка сразу сядет на свое место, или пока пассажиры не кончатся хоть один с занятым местом сядет на место занимающего.

Сначала я решим вспомогательную задачу: Какова вероятность того, что после текущей итерации (Н) среди оставшихся билетов путаница останется, при условии, что к ее началу вероятность того, что место перепутано Н/(Н+1).

Ситуация исправится на этом шаге, если войдет перепутанный и сядет на место путанника.Вероятность сесть на перепутанное место (и исправить ситуацию) 1/Н, но ее учитываем не для всех пассажиров, только для одного, то есть с вероятностью 1/Н.

Вероятность не исправить соответственно 1-(1/Н*1/Н) или (Н2-1)/(Н2), что мы домножаем на текущую вероятность бардака и выходим на (Н/(Н+1))*((Н2-1)/(Н2)) или (Н*(Н2-1))/((Н+1)*Н2) Сокращая через разность квадратов получаем (Н-1)/Н и выходим на следующий шаг индукции. То есть на начало шага Л=Н-1 вероятность того, что ситуация останется неисправленной Л/(Л+1). и так далее.

Теперь начинаю применять решение вспомогательной задачи к основной:На итерации 99(оставшихся пассажиров) очевидно условия исходной задачи и вспомогательной совпадают. (После того как села старушка у нас 1 из 99+1, что что она заняла свое место и, соответственно священник сядет на свое.

) Значит, после того как пассажир 99 сядет, согласно вспомогательной, вероятность того, что все станет хорошо 1/99.Теперь для итерации 98. Входной вероятностью для нее является вероятность того, что после итерации 99 все уже хорошо (1/99), что соответствует условию вспомогательной задачи, значит выходная вероятность — 1/98.

Крутим, крутимДля итерации 2 (последний пассажир и священник) вероятность, что все станет хорошо после нее 1/2.

Для итерации 1 священника формулу уже не применяем. Просто говорим, что раз по итогам итерации 2 вероятность того, что на ней все стало хорошо 1/2, то это и есть вероятность сесть священнику на свое место.

.

Page 6

ru_golovolomkacountrclockwise
В ЖЖ есть очень для нас две очень неудобные фичи.

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

(Спасибо gul_kiev за вычисляние «дырки» и тем игрокам, которые прислали мне в личку: «А чего это мне в мыло все ответы падают?»)

К счастью, я нашел возможность отредактировать CSS и убрать линк «Track This» на пост. Можно вернуться к старому доброму методу — комментировать ответы непосредственно.Но.

Так как при комментировании ответ все равно приходится открыть, постарайтесь делать это так:- написать ответ (Notepad, Semagic — неважно)- откройте коммент, на который пишите ответ- нажмите «Reply» и скопируйте текст в ваш коммент (обычно коммента типа «юзер — зачет/незачт» хватает, но решать вам)- закройте ответ, и закройте ваш коммент (если ваш коммент будет только «юзер такой-то — зачет» закрывать ваш коммент не нужно)Таким образом ответ пробудет открытым и видимым минимальное количество времени.

P.S. НЕТ такого замка, к которому нельзя было бы найти ключа. Стоит ли это делать, или лучше порешать задачки — решайте сами

Page 7

|

ru_golovolomkacountrclockwise
Дoбавлена неделя на задачу «Кляксы»—————————-На белом квадратном листе бумаги шириной один метр наляпали большое количество мелких клякс. В результате лист оказался частично окрашенным, причём таким образом, что:- ни одна окрашенная точка не подходит ближе, чем на 1мм к краю листа.- на листе нельзя найти две окрашенные точки, расстояние между которыми ровно 1мм. Доказать, что общая площадь клякс меньше трети площади листа.—————————-

Ответы, пожалуйста, в оригинальный пост: «Кляксы»

Правильный ответ пока только один: gul_kiev

Источник: https://ru-golovolomka.livejournal.com/14569.html

Поделиться:
Нет комментариев

    Добавить комментарий

    Ваш e-mail не будет опубликован. Все поля обязательны для заполнения.

    ×
    Рекомендуем посмотреть