Great Big House in New Orleans: The Special Case
A few months ago, I published a post called Great Big House in New Orleans, in which I discuss a game I used to play in my elementary school music class. In that post, I explained how I designed an efficient algorithm that allowed me to quickly find the winning position of the game given how many people are playing. I published the actual algorithm itself in a second post. Basically, in the game, all students in the class sat in a circle and passed a stuffed pumpkin around while singing a song. The rules of the game were such that every eighth student gets out (i.e. exits the circle), and the last student to remain in the circle wins.
Essentially, I discovered that if you have add one person to the group of people playing the game, the winning position shifts to the right by eight. For example, in an elementary school class of 21 students sitting in a circle, the student sitting at position 10 will win. If I add one student to the class, the winning position increases by eight. Thus, for a class of 22 students, position 18 will win. I call this the "just add eight" algorithm. The beauty of this method is that it allows me to calculate the winning position of class sizes in the millions in less than a second, whereas in my original implementation of simulating games using lists, it starts to lag significantly when calculating the winning positions for class sizes in the tens of thousands.
There is, however, an important exception to the "just add eight" rule. If you have a class size whose winning position is the first person in the circle (i.e. position 1), then if you add one student to the class, the next winning position will be 8, not 9. The "just add eight" rule resumes thereafter; the next winning position after 8 would be 16, then 24, and so on. I discuss why this is the case in my original post under the section titled "Special case: if the starting point is (c0, 1)". When I wrote the blog post, I originally found only 4 cases when the special case held: for all class sizes below 1000, position 1 wins only for sizes of 3, 13, 15, and 26. I wondered whether there were more above 1000. It turns out, there are indeed more. A lot more.
I ran my improved algorithm up to class sizes up to 1 billion, and when the game is played with the following class sizes, position 1 will win.
Essentially, I discovered that if you have add one person to the group of people playing the game, the winning position shifts to the right by eight. For example, in an elementary school class of 21 students sitting in a circle, the student sitting at position 10 will win. If I add one student to the class, the winning position increases by eight. Thus, for a class of 22 students, position 18 will win. I call this the "just add eight" algorithm. The beauty of this method is that it allows me to calculate the winning position of class sizes in the millions in less than a second, whereas in my original implementation of simulating games using lists, it starts to lag significantly when calculating the winning positions for class sizes in the tens of thousands.
There is, however, an important exception to the "just add eight" rule. If you have a class size whose winning position is the first person in the circle (i.e. position 1), then if you add one student to the class, the next winning position will be 8, not 9. The "just add eight" rule resumes thereafter; the next winning position after 8 would be 16, then 24, and so on. I discuss why this is the case in my original post under the section titled "Special case: if the starting point is (c0, 1)". When I wrote the blog post, I originally found only 4 cases when the special case held: for all class sizes below 1000, position 1 wins only for sizes of 3, 13, 15, and 26. I wondered whether there were more above 1000. It turns out, there are indeed more. A lot more.
I ran my improved algorithm up to class sizes up to 1 billion, and when the game is played with the following class sizes, position 1 will win.
- 3
- 13
- 15
- 26
- 1276
- 1905
- 2,844
- 8,278
- 12,357
- 16,140
- 21,081
- 1,157,873
- 3,369,742
- 21,851,636
- 48,689,537
- 83,062,201
- 918,879,332