中文

Operations Research Transactions >

2016 , Vol. 20 >Issue 4: 102 - 108

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2016.04.012

Searching for two counterfeit coins

Expand
  • 1. School of Mathematical Sciences, Shanxi University, Taiyuan 030006, China

Received date: 2016-05-25

  Online published: 2016-12-15

Fold

Abstract

The following weighting problem is considered: determine two counterfeit coins which are heavier than good coins in a set of n coins of the same appearance using only an equal arms balance. Let L^{(2)}(n) denote the minimum number of weighings necessary when exactly two of n coins are known to be  defective. For all n\geq 2, it satisfies \lceil \log_3\binom{n}{2}\rceil \leq L^{(2)}(n)\leq\lceil \log_3\binom{n}{2}\rceil+1. It was conjectured that the lower bound is always achieved. In this paper, using an novel algorithm, we improve on the range of n for which the lower bound is reached.

Key words： combinatorial search; group testing; weighting problem; two counterfeit coins

Cite this article

WU Xiaohui, LI Shengjia . Searching for two counterfeit coins[J]. Operations Research Transactions, 2016 , 20(4) : 102 -108 . DOI: 10.15960/j.cnki.issn.1007-6093.2016.04.012

References

[1] Aigner M. Combinatorial Search} [M]. New York: Wiley-Teubner, 1988, 80-98.
[2] Manvel B. Counterfeit coin problems [J]. Siam Journal on Computing, 1977, 50: 90-92.
[3] Li A.  Note on the conjecture at two counterfeit coins [J]. Discrete Mathematics, 1994, 133:301-306.
[4] Aigner M, Li A. Searching for counterfeit coins [J]. Graphs and Combinatorics, 1997, 13: 9-20.
[5] Bellman R, Glass B. On various versions of the defective coin problem [J]. Information \& Control, 1961, 4: 119-131.
[6] Pyber  L. How to find many counterfeit coins? [J]. Graphs and Combinatorics, 1986, 2: 173-177.
[7] Ratko To\v{s}\.{i}\`{c}．Two counterfeit coins [J]．Discrete Mathematics, 1983, 45: 295-298．
[8] Ratko To\v{s}\.{i}\`{c}．Three counterfeit coins [J]．Review of Research Faculty of Science University of Novi sad Mathematics series, 1985, 15: 224-233．
[9] Ratko To\v{s}\.{i}\`{c}．Four counterfeit coins [J]．Review of Research Faculty of Science University of Novi sad Mathematics series, 1984, 14: 99-108．
[10] Ratko To\v{s}\.{i}\`{c}. Five counterfeit coins [J]. Journal of Statistical Planning \& Inference, 1989, 22: 197-202．
[11] Hu X D, Chen P D, Hwang F K. A new competitive algorithm for the counterfeit coin problem [J]. Information Processing Letters, 1994, 51(4): 213-218.
[12] Hu X D, Hwang F K. A Competitive Algorithm for the Counterfeit Coin Problem} [M]. Dordrecht: Kluwer Academic Publisher, 1995, 213-218.
[13] Du D Z, Hwang F K. Combinatorial Group Testing and its Applications(2nd Edition) [M]. Singapore: World Scientific, 2000.
[14] Bonis A De. A predetermined algorithm for detecting a counterfeit coin with a multi-arms balance [J]. Discrete Applied Mathematics, 1998, 86: 181-200.
[15] Bonis De A , Gargano L, Vaccaro U. Optimal detection of a counterfeit coin with multi-arms balances [J]. Discrete Applied Mathematics, 1995, 61: 121-131.
[16] Liu W A , Zhang Q M , Nie Z K . Optimal search procedure on coin-weighing problem [J]. Journal of Statistical Planning and Inference, 2006, 136: 4419-4435.
[17] Liu W A , Zhang Q M , Nie Z K.  Searching for two counterfeit coins with two-arms balance [J].  Discrete Applied Mathematics, 2005, 152: 187-212.
Options
Outlines

/

〈 〉