Four counterfeit coins problem (Q1909424)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Four counterfeit coins problem
scientific article

    Statements

    Four counterfeit coins problem (English)
    0 references
    0 references
    0 references
    1 August 1996
    0 references
    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. \]
    0 references
    information-theoretic bound
    0 references
    counterfeit coins
    0 references

    Identifiers