Round Table: Students' Notes
Introduction
These notes are designed to provide you with hints to help you while you work towards solving this problem and also to help you see a much larger picture of both the problem and of mathematics itself. The activity is available online at:
The notes below are split into four phases:
- Understanding and solving specific problems
- Generalising
- Proving
- Extending
The four phases are the same as those used by mathematicians when they are working on research problems. Of course, if you only want to go as far as solving the Round Table problem for a specific number of seats, you won’t need to go through all of these phases. However, the problem is set up for you to find a conjecture about the winning seat M given N seats around the table
Below we have provided a number of hints for you to use if you need help. Try to do as much of the problem as you can yourself, and only use the hints if you get stuck.
Phase 1: Understanding and solving specific problems
At first glance this is a really very simple problem. All you have to do is to put some number of seats around a round table; alternately remove seats according to a straight forward process; and decide which seat number is left. So if you are careful you can do this for any number of seats N and come up with the last seat left M. It’s just a matter of being careful to use the process correctly and you’ll get the right answer. What we are hoping for here though is that you will gradually be able to see patterns. Are there sets of values of N for which you can predict M? Or better still, given any value of N can you find the value of M? It is certainly an achievement to be able to go this far. However, the next step is to be able to justify the patterns that you think that you can see. We hope that you will try to make progress with this. Finally, and you can do this without necessarily doing everything else above, you might think about extending the problem to other similar problems.
This Round Table situation then, gives you a chance to analyse a problem and produce some generalisations. To do this you will need to experiment until the game is understood. This provides an opportunity for systematic experimentation and the application of logic.
Hint 1
If you are not sure how to solve the problem, the first thing you should try is experimenting with some different numbers of people at the table.
Hint 2
Keep an organised list of the different numbers of people at the table and winning seat number for each.
Hint 3
Look for patterns in the list of winning positions.
Hint 4
Are there seat numbers that can never win? Why not?
Hint 5
No even numbered seats can win, because all the even numbered seats are excluded immediately. What different numbers of people at the table give the same winning seat number?
Hint 6
What numbers of people could be at the table for the person at position 1 to win?
Hint 7
Person 1 wins if there are 2 (you can’t actually do this in the game), 4, 8, 16… people at the table. What do you notice about these numbers?
Phase 2: Generalising
Hint 8
Person 1 wins if the number of people at the table is a power of 2. This means a number that you can get to by multiplying by 2 (2x2=4; 2x2x2=8; 2x2x2x2=16). So, how do you find the winning seat number if the total number of seats is not a power of 2?
Hint 9
Look at the winning positions for total numbers of seats one more than a power of 2, and then two more than a power of two. How can you find the winning seat position for numbers of seats that are not a power of 2?
Hint 10
From the nearest power of 2 count up in odd numbers to find the winning seat. Can you describe a rule for the winning seat number given any number of seats?
Hint 11
If the total number of seats is a power of 2 then the winning seat is seat 1. If the total number of seats is not a power of 2 then the winning seat can be found by subtracting the closest power of two from the total number of seats and adding twice the result onto 1. For example, if there are 13 seats, the closest power of 2 is 8, so you take 8 away from 13 to give 5, then add twice 5 onto 1 to give 11 – the winning seat is seat 11.
Can you describe a rule to find the number of seats if you know the winning seat number?
Hint 12
If the winning seat is seat 1 then the total number of seats must have been a power of 2, but there is no way to tell which one, unless you have more information. If the winning seat is more than 1, then you can find out how many more than a power of 2 the total number of seats is by taking 1 off the winning seat number and halving the result. For example, if the winning seat is seat 9, then the total number of seats can be found by taking 1 away from 9 and halving the result to get 4 – so the total number of seats is 4 more than a power of 2.
The hints above should give you enough information to complete the Round Table problem online, but you may be interested in exploring the problem further. For the following hints we have used N to represent the number of seats at the table, and M to represent the winning seat number. Some of these hints repeat ideas included above, but this time we'd like you to try using algebra to describe your rules.
Hint 13
Can you make some conjectures about N and M?
Hint 14
What can you say about the values of M?
Hint 15
What is special about the case where N is a power of 2?
Hint 16
What is special about the cases where M and N are the same?
Hint 17
What can be said about the general value of N? How can N be written to make this simpler to state?
Hint 18
Given M how can you write N?
Phase 3: Proving
As the result of the last section you might come up with these conjectures.
Conjecture 1: M can never be even.
Conjecture 2a: If N is a power of 2, then M is 1.
Conjecture 2b: If M is 1, then N is a power of 2.
Conjecture 3: M = N if N is one less than a power of 2.
Conjecture 4a: If N = 2n + i, for 0 ≤ i < 2n, then M = 2i + 1.
Conjecture 4b: Let 2n be the highest power of 2 less than N. Then M = 2(N – 2n) + 1
Hint 19
Do you need a hint for Conjecture 1? What happens the first time round?
Hint 20
For N = 16 can you see how you only need to know the answer for N = 8 or rather N = 4 or rather N = 2? What about N = 64?
Hint 21
We suggest that you leave Conjecture 2’ until after Conjecture 4 has been established.
Hint 22
We suggest the same thing with Conjecture 3, although working on this and Conjecture 2 may give you an idea of how you might proceed in the general case.
Hint 23
You may find Conjecture 4 is easier if you break it up into two cases: N is even and N is odd.
Hint 24
For N even look again at the situation in Conjecture 2. Can you change the N even case into a smaller case? N/2 perhaps? Try N = 6, 10 and 34 as special cases from which you might get the general case.
Hint 25
Is there a ‘smaller case’ argument for N odd? Try N = 7, 11 and 35.
Hint 26
Do you need to know anything else now in order to get the remaining conjectures proved?
Hint 27
Are there any conjectures that we have missed?
Phase 4: Extending
The question now is can we take the problem any further. What Round Table-like problems can we build around this one? Extending problems is a fundamental way of working for mathematicians. Let us suggest some related problems.
- Suppose that instead of keeping one and deleting the next we keep two and delete the next. Given N what is M then?
- Suppose that instead of keeping one and deleting the next we keep three and delete the next. Given N what is M then?
- Suppose that instead of keeping one and deleting the next we keep r and delete the next. Given N what is M then?
- Suppose that instead of keeping one and deleting the next we keep one and delete the next two. Given N what is M then?
- Suppose that instead of keeping one and deleting the next we keep one and delete the next three. Given N what is M then?
- Suppose that instead of keeping one and deleting the next we keep one and delete the next s. Given N what is M then?
- Suppose that instead of keeping one and deleting the next we keep r and delete the next s. Given N what is M then?
