0
$\begingroup$

A circular tabletop is divided into four congruent sectors by two diameters that are perpendicular to each other. Each sector is to be painted with one of four colors. How many distinct ways can the table be painted? (A color may be used on more than one sector, but paintings that are the same after a rotation are not considered distinct.)


I got the answer 58 through bashy casework, but I'm not sure if that answer is even correct. Is there a clever-er or quicker way to do it?

Thanks!

$\endgroup$
2
  • 1
    $\begingroup$ Burnside's lemma seems to be the way to go here. Are reflections counted as distinct, or not? Edit: in context I suppose reflecting the table wouldn't make sense. $\endgroup$ Aug 16 '20 at 18:34
  • $\begingroup$ What is burnside's lemma? $\endgroup$
    – Mike Smith
    Aug 16 '20 at 18:50
2
$\begingroup$

I'll put a full answer, assuming only rotations.

Burnside's lemma states that the number of ways to color an object with a group of symmetries $G$ is the average number of colorings fixed by each of the symmetries in $G$. That is, if $X^g$ is the number of colorings fixed by a group element $g \in G$, the total number of colorings under these symmetries is $$ \frac{1}{|G|} \sum_{g\in G} X^g. $$

The group of rotations $G = \langle r \rangle$ on the table is a cyclic group of order $4$, consisting of the identity $e$ (which doesn't move anything), the $90^{\circ}$ rotation clockwise $r$, the $180^{\circ}$ rotation $r^2$, and the $90^{\circ}$ rotation counterclockwise $r^3$.

Let us represent each coloring with the colors $c_1c_2c_3c_4$.

The number of colorings fixed under $e$, the identity, is simply every possible one. There are four possibilities for each of $c_1, c_2, c_3, c_4$, giving us $4^4 = 256$.

Now, $r$ acts on the coloring $c_1c_2c_3c_4$ by turning it into $c_2c_3c_4c_1$. This coloring is fixed if $c_1 = c_2 = c_3 = c_4$. The colorings fixed by the rotation $r$ are thus precisely the colorings for which there is only one color, and there are thus clearly $4$ of these. By symmetry, this is the number of colorings fixed by $r^3$ as well.

Finally, $r^2$ turns $c_1c_2c_3c_4$ into $c_3c_4c_1c_2$. These two colorings are the same if $c_1 = c_3, c_2 = c_4$. Thus, the colorings fixed by $r^2$ are precisely the colorings with at most two alternating colors. These colorings are determined by $c_1$ and $c_2$, and so there are exactly $4 \cdot 4 = 16$ of these.

Thus, the number of colorings required is $\frac{1}{4}(256 + 4 + 4 + 16) = 70$.

$\endgroup$
4
  • $\begingroup$ Could you direct me to a proof of Burnside's Lemma? $\endgroup$
    – Mike Smith
    Aug 16 '20 at 18:57
  • 1
    $\begingroup$ Here's the usual Wikipedia article, but the language is quite group-theoretic. en.wikipedia.org/wiki/Burnside%27s_lemma $\endgroup$ Aug 16 '20 at 19:01
  • 1
    $\begingroup$ 1/ I like to think of it, combinatorially, as a double-counting correction of sorts. This is a bit more obvious in the following example: suppose you have $n$ people to be seated at a circular table. Naively, you would count $n!$ ways to arrange them. Of course, if we're treating rotationally equivalent arrangements as the same, there's overcounting of sorts. To avoid this, fix one of these $n$ people as an anchor, seat them at any of $n$ possible seats. This tells us that the $n!$ is an overcount by a factor of $n$, and so there are $(n - 1)!$ seatings. $\endgroup$ Aug 16 '20 at 19:12
  • 1
    $\begingroup$ 2/2 Now, do the calculation above, using Burnside's lemma with the group of rotations by $0, 1, 2, \dots, n - 1$ seats. $\endgroup$ Aug 16 '20 at 19:12
2
$\begingroup$

First, we have $4$ colourings with only one colour.

Then, we have ${4\choose 2}=6$ colourings with two colours and a repeating pattern (e.g. black/white/black/white).

Out of $4^4=256$ colourings of the table distinguishing the orientation, the first $4$ colourings correspond to $4$ colourings. The other $6$ colourings correspond to $6\times 2=12$ colourings.

The remaining $256-4-12=240$ colourings are all asymmetrical, and so groups of $4$ of them correspond to a single colouring disregarding the orientation. Thus, the number of those colourings is $240/4=60$.

Putting it all together, we end up with $60+4+6=70$ colourings.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.