Search for Three Forged Coins
| dc.creator | Zhai, Shaohui | |
| dc.date | 2000-09-08 | |
| dc.date | 2000-09-10 | |
| dc.date.accessioned | 2026-07-07T04:37:18Z | |
| dc.date.available | 2026-07-07T04:37:18Z | |
| dc.description | Suppose we are given a set of t coins which look identical, but a known number s of them are counterfeit, with a known weight different from the others. Our problem is to locate the counterfeits by weighing subsets of the t coins, with as few weighings as possible. Despite a large literature on this problem, it remains wide open for s>2. In this paper, we give an efficient sequential weighing algorithm for the case s=3, with an average of 1.75 weighings per bit of t, as t approaches infinity. (It is known that any algorithm must have more than 1.5 weighings per bit.) We use our algorithm to give an efficient channel coding for the three-sender multiple-access adder channel with feedback. | |
| dc.description | six pages | |
| dc.identifier | https://arxiv.org/abs/math/0009096 | |
| dc.identifier | http://arxiv.org/abs/math/0009096 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/59905 | |
| dc.subject | Combinatorics | |
| dc.title | Search for Three Forged Coins | |
| dc.type | text |