## Reading double- and triple-sided paper

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 $\mathbb{Z}_3$).

If a sheet of paper is denoted by a variable $p$, we will use $p^+$ to denote the flipped version of $p$, and $p^-$ to denote the anti-flipped version. So $p^{++} = p^-$ and $p^{+++} = p$, and so on.

Given a stack of three-sided sheets of paper $p_1 p_2 \dots p_n$, where $p_1$ is on top and $p_n$ is on the bottom, there are a number of operations you can do:

• Move the top sheet to the bottom: $p_1 p_2 \dots p_n \mapsto p_2 \dots p_n p_1$.
• Move the bottom sheet to the top.
• Perform a flip or anti-flip on the top sheet: $p_1 p_2 \dots p_n \mapsto p_1^+ p_2 \dots p_n$, 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: $p_1 p_2 \dots p_n \mapsto p_n^+ \dots p_2^+ p_1^+$, 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 $3n$ sides show up on top of the stack. Some desirable criteria for a solution include:

1. The sequence of operations is particularly easy to remember
2. Every side of every sheet shows up on top exactly once
3. The sides show up in order ($p_1$, $p_1^+$, $p_1^-$, $p_2$, 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?

## About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in Uncategorized and tagged , , , , , , . Bookmark the permalink.

### 5 Responses to Reading double- and triple-sided paper

1. blaisepascal2014 says:

The first method which comes to mind is:
Make a mark on the top sheet. (side $p_1$)
Read it, and move it to the back, repeat until the marked sheet is on top again.
Flip the stack, and make a mark on the top sheet (which would be side $p_n^+$).
Read it, and move it to the back, repeat until the marked sheet is on top again.
Flip the stack, and make a mark on the top sheet (which would be side $p_1^-$).
Read it, and move it to the back, repeat until the marked sheet is on top again.

At which point, you have read $p_1, p_2, \ldots, p_n, p_n^+, p_{n-1}^+, \ldots, p_1^-, p_2^-, \ldots, p_n^-$. Not exactly the order you want, but it gets the job done.

You could also:
A. Mark the page.
B. Read it. Flip it
C. If it is not now marked, do B again, otherwise move the page to the back
D. If after moving the page to the back, the new top page is marked, stop.

That would read them in order, at the cost of a bunch more marking.

• blaisepascal2014 says:

I need to read the directions… “Note you have to literally write ‘latex’ after the first dollar sign!”. How do I edit?

• Brent says:

No worries. I don’t think there’s any way for you to edit your own comments. (Perhaps you can if you are logged in to WordPress?) Anyway, I fixed them for you.

• Brent says:

Incidentally, your first algorithm just made me realize that although performing three flips on a single sheet is the identity, it is not the identity on a stack! In fact, flipping a stack three times is a quick way to reverse the order of the sheets. =D

(I think this means that even if there are reasonable physical models of triple-sided sheets, there are NOT reasonable physical models of stacks of such, at least not as I have defined them!)

Comments are closed.