Fav Problem Tweeted Dec 30 2018 by James Tanton @jamestanton (edited for clarity):
10 students sit in a circle. Is it possible for one student to move 1 place clockwise, one student 2 places clockwise, one student 3 places clockwise, and so on, all the way up to tenth student moving 10 places clockwise (back to his/her own seat) and ALSO end up one student per seat? 11 students?
Photo is of Chippeaw Falls kids, without permission.
I recognized that this was similar to
Langford's problem,
so I was determined to explore it.
Jan 8 2019 @MODUALITY JoHN MiLLeR
What If I said it was possible only with odd numbers of students & seats (≥3), and that there were 3,441 different ways of doing this with 11 students?
Jan 8 2019 @MODUALITY JoHN MiLLeR
Are Tanton's Chairs like Langford Pairs? Kinda.. A variation of the Langford algorithm counted solutions given the number of students/seats from 1..15. Sequence is:
0, 0, 1, 0, 3, 0, 19, 0, 225, 0, 3441, 0, 79259, 0, 2424195...
Then I made an effort to check my program and output for correctness. I also began to explore the solutions, and found out how far the program would go before hitting a wall.
Computing n=19 took ~4 days of computer time, so I haven't tried n=21!
When are solutions Feasible?
@HgChuck Chuck Carroll replied to my tweet of a hand-drawn solution for SEVEN seats/students:
The first diagram suggests a general solution for (all) odd numbers.
Hand Drawn Solution, tweeted --jm
Chuck then continued:
Not possible for even numbers: number chairs in circle 1..n. Sum of numbers is the nth triangular number, T(n). T(n) ≡ n/2 mod n for even n. Movement described adds another T(n) mod n to total, but this ≡ 0 mod n.
[Can we clarify Chuck's tweet-length proof?]
Enumeration
To solve this, you must match up unique future chairs for the students with the constraint of also moving a unique number of chair units i.e., Each student is destined to move a unique number of chairs clockwise, and claim an emptied seat.
Tanton's present-and-future chairs are like Langford's pairs of colored blocks. So I hacked my standard algorithm for Langford's Problem and counted solutions for 1..15 students/chairs. The Solution sequence seems to be: 1, 0, 1, 0, 3, 0, 19, 0, 225, 0, 3441, 0, 79259, 0, 2424195, ... i.e. The problem given above with 11 chairs has 3,441 solutions! Since even numbers of seats don't work out, there are 0's in the sequence. The problem with One student and one seat is the trivial, or degenerate case!
My program output the solution vectors into a file. The file of solutions for 15 measured 177 MB, so I didn't write the solutions for 17 or 19 to disk, I just counted.
Table of Number of Solutions for Tanton's Chairs
It would be nice to see others confirm these results independently.
This turns out to be sequence A003111 on [OEIS], Number of complete mappings of the cyclic group Z_{2n+1}. Thanks to Ian Duff, UK, for pointing this out!
Visualization
How best to visualize a solution? I tried different things, as have others.
The chair a student leaves should be clearly connected to the chair they take.
There may be a better representation of this using circular arcs. Fee free to play.
I decided to explore straight line arcs, and somehow show the clockwise aspect.
Here are sample solutions for 9 students & chairs… There are 225 of these! The Lone dot is the student that goes all the way around and back to his/her chair.
These graphs don't show the clockwise direction at all. You have to infer it using the clockwise differences. But it is interesting to see them as they are here, before I came up with a way to communicate the direction each student goes.
The one above has a 3-cycle, a 5-cycle, and a loop. (3+5+1=9).
This one (above) also has a 3-cycle, a 5 cycle, and a loop..
This one has a 2-cycle, a 6-cycle, and a loop..
This one has one 8-cycle, and a loop.
Two solutions for 15
This one has two 4-cycles, three 2-cycles, and 1 loop. (8+6+1=15)
This one has a 3-cycle, and a 11-cycle, and 1 loop. (3+11+1=15)
See section below on Cliques/Cycles for a breakdown for all solutions of N from 1 to 15.
An improved visualization... 11 chairs
In these 4 examples (with 11 chairs), green nodes are seats where students start, red nodes are seats where they go to. Each Red-Green pair represents a start and future chair. A line that looks like it's going counter-clockwise is just taking a shortcut.
Exercise: Describe the above!
Exercise: Describe the above!
The above graph is labeled with the clockwise distances.
There are 3,441 solutions similar to these… As in previous tweet, the Lone dot is the student who runs all the way around… moving clockwise 11 chairs.
Slightly improved graphic
Two sample solutions for n=11. Again, Green denotes a Start chair; Reds are Stop chairs.
This one consists of 5 pairs of students swapping chairs!
Can you count the two non-trivial cycles?
19 chairs!?
Here is one of over 4 billion solutions for 19 students and chairs.
Can you describe it?
Cliques, or cycles
I wondered whether the chair swapping would be one long chain - student takes a chair, the student who was in that chair takes different chair, and so on. (plus the one n→n looper). BUT! I noticed 'cliques' in some of the solution sequences.
(A
clique
is a distinct subset of chairs involved in the swapping.)
So, I wrote a perl script to read the saved output files and count the number of such cycles for various solutions.
Remember, we always have one 1-cycle (or loop) for nth student, by definition. That one student loops back to his/her original seat.
HOW TO READ THE NUMBERS BELOW. The first number on each line is the tally of the particular pattern on the line. The second number on the line is always '1' because that is the single loop. The remaining numbers give the number of cycles of increasing sizes. The number of cycles of given length times the length of the cycle = n.
EXAMPLE: The first line of 7 (below) says there are 14 solutions that have a single cycle of 6, plus the loop.
ANOTHER EXAMPLE. Under 15, the line:
53808 1 1 1 1 1 . . . . . . . . . .
means that there are 53,808 solutions that have a 2-cycle, a 3-cycle, a 4-cycle, a 5-cycle, and the loop — ie 2+3+4+5+1 = 15.
The most common pattern for 15 is a cycle of length 14 plus a loop.
Then next most common solutions for 15 are either a 12-cycle with a chair swap, or an 11-cycle with a 3-cycle (with loopers on each of course). It would be fun to represent all this info graphically.
EXERCISE. Under 15 above, the line 631 1 7... means there are 631 different solutions consisting of 7 pairs of students swapping seats, plus the looper.
In fact, you can see that each n has solutions based on (n-1)/2 pairs of students swapping chairs. (See the last line of tallies for each n.) Explain why this is the case.
End Notes
Origin of problem: I don't know where James got this problem. He may have just made it up years ago. He delights in tormenting his followers with fiendishly difficult questions like this. :^) Maybe something inspired the question. Hopefully, James will be able to track this back. For now, shall we say Origin uncertain?
The number of solutions turns out to be sequence A003111 on
[OEIS],
Number of complete mappings of the cyclic group Z_{2n+1}. Thanks to Ian Duff, UK, for pointing this out!
Note on Algorithm:
Without loss of generality, the first student doesn't need to try all n chairs, that would just multiply the number of solutions by n.
That is, the program can explore solutions assuming that the student who goes n chairs clockwise starts in chair 1.. and when the algorithm wants to shift that first student over, it terminates.
What number theory principle is at work here? (Full disclosure: I don't know!)
My solving program is written in C which outputs solution vectors to file.
The graphics were made with 'Processing' via Processing.org.
Consistency checker and cycle counter were done in Perl.
