Colour it Red!

Probability Level 4

I'm going to color four of the vertices of a regular octagon red, leaving the other four vertices alone. How many such colorings are there, up to a rotation?

11

<8

>11

9

10

8

2 solutions

Ivan Koswara
Mar 3, 2016

Burnside's lemma kills it. The underlying group is $C_8$ , rotations on an octagon (as is spelled out). Now,

Identity rotation: $\binom{8}{4} = 70$ colorings
Rotation by 45, 135, 225, or 315 degrees: No such coloring because all of them would need to be of the same color
Rotation by 90, 270 degrees: Every other vertex has the same color, so it's just choosing which of the two sets of four vertices is red: $\binom{2}{1} = 2$ colorings
Rotation by 180 degrees: Every opposite pair of vertices have the same color, so it's choosing two out of four pairs that are red: $\binom{4}{2} = 6$ colorings

On average, the number of colorings is $\frac{70+0+2+0+6+0+2+0}{8} = \boxed{10}$ , which is also the number of colorings up to rotation (by Burnside's lemma).

Moderator note:

Great! Burnside's lemma allows for easy counting under such scenarios where we want to account for symmetry (group actions).

Yes, that's exactly what I had in mind, and you explained it very well. Thanks! (+1)

Follow-up question: What if we allow reflections too?

Amusing historical note: On the Continent, this result is often attributed to Cauchy and Frobenius; as they explain here , one might call it "the lemma that is not Burnside's" ;)

Otto Bretscher - 5 years, 3 months ago

Plus reflections, the group is now $D_8$ . We have these two additions:

Reflection along the axis made by midpoints of two opposite sides (four such reflections): Four pairs of vertices again, so $\binom{4}{2} = 6$ colorings.
Reflection along the axis made by two opposite vertices (four such reflections): The two vertices on the axis will necessarily have the same color (because if only one of them is red, the number of red points is odd). Four pairs of vertices again, 6 coloring again.

Totaling everything gives $\frac{80 + 8 \cdot 6}{16} = \boxed{8}$ .

Ivan Koswara - 5 years, 3 months ago

Yes exactly! Perfect!

Otto Bretscher - 5 years, 3 months ago

Otto Bretscher
Mar 4, 2016

Ivan has written a fine conceptual solution. Since we are dealing with rather small numbers, it is also possible to enumerate the possible colourings.

Let's label consecutive vertices 1,2,...,8, and let's put the largest set of consecutive coloured vertices first:

1234, 1235, 1236, 1237, 1245, 1246, 1247, 1256, 1257, and 1357... $\boxed{10}$ in all

If we allow reflections as well, then the cases 1235 and 1237 are identified, as are the cases 1257 and 1246, for a total of 8 possible colourings.

@Otto Bretscher Sir, isn't it possible to obtain 1237 from 1235 by 1 rotation? If we rotate the octagon about the line passing through 2 and 6 by 180 degrees then we can get the other one.

Nitish Joshi - 5 years, 3 months ago

Colour it Red!

2 solutions

Moderator note:

0 pending reports