In how many ways can you paint the six vertices of a regular pentagonal pyramid using at most six different colours

combinatoricscontest-math

In how many ways can you paint the six vertices of a regular pentagonal pyramid
using at most six different colours, such that two vertices connected by an edge
have different colours? If the result of one way of painting may be obtained by
rotation from the result of another way of painting, only one of them will be
counted.

enter image description here

The answer is supposedly 288 but I keep getting answers significantly greater than that. Solutions would be appreciated.

taken from the 2018 BIMC https://chiuchang.org/imc/wp-content/uploads/sites/2/2018/07/BIMC-2018_Keystage-3_Individual.x17381.pdf

Best Answer

Call the peak color $p$. Because the peak is adjacent to every base vertex, no base vertex can have color $p$. On the base, note that no color can be used more than twice without being forced to be a neighbor of itself. So there are 3 possible cases:

  • 5 colors used: $c_1, c_2, c_3, c_4, c_5$, each used once.
  • 4 colors used: $c_2$ is used twice, $c_1, c_3, c_4$ each used once.
  • 3 colors used: $c_1$ used once, $c_2, c_3$ each used twice.

In the 5 base color case, We fix a vertex as being $c_1$ and proceed to the right to label the other colors. All orderings are distinct, so we have $6!$ ways to assign actual colors to $p$ and $c_1$ through $c_5$. Each ordering has 5 rotations, so the number of distinct colorings is $\frac {6!}5$.

In the 4 base color case, we set $c_1$ to be the color of the vertex which is between the two vertices that are the same, so the colors (preceeding to the right) are $c_1 - c_2 - c_3 - c_4 - c_2$. This assignment doesn't allow for rotation. So there are $5!$ ways of coloring the vertices with 1 peak + 4 base colors. So there are $\frac {6!}{1!}$ ways of coloring the vertices with 1 peak + 4 base colors.

In the 3 base color case, we set $c_1$ to be the color that is used only once. Again, this uniquely identifies the $c_1$ color, so rotations are not possible. There are $4!$ ways to assign the colors. There are $\frac{6!}{2!}$ ways to assign the colors.

So I get a total of $$\frac {6!}5 + \frac {6!}{1!} + \frac{6!}{2!} = 144 + 720 + 360 = 1224$$

If you make the same mistake I had made and forget that you are still picking from 6 colors, even when you are only picking 5 colors or 4 colors total, then you get $\frac {6!}5 + 5! + 4! = 288$. So apparently that was the source of the error in the "solution" you found.

Related Question