Cool problems to impress students with group theory [closed]

Question

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!

Answer 1

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.

Answer 2

Mattress Turning! Don't say it's not 'cute'!

The set of sensible orientations of your mattress on a bed (probably) has 4 elements. If your mattress is prone to sagging due to the weight of its users then you need to periodically turn it into another one of the 4 configurations. It'd be nice if there were a simple operation you could perform on the mattress once a month, say.

Now comes the group theory: the 4 element group of configurations is the Klein viergruppe, not a cyclic group. So you can't find one transformation that you can repeat to get all configurations. You need to have a more complex procedure where the transformation varies from month to month.

It gets harder, of course, if you have a cubical mattress. See Group Theory in the Bedroom for more information.

Answer 3

Here is a striking application of a particular finite non-abelian group.

Explain to your students the issue of check digits as an error-detecting device on credit cards, automobile identification numbers, etc. Two common errors in communicating strings of numbers is a single-digit error (...372... --> ...382...) or an adjacent transposition error (...32... ---> ...23...). We want to design a check digit protocol in such a way that these two common errors are both detected (though not necessarily corrected: an error sign may flash in practice and the person is just prompted to enter the numbers all over again). The simplest check digit protocol uses modular arithmetic, as follows.

If we have an alphabet of m symbols and we agree that our strings of symbols to be used all have n terms, say they are written as $a_1a_2...a_n,$ introduce a set of weights $w_1,...,w_n $ and a valid string is one where

$w_1a_1 + ... + w_na_n = 0 \mod m.$

In practice we take $ w_n = 1 $ or $-1 $ and the unique choice of $a_n $ that fits the congruence given all the other data is the check digit.

Theorem 1: All single digit errors are caught iff $ (w_i,m) = 1 $ for all i.

That means if a valid string -- one satisfying the above congruence -- has a single term changed then the result will not satisfy the congruence and thus the error is detected.

Theorem 2: All adjacent transposition errors are caught iff $(w_{i+1}-w_i,m) = 1 $ for all i. (Wrap around when i = n.)

For example, say m = 10 (using the symbols 0,1,2,...,9). If all single digit errors are caught then each $w_i $ has to be taken from {1,3,5,7}, but the difference of any two of these is even, so Theorem 2 won't apply.

The conclusion is that "no check digit protocol exists on Z/10 (for strings of length greater than 1) which detects all single digit errors and all adjacent transposition errors.

Maybe you think we are just not being clever enough in our check digit protocol mod 10. For example, instead of those scaling operations a |---> $w_i$a which are put together by addition, we could just define in some other way a set of permutations $s_i$ of Z/m and declare a string $a_1....a_n$ to be valid when

$s_1(a_1) + ... + s_n(a_n) = 0 $ mod m.

We can use this congruence to solve for $ a_n $ given everything else, so we can make check digits this way too.

Theorem 3. When m = 10, or more generally when m is even, there is an adjacent transposition error -- and in fact a transposition error in any two predetermined positions for some string -- that won't be caught.

The proof is a clever argument by contradiction, but I won't type up the details here.

Since in practice we'd like to use 10 digits (or 26 letters -- still even) for codes, Theorem 3 is annoying. The book community with their ISBN code got around this by using m = 11 with a special check digit of X (a few years ago they switched to m = 13). It is natural to ask: is there some check digit protocol on 10 symbols?

Answer: Yes, using the group $ D_5$ (non-abelian of order 10) in place of Z/10.

This was found by Verhoeff in 1969. It has hardly been adopted anywhere, due to inertia perhaps, even though the mechanism of it would in practice always be hidden in computer code so the user wouldn't really need to know such brain-busting group theory like $D_5$.

You can read about this by looking at

S. J. Winters, Error Detecting Schemes Using Dihedral Groups, The UMAP Journal 11 (1990), 299--308.

The only bad thing about this article by Winters is the funny use of the word scheme, e.g., the third section of the article is called (I am not making this up) "Dihedral Group Schemes". I recommend using the word "protocol" in place of "scheme" for this check digit business since it it more mathematically neutral.

By the way, Theorem 3 should not be construed as suggesting there is no method of using Z/10 to develop a check digit protocol which detects both of the two errors I'm discussing here. See, for example,

K. A. S. Abdel-Ghaffar, Detecting Substitutions and Transpositions of Characters, The Computer Journal 41 (1998) 270--277.

Section 3.4 is the part which applies to modulus 10. I have not read the paper in detail (since I'm personally not interested enough in it), but the end of the introduction is amusing. After describing what he will be able to do he says his method "is easier to understand compared to the construction based on dihedral groups". What the heck is so hard about dihedral groups? Sheesh.

Answer 4

An obvious choice is the enumeration of orbits of finite group actions, which show up everywhere in middle- and high-school competitions in disguise. The "cute" example here is coloring a cube or a regular polygon up to rotation. I have written a few blog posts on the subject and there are several examples given in the third post. One of my favorite applications here is Lucas' theorem, and once you bring that up you can casually mention the Sierpinski triangle as well.

Edit: And again I feel the need to tell you things most AoPSers already know, but another nice class of examples is provided by the application of linear algebra over $\mathbb{F}_2$ to problems in combinatorics, see e.g. this post by Tim Gowers or Jacob Steinhardt's excellent solution to USAMO 2008 #6.

Edit #2: Although it is possible to state all this in the simpler language of equivalence relations, one of my favorite ways to show that one integer divides another is to show that there exist a pair of groups $H, G$ with the corresponding cardinalities, one of which is a subgroup of the other. I know a few examples related to the symmetric groups in particular:

• $S_{m+n}$ contains the subgroup $S_m \times S_n$, hence $m! n! | (m+n)!$.

• $S_{mn}$ contains the subgroup $S_m \wr S_n$, hence $m!^n n! | (mn)!$. (See also the Young tableaux example I wrote about above.)

• The Sylow $p$-subgroups of $S_n$ are the iterated wreath product of cyclic groups of order $p$, as follows: divide $n$ up into $\lfloor \frac{n}{p} \rfloor$ blocks of $p$ elements and consider the permutations which preserve these blocks, then divide the blocks up into $\lfloor \frac{n}{p^2} \rfloor$ blocks and toss in permutations of these blocks, etc. Consequently $v_p(n!) = \sum_{k \ge 1} \lfloor \frac{n}{p^k} \rfloor$.

Answer 5

Here's the first "group theory" problem I ever saw (before I knew anything about groups). Consider the following tiling of a 4x4 square with 15 numbered square tiles and one empty square:

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 15 14 []

The [] is the empty square. You can slide any adjacent tile into the empty square, leaving its previous space empty. Is there any way to put the tiles in numerical order with the lower left corner empty (i. e., switch the 15 and 14)?

The solution is simple (but hardly obvious) even without explicitly mentioning group theory, but it's especially simple if you know a little bit about permutation groups.

Answer 6

Fermat's little theorem, which is easy to prove with cyclic groups, can be used to prove that an integer is composite without producing a factorization.

Answer 7

This summer I developed a minicourse for high school students in group theory. We discussed the game of 15, SET, wallpaper patterns, and Rubik's cube. Maybe this could be helpful:

www-math.mit.edu/~etingof/groups.pdf

in particular, we used this diagram for recognition of the 17 plane patterns:

www-math.mit.edu/~etingof/Patternsdiagram.pdf

Answer 8

This thread has been dormant for some time, and the class which motivated it is probably by now over, but I've just stumbled across it and can't help but mention an interesting and surprising example of elementary group theory making an appearance in anthropology.

This comes from an appendix, "On the Algebraic Study of Certain Types of Marriage," that Andre Weil wrote for a book of Claude Levi-Strass.(!) (In turn, my knowledge of it stems from a mention of it in the book "Algebra" by T.T. Moh.) I can't find a good summary online, so:

Anthropological Part

The following kinship system (the "Murngin system") is found apparently often in primitive societies:

(1) Every member of the society is assigned a type, with marriage only permissible for couples of the same type

(2) A person's type is a determined solely by their gender and the type of their parents; in the opposite direction, the type of a person's parents can be determined by their gender and type.

(3) Blood relations only determine whether or not two people have the same type. (So if there is one instance of a father and son having the same type, all fathers and sons have the same type -- if this is opaque, it will be rephrased more transparently using group theoretic language below.)

(4) The type of brothers and sisters is always different.

(5) It is always possible for some descendants of any two people to get married.

An anthropologist might observe that first cousins whose mothers are sisters never marry, or that when there less than 4 types of people in a tribe a marriage between first cousins whose parents are oppositely gendered siblings is permissible, and wonder whether these are separate empirical observations, or already implied by observations made above. Some elementary group theory gives the answer.

Group Theoretic Part

(1)&(2) rephrased: If we let the types of people be $1, 2, ..., n$, then by (2) we can define the type of the son of a couple of type $i$ to be $s(i)$, and the type of a daughter to be $d(i)$. The second part of (2) is just the statement that $s$ and $d$ are group actions on the set of types.

(3) rephrased: If $H$ is the subgroup of $S_n$ generated by $s$ and $d$, we can rewrite (3) as the statement that for any element $g$ of $H$, if $g(i) = i$ for some $i$, then $g(i) = i$ for all $i$ (in other words $g=e$).

(4) rephrased: $s(i) \neq d(i)$, or equivalently $d^{-1}s(i) \neq i$, for all $i$.

(5) rephrased: The orbit of any number $i$ under $H$ is the entire set of types $\{1,2,...,n\}$.

We can see right away then that if cousins share mothers who are sisters, they cannot marry, as if the type of the male is $i$, the type of the female is $ddd^{-1}s^{-1}(i) = ds^{-1}(i) \neq i$. This of course is not hard to see without group theory, but we can do more.

Plainly if the tribe is going to perpetuate itself there must be more than 1 type. If there are 2 types, then $s$ must be $(12)$ (it cannot be $e$), and likewise for $d$, a contradiction.

In the case of 3 types, then it is a matter of running through possibilities to show $s = d^{-1} = (123)$ up to permutation of type.

In the case of 4 types, a similar but more lengthy computation yields that up to permutation of type, there are the following four possibilities:

1. $s = (1234)$, $d=e$
2. $s = (1234)$, $d = (13)(24)$
3. $s = (1234)$, $d = (1432)$
4. $s = (12)(34)$, $d = (13)(24)$.

In both the case of 3 different types and 4 different types, it is now easy to verify that the group generated by $s$ and $d$ is commutative, proving that the statement about permissible marriages made earlier will always hold for such a type system.

...Hopefully at least a little interesting. I suppose some of the more geometric examples above might make for a more visceral application of group theory, at least on first exposure.

Answer 9

One of my favourite easy group theory problems:

Any prime number $p$ divides $f_{2p(p^2-1)}$, where $f_n$ is the Fibonacci sequence.

Proof: Let

$$G:= \{ A \in M_2 (Z_p) | \det(a)= \pm1 \}$$

and let

$$F=\left( \begin{array}{c c} 1 & 1 \\\\ 1 & 0 \\\\ \end{array}\right) $$

Then $F \in G$ and $G$ is a group of order $2p(p^2-1)$.

Thus

$$\left( \begin{array}{c c} f_{n+1+2p(p^2-1)} & f_{n+2p(p^2-1)} \\\\ f_{n+2p(p^2-1)} & f_{n+2p(p^2-1)-1} \end{array}\right)$$

$$= F^{n+2p(p^2-1)}= F^n = \left( \begin{array}{c c} f_{n+1} & f_{n} \\\\ f_{n} & f_{n-1} \end{array}\right) \mod p \,.$$

P.S. Better periods can be obtained by solving the linear reccurence in $Z_p$ if $p =\pm1 \mod 5$ or in an algebraic extension if $p =\pm 2 \mod 5$, but that's exactly the same thing as calculating the order of the matrix $F$ by diagonalizing it.

The same idea can be used for any linear recurrence, but one has to replace $G$ by $GL_2(Z_p)$, and discuss the cases when $p$ divides or doesn't divide the free term of the polynomial associated to teh recurrence.

PPS: Can anyone please fix my matrices.

Answer 10

There's a slightly eccentric (but entertaining) book by Budden called "The Fascination of Groups" that has an extensive chapter about the application of groups to the British practice of "change ringing" (this actually is featured prominently in the Dorothy Sayers, Lord Peter Wimsey mystery, "The Nine Tailors"). Change Ringing is the practice of ringing all the permutations of some number of church bells (usually 5 or 6, but can be as many as 9) with the requirement that successive permutations differ by a two-cycle (i.e. just swapping the order of two particular bells). Why this practice arose, I don't really know, but it sets up interesting algorithmic and mathematical problems.

Answer 11

This is related to many of the answers already here, but a little different. When I was an undergrad, I got fixated on the following problem:

Given a deck of $n$ cards, how many perfect shuffles does it take to get back to the starting position. Does it matter if this preserves the top and bottom card (what I called an "out shuffle") or mixed them in ("an in shuffle")? This leads to the discrete logarithm problem and other stuff with cyclic groups.

Answer 12

The set of rational tangles has a nice identification with $PSL(2,Z)$. Here's a formal treatment: Rational Tangles and the Modular Group. And here's an easy version aimed at teachers: http://www.geometer.org/mathcircles/tangle.pdf.

Rather than repeat what's written in these papers I'll just say this: We can use the isomorphism, and a bit of continued fractions, to give us a procedure for undoing tangles. I think it gives a wonderful example of how the same abstract group structure appears in two entirely different looking places: topology and (elementary) arithmetic.

Answer 13

There's a group-action proof of the famous Morley's theorem in Euclidean Geometry: http://www.ems-ph.org/journals/newsletter/pdf/2004-12-54.pdf. It's near the end of Alain Connes's article. This proof very convincingly shows that geometry is about symmetry which is what groups are about.

Answer 14

Theorem 5.10 of http://www-math.mit.edu/~rstan/algcomb.pdf is proved by elementary group theory and linear algebra. It states the following:

(a) Fix $m\geq 1$. Let $p_i$ be the number of
nonisomorphic simple graphs with $m$ vertices and $i$ edges. Then the
sequence $p_0, p_1,\dots,p_{{m\choose 2}}$ is symmetric and unimodal. (This means that $p_i=p_{{m\choose 2}-i}$ and $p_0\leq p_1 \leq \cdots \leq p_{\lfloor \frac 12{m\choose 2}\rfloor}$. The symmetry propery is trivial, but unimodality is another story.)

(b) Let $T$ be a collection of nonisomorphic simple graphs with $m$ vertices such that no element of $T$ is isomorphic to a spanning subgraph of another element of $T$. Then $|T|$ is maximized by taking $T$ to consist of all nonisomorphic simple graphs with $\lfloor \frac{1}{2}{m\choose 2}\rfloor$ edges.

Many similar results can be proved using the techniques of the above link.

Answer 15

Peg solitaire can be analyzed by putting elements of the Klein group on the diagonals of the board so that whenever you make a legal move the product of the elements with pegs is invariant. You can prove that European solitaire is unsolvable (when the central peg is missing) or that if solve the English version and the last peg isn't in the center, your last move was very, very stupid.

Answer 16

I love the proof of Wilson's theorem through consideration of the multiplicative group of integers modulo-p. The solution is very slick and it wasn't until I saw this early in an undergraduate course that I truly understood the power of group theory and its wide range of applicability. It also has a nice bit of history to it: After neither Wilson nor his mentor Waring was able to give a proof of the assertion, Gauss remarked in Disquisitiones Arithmeticae: "And Waring confessed that the proof seemed the more difficult, since one cannot imagine any notation to express a prime number. – In our opinion, however, such truths should be extracted from notions rather than from notations".

Answer 17

One can use finite group theory to understand the Rubik's cube. This might not be as elementary as you're looking for, but it's usually pretty entertaining.

Answer 18

This may be a bit frivolous, but I was told the following puzzle by Peter Cameron:

A prison has $2n$ prisoners. One day the warden decides to set them a challenge. The prisoners' names are put in boxes, one in each box. Each prisoner is then independently allowed to look in up to $n$ of the boxes - he looks inside one box, then another, and so on, with a free choice of box at each step. After this the warden will ask each of the prisoners to say which box contains their name. The prisoners succeed if all of them give the correct answer, and all fail if any of them gives an incorrect answer. Before the challenge starts, the prisoners can agree a strategy, but once they start looking in boxes, no information passes between them (so they don't know for instance which boxes have been looked in). Random strategies are allowed.

There is a strategy for the prisoners that gives them a probability of success bounded away from $0$ for $n$ arbitrarily large. (I won't give the answer away, but suffice to say it involves permutations.)

Answer 19

The calculation of the probability of getting a graph isomorphic to a specific graph $\Gamma$ when picking a uniformly random graph of with the same number of vertices as $\Gamma$.

Answer 20

Consider the Westminister Chimes. If you consider the 4 notes as your elements and the operation of switch (where you swap any two notes), the westminister chimes have all the characteristics of a group. One note of caution....there appear to be a number of 'modified' westminister chimes that alter one note here or there....you have to find the original one). This is particularly effective with math students who are from the fine arts area. They see that math is really infused in everything that is done.

Answer 21

Using permutations group to study solving and/or showing the impossibility of solving given initial configurations of the 15-puzzle (roughly, one can only solve "even" permutations of the puzzle). Cute, non-abelian, and non-obvious -- and most students will have seen the puzzle.

Edit: Ah, sorry for the repeat. Darsh beat me to it mid-writeup.

Answer 22

I always liked knot coloring and how it related to knot groups and classifications of knots. The property of if a knot is n-colorable or not is an property of the knot (so it doesn't change under any movement that doesn't cross the strands of the knot). The colors of a presentation of a knot's strands can be assigned labels which are related to each other according to whoever moves over/under a strand, which can lead to a generalized way to label the strands of a knot in a way that assigns (almost uniquely) a group to each knot (usually defined in terms of the fundamental group of $\mathbb{R}^3-K$, but you can get at it through a particular presentation, too.)

An example with pictures, http://en.wikipedia.org/wiki/Fox_n-coloring

There are also associated group-like structures, http://unapologetic.wordpress.com/2007/05/02/more-knot-coloring/

Answer 23

Another nice arithmetic application of (cyclic) group theory is the fact that the multiplicative group of a finite field is cyclic, or (in down-to-earth terms) that one can obtain every non-zero residue class modulo a prime just taking consecutive powers of a single well-chosen one.

I always give this example in my undergraduate Algebra course because it also gives me the occasion to show that in maths there are still questions which are unanswered but can be easily understood by a beginner (obviously, I'm referring to Artin's conjecture in this context).

Answer 24

Suppose one has a rectangle and a rhombus neither of which are squares. Which is more symmetric?

I think that issues about symmetry naturally lead to ideas that show how powerful thinking about the theory of groups is.

In addition to the above question there is the issue of how many different kinds of patterns one can have on a strip (frieze patterns). Though visually there appears to be great complexity there is a natural sense in which there are only 7 types of patterns. One can generalize to patterns in the plane (17 wallpaper groups) and to patterns where colors are allowed.

Details and lovely pictures can be found in:

Grunbaum and Shephard, Tilings and Patterns Conway, Burgiel, and Goodman-Strauss, The Symmetries of Things

Answer 25

Quintic equations?

Answer 26

Let $A$, $B$, $C$ be subsets of a finite set $X$. Let $A \Delta B$ denote the symmetric difference of $A$ and $B$, i.e. the set of elements of $X$ lying in exactly one of $A$ and $B$. Then $A \Delta B$ = $C \Delta D$ if and only if $A \Delta C = B \Delta D$.

This has a one-line proof: take the symmetric difference of both sides of either equation with $B \Delta C$. Underlying this is the fact that the set of all subsets of $X$ is an elementary abelian group of order $2^{|X|}$ under symmetric difference, with the empty set as the identity.

Answer 27

How about Galois theorem that a prime degree equation is solvable if and only if all the roots are rational functions in two of the roots. I have read that Galois stated it this way, so that the statement does not involve the notion of a solvable group, but the proof uses the result that a transitive subgroup of $S_p$ ($p$ prime), is contained in the normalizer of the group generated by a $p$-cycle.

Answer 28

This problem might be related to some of the ones suggested above, I did not check carefully.

Assume that you have to prepare the calendar of a basketball league to which $2n$ teams take part, where $n$ is an integer $\geq 1$. The full season consists of $2n-1$ dates where in each date each of the team has to play against another one (different than itself :-)). This has to be done in such a way that, overall, every team meets every other team exactly once (we all know what the calendar of a basketball league look like).

A solution is given in the comment below. The solution I had first suggested was wrong.