On a combinatory detection problem I.

Lindström, Bernt (1964) On a combinatory detection problem I. A MAGYAR TUDOMÁNYOS AKADÉMIA MATEMATIKAI KUTATÓ INTÉZETÉNEK KÖZLEMÉNYEI, 9 (1-2). pp. 195-207.

Preview

Text cut_MATKUTINT_1964_1_-_2_pp195_-_207.pdf - Published Version Download (5MB) | Preview

Abstract

The present investigation was inspired by the work of H. S. Shapiro and S. Söderberg [4] on a weighing problem: "Counterfeit coins weigh 9 grams and genuine coins weigh 10 grams. Given a scale that weighs all real numbers exactly, what is the minimum number of weighings required to extract all the counterfeits from a sample of n coins"?. The schemes for finding the counterfeits are of two kinds; (1) either one determines in advance which coins are to be weighed together in each weighing or (2) the choice of coins for a weighing is made t o depend on the results of all previous weighings. I shall only consider schemes of the first kind. Then the problem can be given a formulation in terms of sets. Detection Problem. Let S be a given set of | S | = n elements. A family F f subsets T₁, T₂, . . ., Tₘ of S is a detecting family for S if each subset M of S is uniquely determined by the m numbers | M ∩ Tᵢ | , i= 1, 2, . . ., m. Then the problem is to find f(n) = min m is the class of all detecting families for S. It is easy to prove that f(4) = 3 and f(5) = 4, but for larger n the determination of f(n) is difficult. Therefore one must in the first instance search for good estimates. Since there are at most (n + l)ᵐ combinations of values for the numbers | M ∩ Tᵢ |, (i = 1, . . ., m) and different combinations correspond to the 2ⁿ different subsets of S, we find that 2ⁿ ≦ (n + l)ᵐ and (1.1) f(n) ≧ n log 2/log (n + 1). The main achievement of H . S . Shapiro and S. Söderberg was the proof of (1.2) f(n) = 0( n/log n ). P. Erdős and A. Rényi have given a proof [1] of the inequality (1.3) lim infₙ→∞ f(n) log/n ≧ log 4. This inequality has also been proved by B. Gordon, L. Moser and myself (see [1] Remark). Although my proof is not the shortest it may have some interest as an application of information theory. But my main result is (1.4) lim supₙ→∞ f(n) log/n ≧ log 4, thus confirming a conjecture in [1] that the limit exists. I am grateful to Professor H. S. Shapiro for stimulating discussions during his stay in Stockholm. I also express my thanks to Prof. 0. Frostman, who suggested many simplifications in my proofs.

Actions (login required)

Edit Item