# 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.

-
also see mathoverflow.net/questions/13320, but answers might be too hard for beginning students –  sdcvvc Jan 15 '12 at 19:54
Shouldn't a big-list question be community wiki? –  j.p. Jan 16 '12 at 14:27
@jug: yes, especially one that asks for "brainstorming" and surely cannot admit an accepted answer. –  Willie Wong Jan 16 '12 at 15:07

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:

-
A nice presentation of this result can be found in this talk by Dana Ernst: oz.plymouth.edu/~dcernst/Talks/DeckJS/GordonTalk/… –  Andres Caicedo Jan 15 '12 at 21:00

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$).

-
American Scientist had a short article on this: americanscientist.org/issues/num2/group-theory-in-the-bedroom/1 –  Andres Caicedo Jan 15 '12 at 21:02
@Andres: Interesting; my memory is that I encountered this particular set-up before pillow-tops were common, and I have it mentally filed under "Martin Gardner's columns", but I could have seen it elsewhere... I'll have to check the CD-ROM of Gardner's columns I have. –  Arturo Magidin Jan 15 '12 at 21:10
If you find something, please let me know (I am compiling a list of resources for a course I'm teaching this term). –  Andres Caicedo Jan 15 '12 at 21:24
@Andres: Looks like I may have have it mentally misfiled. I used the search option on the "Martin Gardner's Mathematical Games" CD-ROM from the MAA, and failed to found it when I searched for "mattress" (only one hit, which was unrelated). Searching for "Group Theory" produced more hits, but none of them with this example. I know I had not read the American Scientist article, but I also know I picked up the example somewhere... –  Arturo Magidin Jan 15 '12 at 23:37
@Arturo: Brian Hayes' article was re-printed in his book of the same title (perhaps you flipped through that?), which was reviewed in the 2009 Feb issue of the Notices, so you may also have seen it there. But of course I cannot help with where you may have first seen the set-up. It is of course no impossible that multiple individuals have slept on this particular conundrum over the years. –  Willie Wong Jan 16 '12 at 15:11

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.

-
I'm not sure whether this example qualifies as "elementary," although of course High School students understand it. Anyway, this is an example of a permutation puzzle. Others are Rubik's cube, Skewb, etc. A good reference with many additional suggestions is "Adventures in group theory" by D. Joyner. –  Andres Caicedo Jan 15 '12 at 19:45

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.

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.

-
+1: For Fermat's Little Theorem (among others) –  j.p. Jan 16 '12 at 14:50
+1 Fermat's little theorem, the necklace problem, and the 2 square theorem are just the kind of thing I was looking for. (Although my friend's students do not know any linear algebra, so the proof of the 2 square theorem would have to be substantially altered to be used...) –  Ben Blum-Smith Jan 16 '12 at 16:33

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?

-
Don't quite get this, can you explain the idea in more detail? –  Ben Blum-Smith Jan 16 '12 at 15:30
@Ben Suppose the rectangular envelop (two different sides with a stamp in one corner) is positioned so that its axes are in the vertical and horizontal direction. One can now allow "moves" which are rotations or reflections (which have the effect or flipping the envelop over). One would like to have the envelop face up with the stamp in the upper right hand corner. A sensor tells one where the stamp currently is. One wants the "machine" to "efficiently" move the stamp to the proper position for canceling the stamp and/or for sorting. –  Joseph Malkevitch Jan 16 '12 at 16:47