Minimal average cost of searching for a counterfeit coin: restricted model. (English) Zbl 1180.68307
Summary: The following restricted model of coin-weighing problem is considered: there is a heavier coin in a set of \(n\) coins, \(n-1\) of which are good coins having the same weight. The test device is a two-arms balance scale and each test-set is of the form \(A:B\) with \(|A|=|B|\le l\), where \(l\geq 1\) is a given integer. We present an optimal sequential algorithm requiring the minimal average cost of weighings when the probability distribution on the coin set is uniform distribution.
MSC:
| 68W40 | Analysis of algorithms |
| 05A99 | Enumerative combinatorics |
| 68R05 | Combinatorics in computer science |
References:
| [1] | Aigner, M., Combinatorial Search (1988), Wiley-Teuber: Wiley-Teuber New York · Zbl 0663.68076 |
| [2] | Aigner, M.; Li, A. P., Searching for counterfeit coins, Graphs Combin., 13, 9-20 (1997) · Zbl 0869.05001 |
| [3] | De Bonis, A., A predetermined algorithm for detecting a counterfeit coin with a multi-arms balance, Discrete Appl. Math., 86, 181-200 (1998) · Zbl 0906.68050 |
| [4] | De Bonis, A.; Gargano, L.; Vaccaro, U., Optimal detection of a counterfeit coin with multi-arms balances, Discrete Appl. Math., 61, 121-131 (1995) · Zbl 0831.68030 |
| [5] | Du, D. Z.; Hwang, F. K., Combinatorial Group Testing and its Applications (2000), World Scientific: World Scientific Singapore · Zbl 0749.90035 |
| [6] | Guy, P. K.; Nowakowski, R. J., Coin-weighing problems, Amer. Math. Monthly, 102, 164-167 (1995) · Zbl 0866.05009 |
| [7] | Halbeisen, L.; Hungerbühler, N., The general counterfeit coin problem, Discrete Math., 147, 139-150 (1995) · Zbl 0838.05004 |
| [8] | Katona, G. O.H., Search with small sets in presence of a liar, J. Statist. Plann. Inference, 100, 319-336 (2002) · Zbl 1048.90115 |
| [9] | Li, A. P., On the conjecture at two counterfeit coins, Discrete Math., 133, 301-306 (1994) · Zbl 0811.90063 |
| [10] | Linial, N.; Tarsi, M., The counterfeit coin problem revisited, SIAM J. Comput., 11, 409-415 (1982) · Zbl 0486.68053 |
| [11] | Liu, W. A.; Nie, Z. K., Optimal detection of two counterfeit coins with two-arms balance, Discrete Appl. Math., 137, 267-291 (2004) · Zbl 1040.68030 |
| [12] | Liu, W. A.; Zhang, Q. M.; Nie, Z. K., Searching for a counterfeit coins with two unreliable weighings, Discrete Appl. Math., 150, 160-181 (2005) · Zbl 1071.05003 |
| [13] | Liu, W. A.; Zhang, W. G.; Nie, Z. K., Searching for two counterfeit coins with two-arms balance, Discrete Appl. Math., 152, 187-212 (2005) · Zbl 1085.05004 |
| [14] | W.A. Liu, Q.M. Zhang, Z.K. Nie, Optimal search procedure on coin-weighing problem, J. Statist. Plann. Inference, to appear.; W.A. Liu, Q.M. Zhang, Z.K. Nie, Optimal search procedure on coin-weighing problem, J. Statist. Plann. Inference, to appear. · Zbl 1098.90037 |
| [15] | Pelc, A., Searching games with errors-fifty years of coping with liars, Theoret. Comput. Sci., 270, 71-109 (2002) · Zbl 0984.68041 |
| [16] | Pyber, L., How to find many counterfeit coins, Graphs Combin., 2, 173-177 (1986) · Zbl 0593.05002 |
| [17] | Tošić, R., Two counterfeit coins, Discrete Math., 46, 295-298 (1983) · Zbl 0518.05004 |
| [18] | Tošić, R., Five counterfeit coins, J. Statist. Plann. Inference, 22, 197-202 (1989) · Zbl 0672.90078 |
| [19] | Wegener, I., On separating systems whose elements are sets of at most \(k\) elements, Discrete Math., 28, 219-222 (1979) · Zbl 0416.05003 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
