Wolfram Cloud Document

CITE THIS NOTEBOOK: Group theory in Stanford Math Summer Camp 2023 Problem 2 by Shenghui Yang. Wolfram Community MAR 12 2023.

From SUMAC (Stanford Math Summer Camp) problems for program in 2023 Summer. The second problem gives applicant a taste of simple application of group theory, in particular permutation group. This short article demonstrates how to use the built-in Cycle, PermutationGroup and GroupStabilizerChain etc. to directly compute the possible candidates and reveal the more abstract concepts relating stabilizer and orbits in group theory.

Problem

Consider the following puzzle. Five coins are arranged around the vertices of a pentagon. The goal for this puzzle is to go from the starting configuration below

to a goal configuration that is a rearrangement of the coins around the pentagon. There are two allowable moves that can be applied repeatedly in any order:
• Move X: you can rotate the coins around the pentagon, and
• Move Y: you can rotate the coins in the upper triangle of the pentagon.

For example, two applications of move X from the starting position results in

Then one application of move Y to the above results in

Question: For each of the following, show that the given configuration can be obtained with a combination of moves X and Y, or prove no combination of moves X and Y lead to the given configuration:

◼

Analysis

Brutal force method: List all possible outcomes

To convert the statement of the problem, we argue that any configuration is reached by two simple group operation or their sequential combination:

In[]:=

pg=PermutationGroup[{Cycles[{{1,2,3,4,5}}],Cycles[{{1,2,5}}]}];

It is helpful to think other way round to understand the operation: the mini cyclone (x operation ) can travel clockwise along the side of the pentagon. Thus it is just Y applies onto X instead of directly on elements:

The group has moderate group size. Use GroupOrder function to find the number of valid elements in this operation:

In[]:=

GroupOrder[pg]

Out[]=

Therefore it is not hard to check all possible configurations with brutal force. We can enumerate the possible configurations by applying group elements onto

{"A","B","C","D","E"}

In[]:=

cycles=GroupElements[pg];

In[]:=

perms=Permute[{"A","B","C","D","E"},#]&/@cycles

Out[]=

{{A,B,C,D,E},{A,B,E,C,D},{A,B,D,E,C},{A,C,B,E,D},{A,D,B,C,E},{A,E,B,D,C},{A,C,D,B,E},{A,E,C,B,D},{A,D,E,B,C},{A,C,E,D,B},{A,D,C,E,B},{A,E,D,C,B},{B,A,C,E,D},{B,A,D,C,E},{B,A,E,D,C},{C,A,B,D,E},{E,A,B,C,D},{D,A,B,E,C},{C,A,E,B,D},{D,A,C,B,E},{E,A,D,B,C},{C,A,D,E,B},{E,A,C,D,B},{D,A,E,C,B},{B,C,A,D,E},{B,E,A,C,D},{B,D,A,E,C},{C,B,A,E,D},{D,B,A,C,E},{E,B,A,D,C},{C,D,A,B,E},{E,C,A,B,D},{D,E,A,B,C},{C,E,A,D,B},{D,C,A,E,B},{E,D,A,C,B},{B,C,E,A,D},{B,D,C,A,E},{B,E,D,A,C},{C,B,D,A,E},{E,B,C,A,D},{D,B,E,A,C},{C,E,B,A,D},{D,C,B,A,E},{E,D,B,A,C},{C,D,E,A,B},{E,C,D,A,B},{D,E,C,A,B},{B,C,D,E,A},{B,E,C,D,A},{B,D,E,C,A},{C,B,E,D,A},{D,B,C,E,A},{E,B,D,C,A},{C,D,B,E,A},{E,C,B,D,A},{D,E,B,C,A},{C,E,D,B,A},{D,C,E,B,A},{E,D,C,B,A}}

Because the list includes all valid solutions, we solve the problem by checking the membership of the configurations in the question:

AEDCB (CW) is possible

In[]:=

MemberQ[perms,{"A","E","D","C","B"}]

Out[]=

True

And we find that the action generated by interchangeing 2/5 and 3/4. This is valid with using X and Y moves only.

In[]:=

Position[perms,{"A","E","D","C","B"}][[1,1]]

Out[]=

In[]:=

cycles[[12]]

Out[]=

Cycles[{{2,5},{3,4}}]

ABDCE (CW) is not possible

This configuration is not in the permutation group element

In[]:=

MemberQ[perms,{"A","B","D","C","E"}]

Out[]=

False

Use group stabilizer

For larger group it would be impossible list all candidates. Just like we use modular arithmetic to classify integer in a handful finite cases, we need to group the group elements into very few cases. Here we can take a look our group elements deeper. One good way is to see how many points are fixed in the list.

In[]:=

res=GroupBy[perms,Count[#-Threaded@{"A","B","C","D","E"},0]&]

Out[]=

5{{A,B,C,D,E}},2{{A,B,E,C,D},{A,B,D,E,C},{A,D,B,C,E},{A,E,B,D,C},{A,C,D,B,E},{A,E,C,B,D},{A,C,E,D,B},{A,D,C,E,B},{C,A,B,D,E},{D,A,C,B,E},{E,A,C,D,B},{B,C,A,D,E},{D,B,A,C,E},{E,B,A,D,C},{B,D,C,A,E},{C,B,D,A,E},{E,B,C,A,D},{B,E,C,D,A},{C,B,E,D,A},{D,B,C,E,A}},1{{A,C,B,E,D},{A,D,E,B,C},{A,E,D,C,B},{B,A,C,E,D},{B,A,D,C,E},{B,A,E,D,C},{C,B,A,E,D},{C,D,A,B,E},{C,E,A,D,B},{D,B,E,A,C},{D,C,B,A,E},{D,E,C,A,B},{E,B,D,C,A},{E,C,B,D,A},{E,D,C,B,A}},0{{E,A,B,C,D},{D,A,B,E,C},{C,A,E,B,D},{E,A,D,B,C},{C,A,D,E,B},{D,A,E,C,B},{B,E,A,C,D},{B,D,A,E,C},{E,C,A,B,D},{D,E,A,B,C},{D,C,A,E,B},{E,D,A,C,B},{B,C,E,A,D},{B,E,D,A,C},{C,E,B,A,D},{E,D,B,A,C},{C,D,E,A,B},{E,C,D,A,B},{B,C,D,E,A},{B,D,E,C,A},{C,D,B,E,A},{D,E,B,C,A},{C,E,D,B,A},{D,C,E,B,A}}

In particular we want {A, B} are fixed:

In[]:=

Cases[res[2],{"A","B",___}]

Out[]=

{{A,B,E,C,D},{A,B,D,E,C}}

Notice that (ECD) (DEC) from the above result together with (CDE) forms a cyclic permutation (CW)

Therefore it is not possible to have (EDC) in clockwise direction after we fix A and B.

Use built-in GroupStabilizerChain as One-liner

Formally the above observation is named stabilizer of a group. The result of following application of GroupStabilizerChain shows that configurations given fixture of certain elements. It is possible to fix nothing (ie the whole thing rotate clockwise), one element and up to two elements (discard the trivial fixture of 5 elements):

The case {1,2} says that if A and B is fixed, the remaining item can only permute in clockwise cyclic motion (3,4,5) (4,5,3) (5,3,4), which is the same as our discussion. Therefore the second configuration is not possible:

Summary

◼

Use PermutationGroup and Cycles to generate all possible configuration of the coins

◼

GroupStabilizerChain specifies fixed points and we can check if it possible to fix more points from there

◼

The following poster also shows the valid configuration by stablizers.