Mathematics
ComputerScience,1970-2008-Computer Science-2000.jsonl.gz.gz
Computer Science Mathematics
9e9a187f22626bb600766c709bec4d10c49b6772
Search for Three Forged Coins

Suppose we are given a set of t coins which look identical, but a known number s of them are counterfeit, with a known weight different from the others. Our problem is to locate the counterfeits by weighing subsets of the t coins, with as few weighings as possible. Despite a large literature on this problem, it remains wide open for s>2. In this paper, we give an efficient sequential weighing algorithm for the case s=3, with an average of 1.75 weighings per bit of t, as t approaches infinity. (It is known that any algorithm must have more than 1.5 weighings per bit.) We use our algorithm to give an efficient channel coding for the three-sender multiple-access adder channel with feedback.


Problem
Let T be a set of t coins which are either genuine or forged. Genuine coins have normalized weight 0, forged coins have normalized weight 1, so that for any subset W of T , the weight of W , written by wt(W ), is the number of forged coins in W . Since one weighing can determine the number of forged coins in T , we assume that the number of the forged coins in T is known and denoted by s. We want to identify all the forged coins in T by weighing some subsets of T , with as few weighings as possible.
In a static weighing algorithm, all the subsets chosen to weigh are determined in advance; in a sequential weighing algorithm, each subset depends on all the previous weighing results.
In this paper, we give a sequential weighing algorithm for s = 3 forged coins, which is efficient when the total number of coins t is large. For convenience, we assume that t = 2 m for some m. If t is not a power of 2, we can add "dummy" genuine coins to make up the number without affecting the asymptotic efficiency of an algorithm.

The Algorithm: Three Stages
Stage 0. We reduce T to three disjoint subsets, T 1 , T 2 , T 3 , with exactly one forged coin in each set and with |T 1 | = |T 2 | = |T 3 | = 2 n for some n. First, we bisect T and weigh one of the halves. If the weighing result is 0 or 3, we bisect the half with 3 forged coins and weigh one of the quarters. We continue these bisections until the weighing result is 1 or 2. Suppose l 1 steps are needed and the resulting subsets are T ′ and T ′′ , containing one and two forged coins, respectively. Next, we bisect T ′′ until the weighing result is 1. Suppose l 2 steps are needed and the resulting subsets are denoted by T 1 and T 2 . Finally, we do l 2 bisections on T ′ and denote the resulting subset with one forged coin by T 3 .
Stage 0 takes l 1 + 2l 2 weighings and n = m − l 1 − l 2 . Label each coin in T i by a distinct binary sequence of length n. Let c indicate the label of a coin; c (i) the i-th digit of c; and c 1 , c 2 , c 3 the labels of the three forged coins in T 1 , T 2 , T 3 respectively. Stage 1. We do n static weighings. The i-th weighing is the subset W i of all coins in T 1 , T 2 , and T 3 whose i-th digit is 1: = 0 (resp. = 1). If wt(W i ) = 1 or 2, then the ith digit of c 1 , c 2 and c 3 is not completely determined, and we call such a position an ambiguity. If wt(W i ) = 1, exactly one of c 3 is 0. Suppose there are l 3 weighings with result 1 or 2.
The results of Stage 1 and Stage 2 are illustrated in the following table.
Lemma. The mean number N of weighings in the algorithm is Proof. In Stage 0, l 1 is the number of weighings for the first occurrence of a weighing result of 1 or 2 to appear. Consider the first occurrence of a weighing result 1 or 2 to be a geometric random variable, then the probability to have l 1 weighings is 3 4 ( 1 4 ) l 1 −1 , since the probability of getting weighing result 1 or 2 is 3 4 . Similarly, the probability to have l 2 weighings is 2 −l 2 , since the probability of getting weighing result 1 is 1 2 . In Stage 1, the number of weighings is n = m − l 1 − l 2 . In Stage 2, the probability of having l 3 ambiguities is n l 3 ( 3 4 ) l 3 ( 1 4 ) n−l 3 , and l 3 weighings is needed to resolve the l 3 ambiguities. • Simplifying the formula in the Lemma, we get . We use the asymptotic rate R to measure the efficiency of an algorithm when t goes to infinity. Then the rate of this weighing algorithm is The best known weighing algorithm is Lindström's [1] static algorithm which gives R = 0.46. The theoretical rate bound for static weighing algorithm is 0.6 [2]. The theoretical rate bound for sequential weighing algorithm is unknown.

Corresponding code for three-user Adder
Channel with noiseless feedback The three-user Multiple Access Adder Channel takes three independent binary inputs and outputs a ternary symbol which is the sum of the three inputs. The communication system of this channel with noiseless feedback is illustrated in Fig. 1. , the encoders send their binary codewords symbol by symbol simultaneously. The output of each transmission is the sum of all the three input symbols. With the noiseless feedback channel, each encoder knows all the previous output symbols, and then decides its next input symbol, depending on the message itself and all the previous outputs.
We derive a simple and efficient zero-error code from the algorithm in Section 2 for this channel. Let can not be completely determined, since we only know that exactly one of them is 1 when y k = 1, and exactly one of them is 0 when y k = 2, such a position is called an ambiguity. Suppose that there are a such ambiguities after the first l transmissions. In Stage 2, we will resolve these a ambiguous positions.