Сложная задача с интуитивно неочевидным ответом

[spamsink]

Имеется N монет, среди которых есть одна фальшивая, чуть легче настоящих, и электронные весы с разрешением в 0.1 г. Настоящие монеты весят целое число граммов, а фальшивая - на 0.05 г легче, так что определить, что во взвешиваемых монетах есть фальшивая, удается с вероятностью 50% (если все монеты настоящие, весы стопроцентно показывают целое число). Монет можно взвешивать любое число зараз.

Как нужно действовать, чтобы минимизировать ожидаемое количество взвешиваний для нахождения фальшивой монеты?

Comments

[yigal_s]

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

[spamsink]

Матожидание количества взвешиваний для обнаружения фальшивой монеты конечно. Вот мы и хотим минимизировать его.

[spamsink]

Откуда 1/3?

[spamsink]

В формуле энтропии не ln, а двоичный логарифм, и арифметика слегка не такая. Число получается близкое к 0.38, но не 1/е, как можно было бы "математически-интуитивно" подумать, и весьма загадочное. :)

[kdv2005.livejournal.com]

А какая вероятность того, что весы покажут нецелый вес, если фальшивую монету не класть? Тоже 50%?

[kdv2005.livejournal.com]

Понял, 0%.

[spamsink]

Если фальшивую монету не класть, весы всегда показывают целый вес.

[yigal_s]

О! вот этого я тоже сначала не понял

[kdv2005.livejournal.com]

Я понял как перейти от N монет к N/2 в среднем за 4 шага. Стало быть, мой ответ -- 4log₂ N плюс поправка порядка константы. Что можно улучшить?

[kdv2005.livejournal.com]

В смысле, логарифм или константу при логарифме?

[kdv2005.livejournal.com]

Вру, за 3.5 шага. В ответе нужно заменить 4 на 3.5

[spamsink]

И от 3.5 тоже есть куда.

[kdv2005.livejournal.com]

Ну хорошо, a лучше, чем 0.5 log₂N можно?

[spamsink]

Если у весов разрешение было бы лучше, то все равно было бы не меньше log2(N), куда уж там 0.5.

[kdv2005.livejournal.com]

Мне кажется, что при точных весах ответ для стандартного двоичного поиска будет с K=0.5, a не с K=1.

[spamsink]

Если у нас 4 монеты, то нужно два взвешивания, а не одно.

[kdv2005.livejournal.com]

Я имел в виду константу K, a не поправку к ответу типа Klog N +1. Поэтому нужно проверять для больших значений N, например дла тысячи монет или миллиона.

[kdv2005.livejournal.com]

Да, я ошибся. Если весы точные, то K=1, конечно.

[spamsink]

Можно улучшить и то, и другое. Понятно, что все формулы числа взвешиваний можно привести к виду K*log₂N, поэтому будем выражать результат в виде константы при двоичном логарифме. От K=4 есть еще далеко куда двигаться вниз.

[kdv2005.livejournal.com]

Сдаюсь. Я не вижу как можно улучшить ответ в 3.5 взвешивания для двух монет.

[spamsink]

Для N=2 улучшать действительно некуда, но интересно, чему равно K для больших N.

[kdv2005.livejournal.com]

Что-то я на двоичном поиске зациклился. Если что-нибудь еще в голову придет, тогда еще раз попробую.

[krotty.livejournal.com]

пусть x - вероятность что монета в куче, которую мы взвешиваем, тогда (1-x) что монета в другой куче.
полная информация такого состояния - h(x) = x log2(1/x) + (1-x) log2(1/(1-x))
после взвешивания мы либо с вероятностью x/2 оказваемся в h(1) или с вероятностью (1-x/2) в состоянии h(x/(2-x)).

Надо найти x при котором h(x) - (1-x/2)* h(x/2-x) максимально.

[spamsink]

В последней строке скобки в аргументе h пропущены. Правильно, но т.к. программы Математика у меня нет, то в части оптимального значения х я поверил на слово источнику этой задачки - это 0.4.

[sab123.livejournal.com]

Гм, получается, что выгоднее всего - просто перебирать все монеты по очереди пока не найдется правильная.

Если мы пойдем методом двоичного деления:

Делим пополам, взвешиваем. Если показало кривой вес - фальшивая монета в этой кучке, делим ее на две кучки и дальше с тем же алгоритмом. Иначе взвешиваем вторую полкучку. Если показало кривой вес - то аналогично.

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

Если мы обозначим четверные кучки A, B, C, D, то для каждой из них для точного знания о том, что монета в ней, потребуется количество взвешиваний:

Двоичным делением:
A: 2
B: 3
C: 3
D: 4

Последовательным взвешиванием каждой черверть-кучки:
A: 1
B: 2
C: 3
D: 4

Т.е. последовательный перебор выигрывает.

Потом если каждая из 4 кучек показала прямой вес - то делим уже на 8 кучек, из тех же соображений, и повторяем с ними. Но! Что мешало нам изначально поделить монеты на столько кучек, сколько возможно? Т.е. самая выгодная стратегия - взвешивать каждую монету по очереди.

[spamsink]

Взвешивать все монеты по очереди даже на точных весах дает количество взвешиваний в среднем N/2. Оптимальный же алгоритм даже на данных весах дает K*log₂N.