In the comments on my previous post there are some nice suggested algorithms for reading a stack of double-sided sheets of paper. The key seems to be that you need to keep track of a distinguished edge of the stack. When the distinguished edge is on the left, you move the top sheet to the back and flip the whole stack over; when the distinguished edge is on the right, you just flip the whole stack over again. Previously, I had always just flipped the top sheet over and then flipped it over again when I moved it to the back, always keeping the rest of the stack in the same orientation; but it seems clear that this is inferior to the method where all the sheets always stay in the same orientation relative to each other, and the whole stack flips over every time. The question, then, is how to keep track of the orientation: suggestions include a post-it note, dog-earing one corner of a page, and marking one side of the pages with a marker.
So here is a challenge for you. Can you come up with a good algorithm to read a stack of triple-sided sheets of paper? You may not be familiar with triple-sided sheets of paper, so here’s how they work: they stack nicely, just like regular sheets of paper, but you have to flip one over three times before you get back to the original side. In particular, there are two different operations you can do: call them flip (say, left-right) and anti-flip (right-left). On two-sided paper, flip and anti-flip are the same. On three-sided sheets, two flips are the same as an anti-flip, and two anti-flips are the same as a flip. Of course, three flips, or three anti-flips, are both the same as doing nothing. In other words, the operations of doing nothing, flip, and anti-flip form a group (namely, the group ).
If a sheet of paper is denoted by a variable , we will use to denote the flipped version of , and to denote the anti-flipped version. So and , and so on.
Given a stack of three-sided sheets of paper , where is on top and is on the bottom, there are a number of operations you can do:
- Move the top sheet to the bottom: .
- Move the bottom sheet to the top.
- Perform a flip or anti-flip on the top sheet: , or similarly for anti-flip.
- Perform a flip or anti-flip on the entire stack. This reverses the order of the sheets, and flips or anti-flips them, respectively: , and similarly for anti-flip.
Of course, you can also do any sequence of such operations.
The goal is to read every side of every sheet: that is, to come up with a sequence of the above operations such that all sides show up on top of the stack. Some desirable criteria for a solution include:
- The sequence of operations is particularly easy to remember
- Every side of every sheet shows up on top exactly once
- The sides show up in order (, , , , and so on)
It may not be possible to achieve all of the above at once! In the case of the algorithm for reading two-sided sheets of paper, items (2) and (3) above were taken as given requirements, and the name of the game was to solve (1): in particular, the solutions all exploited the phyiscal nature of the paper in order to keep track of one’s place in an alternating sequence of operations, which would otherwise be somewhat difficult to keep track of. For three-sided sheets, I am interested in exploring other possibilities as well—for example, perhaps there is a single operation or sequence of operations that can be done every time, such that all the pages show up, though not in order.
Also, perhaps the double-ended nature of a stack is particularly well-suited to reading double-sided paper. Can you come up with a coherent notion of a triple-ended stack which makes it easy to read triple-sided paper?
Also also, are there any reasonable physical models of triple-sided paper? Perhaps something with flexagons?