# How to detect a counterfeit coin: Adaptive versus non-adaptive solutions

Born, Axel
and
Hurkens, Cor A.J.
and
Woeginger, Gerhard J.
(2003)
*How to detect a counterfeit coin: Adaptive versus non-adaptive solutions.*
Information Processing Letters, 86
(3).
pp. 137-141.
ISSN 0020-0190

PDF
Restricted to UT campus only : Request a copy 81kB |

Abstract: | In an old weighing puzzle, there are n3 coins that are identical in appearance. All the coins except one have the same weight, and that counterfeit one is a little bit lighter or heavier than the others, though it is not known in which direction. What is the smallest number of weighings needed to identify the counterfeit coin and to determine its type, using balance scales without measuring weights? This question was fully answered in 1946 by Dyson [The Mathematical Gazette 30 (1946) 231–234]. For values of n that are divisible by three, Dyson's scheme is non-adaptive and hence its later weighings do not depend on the outcomes of its earlier weighings. For values of n that are not divisible by three, however, Dyson's scheme is adaptive. In this note, we show that for all values n3 there exists an optimal weighing scheme that is non-adaptive. |

Item Type: | Article |

Copyright: | © 2003 Elsevier |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/75027 |

Official URL: | http://dx.doi.org/10.1016/S0020-0190(02)00483-0 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 213205