Round Table: Proof
By looking at several cases we might come up with these conjectures:
Conjecture 1: M can never be even.
Conjecture 2: If N is a power of 2, then M is 1.
Conjecture 3: M = N if N is one less than a power of 2.
Conjecture 4: If N = 2n + i, for 0 ≤ i < 2n, then M = 2i + 1.
Conjecture 1 should be relatively easy to prove. Given the strategy that we have of keeping one and deleting the next, we have to delete all of the even numbers on the first time around the Round Table. The moral is “avoid an even numbered seat”.
Conjecture 2 isn’t so bad either. Suppose that we did start with 64. Then after the first time around when we have got rid of all of the even numbers we end up with 32 ‘active’ seat numbers. Suppose that we now relabel all of the seat numbers in order from 1 to 32. (So 3 has become 2, 5 has become 3 and so on.) On the second time around we lose all the new even numbers and end up with just 16 active seats. Relabel the seat numbers again to get the numbers 1 to 16. But at this stage we realise that M = 1 for N = 16. What’s more 1 is the only number that has not changed over all the relabelling that we have done. So for N = 64, M = 1.
It ought to be possible to work this into a proof for N = 2n for n ≥ 0. (To make this really watertight will need Mathematical Induction but a satisfactory proof can be offered along the lines we have above for N any power of 2.)
We’ll skip Conjecture 3 because that falls out in a similar way if we go round once and then take out the ‘1’ seat. In doing this we go from N = 2n – 1 to 2n-1 -1. This should give us the energy to take on Conjecture 4 and we can prove that in the same way.
First note that we have proved Conjecture 4 for i = 0. Now we break the values of N into two cases: where N is even and where N is odd. We do an example of each before we do the general cases.
Suppose N = 10. Then after the first round we have only 5 odd numbers left. But if N = 5 we know that M = 3. Since the third odd number in the first 10 is 5, then for N = 10, M = 5. Now 10 = 8 + 2 and 2 x 2 + 1 = 5. So the conjecture works for n = 10.
Case 1: Suppose that N is even. This means that if N = 2n + i, that i = 2k for some k. After the first round, we have lost all of the even numbers and we are down to 2n-1 + k odd numbers. Assuming that we have already done this case we know that M = ‘2k + 1’ or rather the (2k + 1)th odd number. But that number is actually 2(2k + 1) - 1 = 2(2k) + 1. So if N = 2n + i with i = 2k, then M = 2i + 1 as we had hoped.
Now consider N = 13. After the first round we have deleted all of the even numbers but we will delete the ‘1’ as well to get no two consecutive numbers. So we now have 3, 5, 7, 9, 11, 13 left. But this is equivalent to 1, 2, 3, 4, 5, 6. For N = 6, M = 5 and the fifth number of our remaining six odd numbers is 11. Now 13 = 8 + 5 and 2 x 5 + 1 = 11 as we had hoped.
Case 2: Suppose that N is odd. This means that if N = 2n + i, that i = 2k + 1 for some k. Now go round the table once to delete all of the even numbers and then delete ‘1’. We now have N = 2n-1 + k odd numbers left. If N = 2n-1 + k, then M = 2k +1. So what is the (2k +1)th odd number starting from 3 or the (2k + 2)th odd number starting from 1. This is just 2(2k + 2) -1 = 2(2k + 1) + 1. So if N = 2n + I, then M = 2i + 1.
To complete the mathematical Induction here we really need to do some starting cases but we already have that in the table we produced earlier. So that is no problem.
Incidentally 1: Conjecture 3 now follows by letting i = 2n-1 – 1.
Incidentally 2: It is now possible that M = 1 if and only if N is a power of 2. To see that first if N is a power of 2 we know that M = 1 by the proof of Conjecture 2. So let’s assume that M = 1. In general N = 2n + i. But then M = 2i + 1. But M = 1 here so i = 0 and N is a power of 2.
We mention this because mathematicians like to have ‘if and only if’ results. These give them characterisations, statements that tell them everything about a certain situation. They like these because it makes it easier for them to test something. In this case if you were looking for M = 1 you would only need to test N to see if it was a power of 2. There would be no need to go and do all the deleting of alternate seat numbers.
