## Tanton's ChairsFav ProblemTweeted Dec 30 2018 by James Tanton @jamestanton (edited for clarity):
I recognized that this was similar to Langford's problem, so I was determined to explore it.
Jan 8 2019 @MODUALITY JoHN MiLLeR
Jan 8 2019 @MODUALITY JoHN MiLLeR
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.
Chuck then continued:
[Can we clarify Chuck's tweet-length proof?] ## EnumerationTo solve this, you must match up uniquefuture chairsfor the students with the constraint of also moving a unique number of chair unitsi.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 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 SolutionsIt would be nice to see others confirm these results independently.
1 = 1 The trivial case 2 = 0 3 = 1 4 = 0 5 = 3 6 = 0 7 = 19 8 = 0 9 = 225 10 = 0 11 = 3441 == 3,441 12 = 0 13 = 79259 == 79,259 14 = 0 15 = 2424195 == 2,424,195 2 million 16 = 0 17 = 94471089 == 94,471,089 94 million 18 = 0 19 = 4613520889 == 4,613,520,889 4 billion (Jan 17, 2019, originally off by 1!) 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! ## VisualizationHow 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.
Here are two solutions for 15.
See section below on Cliques/Cycles for a breakdown for all solutions of N from 1 to 15. ## An improved visualization... 11 chairsIn these 4 examples (with 11 chairs), green nodes are seats where students start, red nodes are seats where they go to. Each Red-Greenpair represents a start and future chair. A line that looks like it's going counter-clockwise is just taking a shortcut.
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 (below) consists of 5 pairs of students swapping chairs!
Can you count the two non-trivial cycles in the one below?
## 19 chairs!?Here is one of over 4 billion solutions for 19 students and chairs. Can you describe it?
## Cliques, or cyclesI 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.
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. 7 -------------- 1 2 3 4 5 6 14 1 . . . . 1 2 1 . 2 . . . 3 1 3 . . . . 9 -------------------- 1 2 3 4 5 6 9 8 9 78 1 . . . . . . 1 0 18 1 . . 2 . . . . 0 48 1 . 1 . 1 . . . 0 42 1 1 . . . 1 . . 0 18 1 1 2 . . . . . 0 12 1 2 . 1 . . . . 0 9 1 4 . . . . . . 0 11 ----------------------- 1 2 3 4 5 6 9 8 9 10 838 1 . . . . . . . . 1 . 138 1 . . . 2 . . . . . . 380 1 . . 1 . 1 . . . . . 580 1 . 1 . . . 1 . . . . 40 1 . 2 1 . . . . . . . 750 1 1 . . . . . 1 . . . 150 1 1 . 2 . . . . . . . 240 1 1 1 . 1 . . . . . . 120 1 2 . . . 1 . . . . . 100 1 2 2 . . . . . . . . 80 1 3 . 1 . . . . . . . 25 1 5 . . . . . . . . . 13 ---------------------------- 1 2 3 4 5 6 9 8 9 ....... 14416 1 . . . . . . . . . . 1 0 3588 1 . . . . 2 . . . . . . 0 7080 1 . . . 1 . 1 . . . . . 0 7956 1 . . 1 . . . 1 . . . . 0 440 1 . . 3 . . . . . . . . 0 8872 1 . 1 . . . . . 1 . . . 0 2928 1 . 1 1 1 . . . . . . . 0 1600 1 . 2 . . 1 . . . . . . 0 116 1 . 4 . . . . . . . . . 0 13008 1 1 . . . . . . . 1 . . 0 1752 1 1 . . 2 . . . . . . . 0 3264 1 1 . 1 . 1 . . . . . . 0 4560 1 1 1 . . . 1 . . . . . 0 1392 1 1 2 1 . . . . . . . . 0 3234 1 2 . . . . . 1 . . . . 0 1140 1 2 . 2 . . . . . . . . 0 2208 1 2 1 . 1 . . . . . . . 0 896 1 3 . . . 1 . . . . . . 0 364 1 3 2 . . . . . . . . . 0 312 1 4 . 1 . . . . . . . . 0 133 1 6 . . . . . . . . . . 0 15 --------------------------------- 453024 1 . . . . . . . . . . . . 1 . 64544 1 . . . . . 2 . . . . . . . . 135744 1 . . . . 1 . 1 . . . . . . . 146576 1 . . . 1 . . . 1 . . . . . . 161384 1 . . 1 . . . . . 1 . . . . . 28864 1 . . 1 2 . . . . . . . . . . 34016 1 . . 2 . 1 . . . . . . . . . 202992 1 . 1 . . . . . . . 1 . . . . 83952 1 . 1 . 1 1 . . . . . . . . . 76944 1 . 1 1 . . 1 . . . . . . . . 42000 1 . 2 . . . . 1 . . . . . . . 9184 1 . 2 2 . . . . . . . . . . . 7408 1 . 3 . 1 . . . . . . . . . . 262072 1 1 . . . . . . . . . 1 . . . 49360 1 1 . . . 2 . . . . . . . . . 93680 1 1 . . 1 . 1 . . . . . . . . 95368 1 1 . 1 . . . 1 . . . . . . . 7468 1 1 . 3 . . . . . . . . . . . 124592 1 1 1 . . . . . 1 . . . . . . 53808 1 1 1 1 1 . . . . . . . . . . <----- 53,808 mentioned in above EXAMPLE 31616 1 1 2 . . 1 . . . . . . . . . 1644 1 1 4 . . . . . . . . . . . . 91708 1 2 . . . . . . . 1 . . . . . 18776 1 2 . . 2 . . . . . . . . . . 37328 1 2 . 1 . 1 . . . . . . . . . 45104 1 2 1 . . . 1 . . . . . . . . 11704 1 2 2 1 . . . . . . . . . . . 24112 1 3 . . . . . 1 . . . . . . . 6098 1 3 . 2 . . . . . . . . . . . 12784 1 3 1 . 1 . . . . . . . . . . 4716 1 4 . . . 1 . . . . . . . . . 2616 1 4 2 . . . . . . . . . . . . 2378 1 5 . 1 . . . . . . . . . . . 631 1 7 . . . . . . . . . . . . . (See Exercise below) 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 ## End NotesOrigin 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 sayOrigin uncertain? 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. Langford's Problem Home Page |