I love numbers. Ever since my grandmother’s brother showed me how to do long division when I was about five years old, I have been fascinated by numbers. So let me start by talking about what they are. It is really very simple, they just go like 1, 2, 3, 4, 5, 6, … etc. So that is the first problem. How do you define them?
It goes something like this. We all know what the number 1 means. Then assuming that you know what the number n means then the next number is defined as n + 1. That is all there is to it. So if you can show that something is true for the number 1, and if you can show that if it is true for the umber n, then it is also true for the umber n + 1 then you have proved it is true for all numbers.
This is called “proof by induction”. So let us look at a real-life problem that can be solved by induction. It is called the “Billiard Ball Problem”. It goes like this:
I am given (3n-3)/2 billiard balls and a balance. I am told that all the billiard balls are identical except exactly one is slightly lighter or heavier than the others. All the others weigh exactly the same as each others. I will refer to these balls as standard balls and the one that is different weight as the different ball. I am also given a standard balance which I am allowed to use n times. How do I find it which one it is and whether it is lighter or heavier?
The point is that each time I use the balance, I gain information about the balls on the balance and those not on the balance. Suppose I put three balls on each side of the balance. Then either it balances; in which case I know it is not one of the six balls on the balance, which must all be standard weight balls. In this case it must be one of the balls not on the balance. Or it doesn’t balance; in which case I know that the ball I am looking for is one of the six on the balance. But I also know a bit more; I know that if it is on the heavy side of the balance then it must be heavy, or if it is on the light side then it must be light. I also know that the balls not on the balance are standard weight balls.
I will need to talk about these balls. So if I put an equal number of balls on the balance and it does not balance then I will refer to the balls on the heavy side as unlight balls and the balls on the light side as unheavy balls. Balls that are either unheavy or unlike will be referred to as partly determined balls. If two balls are each unheavy or unlight, I will refer to them as the same type.
So let me start with a simpler problem.
Problem a:
I am given 3n partly determined billiard balls and a balance. I know that only one of the balls is different and the rest are standard balls. By using the balance exactly n times, how to I find the different ball?
Solution:
Firstly I have to show it is true when n = 1. That is I have 3 partly determined balls and I have to find it by using the balance just once. Note that with three partly determined balls there must be at least two both unheavy or at least two both unlight. I take two balls of the same type and put one on each side of the balance. Either they balance, in which case I know that the different ball that I am looking for is the third ball and if it is unlight then it must be heavy. If it is unheavy then it must be light. Therefore I can find it in the prescribed number of uses of the balance for the case n=1.
Now suppose I have 3n partly determined balls. Divide the balls into three groups of 3n-1 balls in such a way that there are an equal number of the same type in each of the first two groups. I can always do this because if I combine the first two groups then I have an even number of partly determined balls. Therefore there must be an even number of each or an odd number of each. If there is an odd number of each the swap an unheavy ball with an unlight ball from the third group or, if the third group is all unheavy balls then swap an unlight ball with an unheavy ball from the third group. In this case we end up with an even number of unlight balls and an even number of unheavy balls making up the combined first two groups. Suppose there are 2x unheavy balls and 2y unlight balls. Then I take x unheavy and y unlight balls in each of the first two groups. Note that x + y is 3n-1.
Place each of the first two groups on each side of the balance. There are two possibilities. Firstly it could balance. In this case I know that the different ball is in the third group of 3n-1 balls and by our induction hypothesis I have assumed that I can find it by using the balance n-1 times.
Secondly it may not balance. In this case I know it is one of the unlight balls on the heavy side or one of the unheavy balls on the light side. So I have narrowed it down to x + y or 3n-1 balls and again by our induction hypothesis I can find it by using the balance n-1 times.
Now a second problem.
Problem b:
I am given (3n-1)/2 billiard balls which are identical in weight except for exactly one which is either heavier or lighter. I am also given an extra standard weight ball and a balance. I have to find the different ball and whether it is heavier or light with n uses of the balance.
Solution:
First I need to show it is true for n=1. In this case I have I billiard ball which is either lighter or heavier than standard balls, a balance and standard billiard ball. I need to find it (since there is only one I know which one it is) and whether it is heavier or lighter. I simply need to compare it with the standard ball.
Now suppose I have (3n-1)/2 billiard balls which are identical in weight except for exactly one which is either heavier or lighter. I am also given an extra standard weight ball and a balance. I have to find the different ball and whether it is heavier or light with n uses of the balance.
I assume that I can do the n-1 case of (3n-1-1)/2 in n-1 uses of the balance so I leave aside (3n-1-1)/2 balls which I know I can find in n-1 uses of the balance if my first use leads to a balance.
I am left with (3n-1)/2 - (3n-1-1)/2 balls which equals 3n-1 balls. I add in the standard ball to give an even number, divide them into equal numbers and load them on the balance. If it balances I proceed as in the previous paragraph. If they do not balance then I now have 3n-1 partly determined balls and by “problem a” can finish finding the different ball in n-1 uses of the balance.
Now to the original problem.
Problem c:
I am given (3n-3)/2 billiard balls which are identical in weight except for exactly one which is either lighter or heavier. I am also given a balance. I need to find the different ball and whether it is lighter or heavier by using the balance n times.
Solution:
First I need to show it is true for n=1. In this case I have no balls and cannot use the balance. So let us go to case n = 2. In this case I have three balls and can use the balance twice. I start by putting one ball on each side of the balance. There are two possibilities. It may balance. In this case I simply have the case n=1 for “problem b” above. If it does not balance then I have the case n=1 for “problem a” I have an unheavy and an unlight ball. I also have a standard ball (that is the ball I left off). I simply weigh the standard ball against either of the partly determined balls and proceed as in 1a.
Now suppose I have (3n-3)/2 billiard balls and a balance. I can leave off (3n-1-1)/2 balls since I am assuming I can find it amongst them in n-1 uses of the balance if the first use balances (Problem b). I am left with (3n-3)/2 -(3n-1-1)/2 = 3n-1–1 balls. I divide them into two equal groups and place them on the balance. If they balance I proceed as in the previous sentence. If they do not balance I add in a standard ball calling it an unlight or unheavy (it doesn’t matter since it is both) and proceed as in “problem a”.
So I have demonstrated a proof of the general solution. So what does this mean? Let us construct a table:
| number of uses of the balance | number of balls | |
| 1 | 0 | |
| 2 | 3 | |
| 3 | 12 | |
| 4 | 39 | |
| 5 | 120 | |
| 6 | 363 | |
| 7 | 1,092 | |
| 8 | 3,279 | |
| 9 | 9,840 | |
| 10 | 29,523 | |
| 11 | 88,572 | |
| 12 | 265,719 | |
| 13 | 797,160 | |
| 14 | 2,391,483 | |
| 15 | 7,174,452 | |
| 16 | 21,523,359 | |
| 17 | 64,570,080 | |
| 18 | 193,710,243 | |
| 19 | 581,130,732 | |
| 20 | 1,743,392,199 |
As far as I know this problem has only been proven up to n=4 (ie 39 balls) before.