Algorithm Debate CounterfeitBall
We present the problem first in English followed by a logical formulation.
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.
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.
(ForAll q'< q: !(CounterfeitBall(n,q')))