Since this forum is densely populated with algebraists, I think I'll ask it here.

I'm teaching intermediate level algebra this semester and I'd like to entertain my students with some clever applications of group theory. So, I'm looking for problems satisfying the following 4 conditions

1) It should be stated in the language having nothing whatsoever to do with groups/rings/other algebraic notions.

2) It should have a slick easy to explain (but not necessarily easy to guess) solution using finite (preferrably non-abelian) groups.

3) It shouldn't have an obvious alternative elementary solution (non-obvious alternative elementary solutions are OK).

4) It should look "cute" to an average student (or, at least, to a person who is curious about mathematics but has no formal education).

An example I know that, in my opinion, satisfies all 4 conditions is the problem of tiling a given region with given polyomino (with the solution that the boundary word should be the identity element for the tiling to be possible and various examples when it is not but the trivial area considerations and standard colorings do not show it immediately) 

I'm making it community wiki but, of course, you are more than welcome to submit more than one problem per post.

Thanks in advance!

In the TV show "Futurama", there's an episode named "The Prisoner of Benda" in which two of the characters swap bodies using a machine with a fundamental flaw: no two people can use it to swap bodies twice. This means they can't simply use the machine again to swap back.

They spend the rest of the episode trying to return to their original bodies. Eventually, a scientist (who also happens to be a Harlem globetrotter) figures out how to help them using group theory.

With a little reflection, one can see that this problem can be recast into one about the symmetric group.
