Four counterfeit coins problem
Let \(S\) be the set of \(n\) coins, in which there are \(m\) counterfeit coins, heavier (or lighter) than the normals. Denote by \(g_m (n)\) the least number of weighings with a balance to find the \(m\) counterfeit coins. It is well-known that \[ g_1 (n)= \lceil \log_3 n\rceil. \] \textit{R. Tošić} [Discrete Math. 46, 295-298 (1983; Zbl 0518.05004)]\ obtained that \[ g_2 (n)\leq \Biggl\lceil \log_3 {n\choose 2} \Biggr\rceil +1. \] The first author [ibid. 133, No. 1/3, 301-306 (1994; Zbl 0811.90063)]\ improved that \[ g_2 (n)\leq \Biggl\lceil \log_3 {n\choose 2}+ 0.03 \Biggr\rceil. \] In [J. Comb. Theory, Ser. A 66, No. 1, 93-101 (1994; Zbl 0799.90126)]\ the first author gave the following result \[ g_3 (n)\leq \Biggl\lceil \log_3 {n \choose 3}+ 1.25 \Biggr\rceil. \] In this paper, we obtain that \[ g_4 (n)\leq \Biggl\lceil \log_3 {n\choose 4} \Biggr\rceil +2, \] and, for \(n\in [3^l, 2\times 3^l ]\cup [\root 4\of {72} \times 3^l+ 2, 3^{l+1} ]\), \[ g_4 (n)\leq \Biggl\lceil \log_3 {n \choose 4} \Biggr\rceil +1. \] In an alternate paper [Graphs Combin, to appear], the first author, with \textit{M. Aigner}, proved that \[ g_m (n)\leq \Biggl\lceil \log_3 {n\choose m} \Biggr\rceil+ 1.5m+ 9. \]
- The general counterfeit coin problem
- scientific article; zbMATH DE number 999579 (Why is no real title available?)
- scientific article; zbMATH DE number 3896639 (Why is no real title available?)
- scientific article; zbMATH DE number 1375194 (Why is no real title available?)
- Searching for counterfeit coins
This page was built for publication: Four counterfeit coins problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1909424)
