Maths Olympiad Prep

Library / /12 of 19

Combinatorics Difficulty 5.1 AIME, harder Prove it United States

Problem:

How many ways are there to color the five vertices of a regular 17-gon either red or blue, such that no two adjacent vertices of the polygon have the same color?

Solution

Solution:

The answer is zero! Call the polygon A1A2A17A_{1} A_{2} \ldots A_{17}. Suppose for contradiction such a coloring did exist.
If we color A1A_{1} red, then A2A_{2} must be blue. From here we find A3A_{3} must be red, then A4A_{4} must be blue; thus A5A_{5} must be red, A6A_{6} must be blue. Proceeding in this manner, we eventually find that A15A_{15} is red, A16A_{16} is blue, and then A17A_{17} is red. But A1A_{1} and A17A_{17} are adjacent and both red, impossible.

The exact same argument holds if we started by coloring A1A_{1} blue. Therefore, there are no colorings at all with the desired property.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.