<p>This is called the "Counterfeit Coin Problem" contributed by E. D. Schell and we have the following theorem according to the <a href="https://www.jstor.org/stable/2689732?seq=1#page_scan_tab_contents" rel="nofollow noreferrer">paper "Counterfeit Coin Problem", 1977</a>:</p>

<blockquote>
  <p>Theorem 1: Let $S$ be a set of coins, one lighter than the rest. 
  The least number of weighings on a beam balance in which the light coin can be found is the unique $n$ satisfying $3^{n-1} &lt; |S| \le 3^n$.</p>
</blockquote>

<p>This bound is tight.</p>

<p>The paper also studies a more difficult variant of this problem, assuming only that the counterfeit coin is a different weight from the others -- either heavier or lighter.</p>

CC BY-SA 4.0
2018-06-26T07:21:02.833Z
Please do not answer off-topic questions.
Emil Jeřábek
CC BY-SA 4.0
2018-06-26T02:24:52.300Z
2018-06-26T02:24:52.300Z
hengxin
<p>We have n balls where 1 is a little heavier than the others and we want to find that heavier ball. We can only put some balls on one side of the scale and some on the other side and see if it leans and to which side. How can we find lower and upper bounds for this problem? We want upper and lower bounds to be equal.</p>

<cc.complexity-theory><time-complexity><lower-bounds><upper-bounds>
Finding upper and lower bounds of a problem
Yhprums
# Finding upper and lower bounds of a problem

(Asked by: username_0 on 2018-06-25)

We have n balls where 1 is a little heavier than the others and we want to find that heavier ball. We can only put some balls on one side of the scale and some on the other side and see if it leans and to which side. How can we find lower and upper bounds for this problem? We want upper and lower bounds to be equal.

**Tags:** cc.complexity-theory, time-complexity, lower-bounds, upper-bounds

---

## 1 answers

### Answer by username_1 on 2018-06-26. Score: 0 | Accepted answer

This is called the "Counterfeit Coin Problem" contributed by E. D. Schell and we have the following theorem according to the [paper "Counterfeit Coin Problem", 1977](https://www.jstor.org/stable/2689732?seq=1#page_scan_tab_contents):

> Theorem 1: Let $S$ be a set of coins, one lighter than the rest.
> The least number of weighings on a beam balance in which the light coin can be found is the unique $n$ satisfying $3^{n-1} < |S| \le 3^n$.

This bound is tight.

The paper also studies a more difficult variant of this problem, assuming only that the counterfeit coin is a different weight from the others -- either heavier or lighter.

> **Comments:**
> **username_2**: Please do not answer off-topic questions.  

---

