Bestimmen Sie die Mindestanzahl der Münzwägungen

In der Arbeit Zu zwei Problemen der Informationstheorie geben Erdõs und Rényi Untergrenzen für die Mindestanzahl von Wägungen an, die zur Bestimmung der Anzahl falscher Münzen in einem Satz von Münzen erforderlich sind .$n$

Formeller:

Die falschen Münzen haben ein geringeres Gewicht als die richtigen Münzen; Die Gewichte und b < a sowohl der richtigen als auch der falschen Münze sind bekannt. Es wird eine Skala angegeben, mit der eine beliebige Anzahl ≤ n Münzen zusammen gewogen werden kann. Wenn wir also eine beliebige Teilmenge der Münzen auswählen und auf der Waage zusammenfügen, zeigt uns die Waage das Gesamtgewicht dieser Münzen, aus dem sich leicht die Anzahl der falschen Münzen unter den gewogenen Münzen berechnen lässt. Die Frage ist, wie hoch die Mindestanzahl A ( n ) der Wägungen ist, mit denen die richtige und die falsche Münze getrennt werden können.$a$$b < a$$\leq n$$A(n)$

Die triviale Untergrenze, die sie anfänglich bereitstellen, ist:

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

Dies ist nicht schwer zu verstehen, warum durch verschiedene informationstheoretische oder kombinatorische Argumente. Das Problem ist, wie man solche Sets konstruiert, um diese Wägungen durchzuführen? Gibt es Algorithmen, die einen konstruktiven Beweis verwenden, um diese unteren Grenzen zu erreichen, ohne sich auf Zufälligkeit zu verlassen? Gibt es randomisierte Algorithmen, die diese Grenzen erreichen?

Ich habe mir dieses Papier kurz angesehen , und es scheint, dass die Antwort auf Ihre Frage Ja lautet (dh keine Randomisierung erforderlich ist). Im Abschnitt Einführung werden auch frühere Algorithmen, informationstheoretische Untergrenzen usw. untersucht.