Browse · MathNet
PrintSelected Problems from the Final Round of National Olympiad
Estonia counting and probability
Problem
Ants has three pencils, each of a different color. In how many ways can he paint the faces of a regular octahedron in such a way that faces with a common edge always have different colors? Colorings that can be obtained from each other via rotations of the octahedron are considered the same.
Solution
i) Case . There are possibilities to choose two colors from the three. After that, there is only one possibility to paint the octahedron. Thus there are possibilities to paint.
ii) Case . Ordering the colors can be done in ways. After that, there is only one possibility to paint the octahedron, since the color used times must occur twice among the faces adjacent to one vertex and twice among the faces adjacent to the opposite vertex. The remaining two colors can be deployed in principle in only one way. Thus there are possibilities to paint.
iii) Case . Choosing the color that is used times can be done in different ways. After that, the octahedron can be painted in only way, since after faces have been painted with the same color, faces with either of the other colors must meet at the same vertex. Thus there are possibilities to paint.
iv) Case . Choosing the color that is used only twice can be done in ways. If the faces painted with this color met at a common vertex , the faces adjacent to the opposite vertex would be painted alternately with the other two colors. But then the remaining two faces adjacent to would have to be painted with the same color, that contradicts the case assumption. Hence the color that occurs twice is used on a pair of opposite sides. The other colors occur alternately on the surface formed by the remaining six faces. Thus there are possibilities to paint.
Consequently, the number of all colorings is .
ii) Case . Ordering the colors can be done in ways. After that, there is only one possibility to paint the octahedron, since the color used times must occur twice among the faces adjacent to one vertex and twice among the faces adjacent to the opposite vertex. The remaining two colors can be deployed in principle in only one way. Thus there are possibilities to paint.
iii) Case . Choosing the color that is used times can be done in different ways. After that, the octahedron can be painted in only way, since after faces have been painted with the same color, faces with either of the other colors must meet at the same vertex. Thus there are possibilities to paint.
iv) Case . Choosing the color that is used only twice can be done in ways. If the faces painted with this color met at a common vertex , the faces adjacent to the opposite vertex would be painted alternately with the other two colors. But then the remaining two faces adjacent to would have to be painted with the same color, that contradicts the case assumption. Hence the color that occurs twice is used on a pair of opposite sides. The other colors occur alternately on the surface formed by the remaining six faces. Thus there are possibilities to paint.
Consequently, the number of all colorings is .
Final answer
15
Techniques
Enumeration with symmetryColoring schemes, extremal arguments