Найдите странный мяч из $18$ шары, где $17$ весить одинаково.
Вариантов этой проблемы много. Я работаю с
Есть $17$ шары, которые весят одинаково, и $1$мяч , который может весить либо тяжелее или легче , чем другие$17$. Сколько весов нужно на балансировочных весах, чтобы определить лишнее и тяжелее оно или легче?
Более простой случай, когда вы знаете, тяжелее или легче лишний мяч, можно найти в $3$весит. Идея состоит в том, чтобы разделить$18$ шары в группы $6$, сказать, $6A$, $6B$, $6C$. Вес$6A$ а также $6B$по шкале. Если они уравновешивают друг друга, то$6C$есть лишний. Если они не уравновешивают друг друга, и$6A$ ниже по шкале, то $6A$ имеет более тяжелый шар, и аналогично для $6B$. Так что требуется максимум$1$ взвесить, чтобы определить группу $6$с более тяжелым мячом. Затем вы можете разделить эту группу$6$ в $3$ группы $2$, и используя ту же идею, вы можете найти нечетную группу $2$ с максимумом $1$вес. Затем вы остаетесь с группой$2$ и это требует $1$взвесьте, чтобы определить более тяжелый мяч. Итак, всего вам понадобится$3$ взвешивание для этого случая.
Но более сложный вариант этой проблемы - это когда вы не знаете, тяжелее или легче лишний мяч. В этом случае я обнаружил, что вам нужно максимум$5$ пытается найти нечетное, а также определить, тяжелее он или легче, но я понятия не имею, правильно ли это, или как обосновать, что это минимальное количество попыток.
Идея аналогична предыдущей задаче. Делить$18$ шары в $6A$, $6B$, $6C$. На этот раз требуется максимум$2$ пытается найти группу $6$. т.е. взвесить$6A$ а также $6B$ по шкале, если они совпадают, то $6C$это нечетная группа. Если$6A$ а также $6B$не совпадает, то нам нужно дополнительное взвешивание, чтобы определить нечетное. Следовательно,$2$ пытается.
Теперь, когда мы нашли нечетную группу $6$, мы применяем ту же идею, которая требует другого $2$пытается (максимум). Затем мы остаемся с группой$2$. Требуется ровно$1$ весить, потому что ты можешь взять $1$ мяч из группы $2$ и взвесьте его с одним из других $16$шары, которые мы знаем, являются. Если этот шар такой же, то оставшийся шар является нечетным. Так что требуется максимум$2+2+1 = 5$пытается найти этот странный мяч. Нам не нужно дополнительное взвешивание, чтобы определить, тяжелее или легче оставшийся мяч.
Это потому, что когда мы нашли группу $6$, и последующая группа $2$, мы взяли максимум $2$пытается. Если потребуется$2$ пытается найти нечетную группу $6$ то это означает 2-е взвешивание $2$ Попытки позволяют нам определить, тяжелее или легче этот странный мяч.
Например, рассмотрим $6A$, $6B$, $6C$еще раз. Скажем, мы сначала взвешиваем$6A$ а также $6B$и обнаруживают, что они не одинаковы. Затем мы взвешиваем$6C$ либо с $6A$ или $6B$. Если мы взвесим$6A$ с участием $6C$ и найди это $6A$ не совпадает $6C$, тогда $6A$ является лишним, но также если $6A < 6C (6A > 6C)$, тогда мы знаем $6A$ имеет мяч, который весит меньше (больше).
Это самый оптимальный подход или есть метод, который требует только $4$взвешивать? Мое чутье подсказывает мне, что должна быть$4$ подход к взвешиванию.
В $12$-шариковый вариант задачи и его решение размещено в http://www.mytechinterviews.com/12-identical-balls-problem. Вы можете видеть, что они применяют аналогичный подход, нарушая$12$ шары в $3$ группы $4$, но они применяют некоторые интересные сочетания и сопоставления, чтобы найти лишнее только в $3$ движется.
Ответы
Решение на классику не проверял $12$ версия мячей http://www.mytechinterviews.com/12-identical-balls-problem. Но если это работает, это тривиально приводит к$4$ решение для взвешивания $18$ чехол для мячей.
На самом деле, учитывая классику, дополнительной работы очень мало!
Сначала вы взвешиваете $3A$ против $3B$. Если они неуравновешены, скажите$3A > 3B$, вы можете узнать с $3A$ против $3C$ (все $3C$хороши), тяжелее или легче плохой мяч. Тогда вы наверняка сможете найти виновника среди группы$3$с еще одним взвешиванием. Общее$3$ взвешивания.
И если $3A = 3B$, то вы переходите к классическому $12$-бол проблема, которую можно решить с помощью $3$ дополнительные взвешивания, всего $4$.
Дальнейшие мысли: на самом деле, $4$ взвешивание может решить $30$ шары, а не только $18$.
В приведенном выше $3A \neq 3B$ ветка всегда ведет к $3$общее взвешивание, что расточительно. Представьте, что у вас есть$9+9+12 = 30$мячи. Первое взвешивание можно$9A$ против $9B$. Если они неуравновешены, снова на секунду$9A$ против $9C$ (все хорошо) скажет вам, тяжелый или легкий плохой, а затем вы можете использовать $2$ больше взвешиваний, чтобы найти виновника среди $9$ (трехкратный поиск), всего $4$ взвешивания.
Более того, много лет назад я решил случай (продолжение классического), когда $13$ шары (неизвестные тяжелые / легкие) можно собрать с помощью $3$ взвешивания, при условии, что у вас есть доступ к дополнительным шарам, которые считаются хорошими - вам нужен IIRC $2$такие хорошие статисты. Это означает$9+9+13 = 31$ можно решить с помощью $4$ взвешивания, потому что в $9A=9B$ если вы действительно остались с $13$ подозревает, но много лишних мячей, как известно, хороших.
Я подозреваю даже $31$ не предел (для $4$взвешивания). Когда ты весишь$9A$ против $9C$возможны только два исхода (поскольку $9A > 9B$). Это очень неэффективно, и дальнейшая эксплуатация возможна ...
Вы, наверное, знаете, что классика связана с $n$ взвешивания есть только $3^n$ возможные результаты, поэтому с $n=4, 3^n = 81$, ты не можешь решить $\ge 41$ мячи ($\ge 82$результаты). Я не говорю$40$ достижимо, но существует большой разрыв между $31$ а также $40$...
Взвешивание 1 : Взвешивание$1$-$6$ против $7$-$12$. Если результат сбалансирован , то мы знаем, что нечетный мяч находится в наборе$13$-$18$, что (действительно) принимает $3$больше измерений, всего 4 взвешивания.
Если первое взвешивание неуравновешено , без ограничения общности предположим, что$1$-$6$ тяжелее чем $7$-$12$. Затем выполните ...
Взвешивание 2 : Взвешивание$1$-$3$ против $7$-$9$. Если результат уравновешен , нечетный мяч$\{ 4, 5, 6, 10, 11, 12 \}$, что действительно требует $3$больше взвешиваний, всего 5 взвешиваний.
Если вместо этого результат несбалансирован , без ограничения общности предположим, что$1$-$3$ тяжелее чем $7$-$9$. Тогда мы знаем, что нечетный мяч находится в наборе из шести, что действительно требует еще двух взвешиваний, всего 5 взвешиваний.