# Algorithm Debate CounterfeitBall

We present the problem first in English followed by a logical formulation.

## Plain English

There are given n balls with the same appearance and weight except that one counterfeit ball has a slightly different weight. You are also given a scale which you use to find the counterfeit ball which is either heavier or lighter than the other balls. The scale allows for the following basic operation: you compare the weights of two sets of balls: the balls in the left bowl and the balls in the right bowl of the scale. The scale says which set is lighter. How many basic operations do you need to find the counterfeit ball? You want to minimize the number of basic operations.

## Logical Formalism

```Claim CounterfeitBall(n,q in Nat)=
ForAll sets of n balls with n-1 of them having identical weight and one ball
(called the counterfeit ball) having either higher or lower weight
Exists a sequence of q basic weighing operations:
The counterfeit ball is correctly found.

Claim MinCounterfeitBall()=
ForAll n
Exists q
CounterfeitBall(n,q) and
(ForAll q'< q: !(CounterfeitBall(n,q')))
```