两伪币的搜索问题

doi:10.15960/j.cnki.issn.1007-6093.2016.04.012

运筹学学报

两伪币的搜索问题

武晓辉^1,* 李胜家¹

1. 山西大学数学科学学院, 太原 030006

收稿日期:2016-05-25 出版日期:2016-12-15 发布日期:2016-12-15
通讯作者: 武晓辉 18734838796@163.com
基金资助:
基金项目: 国家自然科学基金(No. 61174082)

Searching for two counterfeit coins

WU Xiaohui^1,*LI Shengjia¹

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

Received:2016-05-25 Online:2016-12-15 Published:2016-12-15

摘要/Abstract

摘要：

考虑两伪币的搜索问题: 给定外观相同的n个硬币, 其中有两个比较重的伪币, 通过等臂天平在尽可能少的称量次数下去找出两个伪币. L^{(2)}(n)为最坏情况下找到两伪币的最小称量步数. 对于任意的 n\geq2, 满足\lceil \log_3\binom{n}{2}\rceil \leq L^{(2)}(n)\leq\lceil \log_3\binom{n}{2}\rceil+1. 猜想信息理论下界均可达. 通过一个新的方法扩大了满足信息理论下界的n的取值范围.

关键词: 组合搜索, 组测试, 称重问题, 两伪币

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

武晓辉, 李胜家. 两伪币的搜索问题[J]. 运筹学学报, doi: 10.15960/j.cnki.issn.1007-6093.2016.04.012.

WU Xiaohui, LI Shengjia. Searching for two counterfeit coins[J]. Operations Research Transactions, doi: 10.15960/j.cnki.issn.1007-6093.2016.04.012.

参考文献

[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.

两伪币的搜索问题

Searching for two counterfeit coins

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价