Elementary problems with group theoretic solutions

I am helping a friend develop a course in abstract algebra that is designed for high school students who have no knowledge of abstract algebra or any real exposure to formally rigorous mathematics. To motivate the study, we are seeking problems whose statement will be immediately accessible to the students, but whose solution is aided by basic tools of group theory. So my question is this:

What are some interesting problems, whose statements are comprehensible to an average 9th or 10th grade high school student, but whose solutions are greatly aided by group theory?

Here is the best type of example I have thought of so far for what we are looking for:

• How many distinct ways are there to 2-color the 8 vertices of a cube, with colorings only considered distinct up to rotation?

The problem is very tricky by direct enumeration (how do you know when you're done?) but submits to a double-counting method based on the orbit-stabilizer theorem.

This is perfect because the question is natural and kids could get started by direct enumeration; but the group theory really adds a lot of power. Also, the type of group theory needed is at the right level: Lagrange's theorem and its corollary the orbit-stabilizer theorem. These are significant pieces of theory but are realistic to get to in this setting. Problems solvable by computation in some specific group (e.g. can you get a line of people into an arbitrary order by switching them 2 at a time?) are also useful to us but will do less to motivate the theory. Meanwhile, problems involving heavier theory (e.g. Sylow theorems) will be hard to use because it is not realistic to plan on developing this theory in the (1-semester, and slow b/c for high school students) course.

Can you help me brainstorm questions of this kind? Thanks so much.

Update (1/16): These answers are helpful, and my friend may well use them. I am hoping for more though! Specifically, I am hoping for more problems that require (a small amount of) group theory and not just a calculation in some specific group, because the idea is to use the problems to motivate the theory. For example, the Futurama problem is adorable (and therefore great for HS students!), but seems to be pretty much a calculation in $S_n$. The mattress problem is a little more what I'm talking about here because the proffered solution involves concepts central to the theory like cyclic groups, and the theorem (grantedly a minor one but still a theorem) that cyclic groups have at most one element of order 2.

Ideally the solution to the problem involves invoking an important and not very hard theorem of group theory. Examples of the types of concepts and theorems I'd ideally like to see used:

• Subgroups, homomorphisms, normal subgroups, quotients

• Lagrange's theorem / the orbit-stabilizer theorem (this is the virtue of the cube-coloring enumeration problem)

• The first isomorphism theorem

• Basic facts about actions: the stabilizer is a subgroup; stabilizers of objects in the same orbit are conjugate; etc.

Any more ideas folks? Thanks again.

There is the "Futurama Theorem" (based on a television show by the same name) that might be interesting to them. Dr. Farnsworth created a machine that swaps the minds of two individuals (i.e. your mind would be in my body and my mind in your body). Unfortunately, the body builds up resistance after a swap, which prevents swapping the minds back directly (i.e. if you and I just switched minds, we could not switch back without one of us first spending time in someone else's body).

The question is, given a collection of jumbled up minds and bodies, how can you get them all back to normal?

Your students will quickly realize that extra "clean" bodies (individuals who haven't swapped minds with anyone) are needed, since a collection of just two people with swapped minds could never get back to normal. It turns out that, no matter the size of the collection or the permutation of minds, two extra "clean" bodies are sufficient to reverse the permutation.

Here's the proof that appeared in the show, which uses nothing other than basic facts about permutations:

You can also read about it at Wikipedia and CutTheKnot.

With non-pillow-top mattresses, it is recommended that they be rotated and flipped on a semi-regular basis. You can rotate them end-to-end (keeping the same part of the mattress facing "up" as before), or you can flip them so the bottom and top are exchanged, or any combination of these two.

Ideally, one wants to go through all four possible positions one after another, spending the same amount of time in each of them; but that requires you to remember which one you did last time. Is there a single combination of rotations and flips that you can make each time that will guarantee that you go through all possible combinations on a regular basis? What if the mattress is square, so that you also have a 90${}^{\circ}$ rotation, instead of only the end-to-end rotation?

(In group theory terms, is the group of symmetries of the mattress cyclic? No, because it has two distinct elements of order $2$).

There is also a family of puzzles that are related to Groups (specially permutations and transpositions). For example, proving that this puzzle is not solvable if 14 and 15 were swapped.

The postal service wants to be able to cancel the stamp that appears on a letter or a postcard. Describe how the rectangular shape can be transformed so that when looking down at the rectangle one can see the stamp in the upper right hand corner. How many "moves" might be necessary?

I am not sure if the following are entirely elementary, but I am pretty sure that a motivated and determined high school kid should be able to grasp the material that I am mentioning below:

The following material from Prof.Sury's homepage and Prof. Amritanshu Prasad's page are pretty interesting and elementary.

• On Sam Lloyd's bet.
• Polya's theory of enumeration in various avatars here, here and here.

And, of course, I cannot resist from mentioning the Fermat's Two Square theorem. See here for an elementary proof (not the proof by D Zagier!).

The various avatars themselves have interesting problems mentioned there. So, I only hope this is in spirit of your question and is of some help.

EDIT: I thought just linking to various pages over the web, is not useful as I'll be forcing people to visit them. So, I am describing them here.

On Sam Lloyd's bet: The 15 puzzle through the permutation Groups.

The first 'here' links to an exposition of Polya's theory of enumeration-about counting the number of orbits; weighted enumeration and other concepts therein. The second 'here' links to the proof of Fermat's Little theorem amon many other things. The 'third' here links to counting the number of necklaces, which is a primitive of version, of many counting problems, say counting the number of sudokus and so on.