Określ minimalną liczbę ważeń monet

W artykule Na temat dwóch problemów teorii informacji Erdõs i Rényi wyznaczają dolne granice minimalnej liczby ważeń, które należy zrobić, aby określić liczbę fałszywych monet w zestawie monet.$n$

Bardziej formalnie:

Fałszywe monety mają mniejszą wagę niż właściwe monety; znane są wagi i zarówno prawych, jak i fałszywych monet. Podana jest skala, za pomocą której można zważyć razem dowolną liczbę monet. Zatem jeśli wybieramy dowolny podzbiór monet i zestawimy je razem na skali, wówczas skala pokazuje nam całkowitą wagę tych monet, z której łatwo jest obliczyć liczbę fałszywych monet wśród ważonych. Pytanie brzmi: jaka jest minimalna liczba ważeń za pomocą których można oddzielić prawą i fałszywą monetę?$a$$b < a$$\leq n$$A(n)$

Trywialna dolna granica, którą początkowo zapewniają, to:

$n / \log_2 (n + 1)$ .

Nietrudno jest zrozumieć, dlaczego poprzez różne argumenty teoretyczne lub kombinatoryczne. Problem polega na tym, jak zbudować takie zestawy, aby wykonać te ważenia? Czy istnieją algorytmy, które wykorzystują konstruktywny dowód, aby osiągnąć te dolne granice bez polegania na przypadkowości? Czy istnieją losowe algorytmy, które osiągają te granice?

Rzuciłem okiem na ten artykuł i wydaje się, że odpowiedź na twoje pytanie brzmi „tak” (to znaczy - nie ma potrzeby randomizacji). Ponadto sekcja Wprowadzenie zawiera przegląd poprzednich algorytmów, teoretycznych informacji o dolnych granicach i tak dalej.