𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The general counterfeit coin problem

✍ Scribed by Lorenz Halbeisen; Norbert Hungerbühler

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
446 KB
Volume
147
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Given c nickels among which there may be a counterfeit coin, which can only be told apart by its weight being different from the others, and moreover b balances, what is the minimal number of weighings to decide whether there is a counterfeit nickel, if so which one it is and whether it is heavier or lighter than a genuine nickel. We give an answer to this question for sequential and nonsequential strategies and we will consider the problem of more than one counterfeit coin.

📜 SIMILAR VOLUMES

A (log23 + 12) competitive algorithm for
A (log23 + 12) competitive algorithm for the counterfeit coin problem
✍ Peng-Jun Wan; Ding-Zhu Du 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 912 KB

Consider a set of coins where each coin is either of the heavy type or the light type. The problem is to identify the type of each coin with minimal number of weighings on a balanced scale. The case that only one coin, called a counterfeit, has a different weight from others, is a classic mathematic

A 32log 3-competitive algorithm for the
A 32log 3-competitive algorithm for the counterfeit coin problem
✍ Peng-Jun Wan; Qifan Yang; Dean Kelley 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 524 KB

We study the following counterfeit coin problem: Suppose that there is a set of II coins. Each one is either heuuy or light. The goal is to sort them according to weight with a minimum number of weighings on a balance scale. Hu and Hwang gave an algorithm with a competitive ratio of 3 log 3 (all log

On the conjecture at two counterfeit coi
On the conjecture at two counterfeit coins
✍ Anping Li 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 284 KB

Suppose among the given n coins there are two counterfeit coins, which are heavier (or lighter) than the normals. Denote by g,(n) the minimum number of weighings that suffice to search the two false coins by a balance. It is guessed that g&)=rlog,(;)l . This paper affirms the conjecture.