To set up for a Fourth of July party, David is making a string of red, white, and blue balloons. He places them according to the following rules: - No red balloon is adjacent to another red balloon. - White balloons appear in groups of exactly two, and groups of white balloons are separated by at least two non-white balloons. - Blue balloons appear in groups of exactly three, and groups of blue balloons are separated by at least three non-blue balloons. If David uses over 600 balloons, determine the smallest number of red balloons that he can use.
Solution
It is possible to achieve 99 red balloons with the arrangement which contains balloons. Now assume that one can construct a chain with 98 or fewer red balloons. Then there can be 99 blocks of non-red balloons, which in total must contain more than 502 balloons. The only valid combinations of white and blue balloons are WWBBB, BBBWW, and WWBBBWW (Any others contain the subsequence BBBWWBBB, which is invalid). The sequence ...WWR must be followed by BBBWW; otherwise two groups of white balloons would be too close. Similarly, the sequence RWW . . . must be preceded by WWBBB. It follows that WWBBBWW can be used at most once in a valid sequence, meaning that there can be at most non-red balloons. Contradiction. Therefore the minimum is 99 red balloons.
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.