We can assume that there is one and only one football that is heavier.
Regardless of the total number of football’s, it only makes sense to weigh an equal quantity in the left and right pans of the scale.
Let’s examine the case of eight football’s first.
We could start by weighing one football in each pan.
If the scale is unbalanced, then we are done. We know the heavier
outlierBall , best case.
If the scale is balanced, then we can discard the two normal football’s we just weighed.
Now we can repeat this process with two previously unmeasured footballs.
We might need as many as four measurements to discover the
outlierBall, worst case.
Maybe we can do better than this.
We could measure four football’s in each pan, then discard the lighter group of four.
The heavier group of four must contain the
outlierBall. We take this group and divide it in half.
Now compare two football’s against two football’s, discard the lighter pair and keep the heavier.
Now we can compare these last two against each other, as one of them must be the
So, we have performed three weighings, this is the best case and the worst case using this method.
But maybe we can do better yet. Let start by placing three football’s in each pan, setting two aside.
If the scale balances, then we know that the
outlierBall is in the group of two we had set aside.
It is a simple matter to compare those two, by weighing, to determine which is the
If the scale was unbalanced when we weighed three against three, then we know which group of three contains the
We Now take one football from this group and compare it with another football from this group.
If the scale balances, then the third football of that group must be the
If the scale is unbalanced, then we also know which is the
This method has a worst case of two measurements, an improvement over the previous method.
It turns out that if we started with nine balls, and put three in each pan and set three aside that the first measurement tells us which of the three groups contains the
outlierBall and on additional measurement allows us to determine the
Now if we notice the similarities between the case of eight football’s and nine football’s.
The first thing we did was divide the football’s into three groups, as similar in size as possible.
It turns out that if we do this for any quantity, at least two of these groups will have the same size.
We can start by comparing the weight of two of the same sized groups and based on that result we now know which group contains the
outlierBall AND that group is approximately one third the size.
We can repeat the process, eliminating about two thirds of the candidates at each step, until we have found the
We can construct a small table to make this clearer.
N, number of footballs; M, number of steps; L, football’s in the left pan; R, football’s in the right pan; S, football’s set aside.
N M L R S
1 0 0 0 0
2 1 1 1 0
3 1 1 1 1
4 2 1 1 2
5 2 2 2 1
6 2 2 2 2
7 2 2 2 3
8 2 3 3 2
9 2 3 3 3
10 3 3 3 4
11 3 4 4 3
12 3 4 4 4
We always place equal quantities in the left and right pans.
Then we recurse with which ever group holds the
But worst case analysis uses the largest group.
Here M, represents the total for that N; one for the starting row plus one for each additional row as we iterate/recurse using smaller groups.
Notice N is always less than or equal to 3^M.
Thus the logarithm of N, base three is always less than or equal to M. The ceiling rounds up to the next integer.
If we take the ceiling of the logarithm of N, base three; that is exactly M.
That is how I implemented my submission in Python 3.
Here is my code:
from math import log, ceil
def scaleOfTruth( ):
return ceil(log(8, 3))
# the minimum numbers of weighs to find the heavy one
def scaleOfTruthN( n ):
return ceil(log(n, 3))
print("scaleOfTruth( )=", scaleOfTruth( ) )
# 9 is 3^2, 27 is 3^3, 81 is 3^4, 243 is 3^5
for x in 8, 9, 10, 26, 27, 28, 80, 81, 82, 242, 243, 244:
print("scaleOfTruthN(", x, ")=", scaleOfTruthN( x ))
And the corresponding output:
scaleOfTruth( )= 2
scaleOfTruthN( 8 )= 2
scaleOfTruthN( 9 )= 2
scaleOfTruthN( 10 )= 3
scaleOfTruthN( 26 )= 3
scaleOfTruthN( 27 )= 3
scaleOfTruthN( 28 )= 4
scaleOfTruthN( 80 )= 4
scaleOfTruthN( 81 )= 4
scaleOfTruthN( 82 )= 5
scaleOfTruthN( 242 )= 5
scaleOfTruthN( 243 )= 5
scaleOfTruthN( 244 )= 6
Here is the link: