Treffer: Optimal detection of two counterfeit coins with two-arms balance

Title:
Optimal detection of two counterfeit coins with two-arms balance
Authors:
WEN-AN, Liu, ZAN-KAN, Nie
Source:
Discrete applied mathematics. 137(3):267-291
Publisher Information:
Amsterdam; Lausanne; New York, NY: Elsevier, 2004.
Publication Year:
2004
Physical Description:
print, 13 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Combinatoire, Combinatorics, Plans d'expériences et configurations, Designs and configurations, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Logiciel, Software, Organisation des mémoires. Traitement des données, Memory organisation. Data processing, Traitement des données. Listes et chaînes de caractères, Data processing. List processing. Character string processing, Algorithme optimal, Optimal algorithm, Algoritmo óptimo, Algorithme recherche, Search algorithm, Algoritmo búsqueda, Analyse combinatoire, Combinatorial analysis, Análisis combinatorio, Borne supérieure, Upper bound, Cota superior, Détection, Detection, Detección, Informatique théorique, Computer theory, Informática teórica, Méthode cas pire, Worst case method, Método caso peor, Pièce monnaie, Coin, Pieza moneda, Théorie information, Information theory, Teoría información, Algorithme séquentiel, Sequential algorithm
Document Type:
Fachzeitschrift Article
File Description:
text
Language:
English
Author Affiliations:
Faculty of Science, Xi'an Jiaotong University, Xi'an 710049, China
Faculty of Mathematics and Information Science, Henan Normal University, Xinxiang 453002, China
ISSN:
0166-218X
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=15516115
Rights:
Copyright 2004 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Mathematics
Accession Number:
edscal.15516115
Database:
PASCAL Archive

Weitere Informationen

We consider the following coin-weighing problem: suppose among the given n coins there are two counterfeit coins, which are either heavier or lighter than other n - 2 good coins, this is not known beforehand. The weighing device is a two-arms balance. Let NA(k) be the number of coins from which k weighings suffice to identify the two counterfeit coins by algorithm A and U(k) = max{n|n(n - 1) ≤ 3k} be the information-theoretic upper bound of the number of coins then NA(k) ≤ U(k). We establish a new method of reducing the above original problem to another identity problem of more simple configurations. It is proved that the information-theoretic upper bound U(k) are always achievable for all even integer k ≥ 1. For odd integer k ≥ 1, our general results can be used to approximate arbitrarily the information-theoretic upper bound. The ideas and techniques of this paper can be easily employed to settle other models of two counterfeit coins.