HMMT 二月 2010 · 冲刺赛 · 第 4 题

英文解析

4. [ 5 ] To set up for a Fourth of July party, David is making a string of red, white, and blue balloons. Heplaces 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 byat least two non-white balloons.
   • Blue balloons appear in groups of exactly three, and groups of blue balloons are separated by atleast three non-blue balloons.
   If David uses over 600 balloons, determine the smallest number of red balloons that he can use.
   Answer: 99 It is possible to achieve 99 red balloons with the arrangement
   WWBBBWW RBBBWWRBBBWW . . . RBBBWW ,
   ︸ ︷︷ ︸
   99 RBBBWW’swhich contains 99 · 6 + 7 = 601 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 validcombinations of white and blue balloons are WWBBB, BBBWW, and WWBBBWW (Any otherscontain the subsequence BBBWWBBB, which is invalid). The sequence . . . WWR must be followedby BBBWW; otherwise two groups of white balloons would be too close. Similarly, the sequence
   Guts Round
   RWW . . . must be preceded by WWBBB. It follows that WWBBBWW can be used at most once in avalid sequence, meaning that there can be at most 98 · 5 + 7 = 497 non-red balloons. Contradiction.
   Therefore the minimum is 99 red balloons. (Better if the party’s outdoors; then we’d have 99 redballoons floating in the summer sky. :-p)