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

HMMT February 2004 — Team Round — Problem 7

[25] Prove that the number of switch pairs in row n is at most twice the number of switch pairs in row n − 1. 1 Written In The Stars [125 points] 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 .

解析

Prove that the number of switch pairs in row n is at most twice the number of switch pairs 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 by even numbers, except that one even number may simultaneously be an endpoint of two odd blocks. Each odd block contributes two switch pairs to row n , so it is enough to show that each odd block has a switch pair somewhere above it in row n − 1. But the odd 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 terms immediately above it would be all odd or all even, and then the second term in our block would have to be even, contradicting the assumption that it was O . This proves the 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 .