How to find many counterfeit coins? (English) Zbl 0593.05002
Author’s abstract: ”We propose an algorithm for finding m defective coins, that uses at most \(\lceil \log_ 3\left( \begin{matrix} n\\ m\end{matrix} \right)\rceil +15m\) weighings on a balance scale, where n is the number of all coins.”
Reviewer: P.Reichensperger
References:
| [1] | Bellman, R.: Dynamic Programming. Princeton: Princeton Univ. Press 1957 · Zbl 0077.13605 |
| [2] | Bellman, R., Glass, B.: On various versions of the defective coin problem. Inf. Control4, 119–131 (1961) · Zbl 0105.33403 |
| [3] | Cairns, S.S.: Balance scale sorting. Amer. Math. Mon.70, 136–143 (1963) · Zbl 0116.12404 · doi:10.2307/2312882 |
| [4] | Katona, G.O.H.: Combinatorial search problems. In: A Survey of Combinatorial Theory, edited by J.N. Srivastava, et al., pp. 285–308. Amsterdam: North Holland 1973 |
| [5] | Manvel, B.: Counterfeit coin problems. Math. Mag.50, 90–92 (1977) · Zbl 0353.05001 · doi:10.2307/2689732 |
| [6] | Mead, D.G.: The average number of weighings to locate a counterfeit coin. IEEE Trans. Inf. Theory25, 616–617 (1979) · Zbl 0414.05002 · doi:10.1109/TIT.1979.1056091 |
| [7] | Smith, C.A.B.: The counterfeit coin problem. Math. Gaz.31, 31–39 (1947) · doi:10.2307/3608991 |
| [8] | Tosic, R.: Two counterfeit coins. Discrete Math.46, 295–298 (1983) · Zbl 0518.05004 · doi:10.1016/0012-365X(83)90123-1 |
| [9] | Tosic, R.: Three counterfeit coins (to appear) · Zbl 0518.05004 |
| [10] | Tosic, R.: Four counterfeit coins. Rev. Res. Fac. Sci. Univ. Novi Sad14, 97–108 (1984) · Zbl 0562.90036 |
| [11] | Winkelmann, K.: An improved strategy for a counterfeit coin problem. IEEE Trans. Inf. Theory28 120–122 (1982) · Zbl 0472.05002 · doi:10.1109/TIT.1982.1056434 |
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.
