Competition problem — Combinatorics

Library / /15 of 15

Combinatorics Difficulty 5.9 AIME, harder Prove it United States

Problem:

An isolated island has the shape of a circle. Initially there are $9$ flowers on the circumference of the island: $5$ of the flowers are red and the other $4$ are yellow. During the summer $9$ new flowers grow on the circumference of the island according to the following rule: between $2$ old flowers of the same color a new red flower will grow, between $2$ old flowers of different colors, a new yellow flower will grow. During the winter, the old flowers die, and the new survive. The same phenomenon repeats every year.
Is it possible (for some configuration of initial $9$ flowers) to get all red flowers after finitely many years?

Solution

Solution:

The answer is "no". Assume that we got all red flowers in the year $n$ for the first time. Then in the year $n-1$ all the flowers were yellow. We will prove that this is impossible.

Let's change the weird story into the one with the flowers labeled by $1$ (instead of red) and $-1$ (instead of yellow). What really happens is that between two flowers $a$ and $b$ , the new flower will grow and will be labeled by $ab$ . Notice that the initial product of all numbers is $1$ , and at the end of each winter the product of the numbers is $1$ again, so it will never be equal to $-1$ ; hence it is impossible to get the configuration where all the flowers are yellow. This is a contradiction.

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.