HMMT 二月 2004 · 团队赛 · 第 7 题

英文解析

7. Prove that the number of switch pairs in row n is at most twice the number of switchpairs in row n − 1.
   Solution: If we go sufficiently far to the left or right in row n , we get to zeroes.
   Therefore, row n consists of a finite number of “odd blocks” of the form
   EOOO · · · OE
   (where E represents an even number and O an odd number), which are separated byeven numbers, except that one even number may simultaneously be an endpoint of twoodd blocks. Each odd block contributes two switch pairs to row n , so it is enough toshow that each odd block has a switch pair somewhere above it in row n − 1. But theodd block consists of at least one O between two E ’s, making for at least three terms.
   If there were no switch pairs above the block, then in particular, the first three termsimmediately above it would be all odd or all even, and then the second term in ourblock would have to be even, contradicting the assumption that it was O . This provesthe result.
   Written In The Stars
   Suppose S is a finite set with a binary operation ? — that is, for any elements a, b of S ,
   there is defined an element a ? b of S . It is given that ( a ? b ) ? ( a ? b ) = b ? a for all a, b ∈ S .