HMMT 二月 2004 · 团队赛 · 第 6 题
HMMT February 2004 — Team Round — Problem 6
题目详情
- [20] Prove that the number of odd numbers in row n is at most twice the number of switch pairs in row n − 1.
解析
- Prove that the number of odd numbers in row n is at most twice the number of switch pairs in row n − 1. Solution: Each odd number in row n is the sum of two of the three numbers above it in row n − 1; these three numbers cannot all have the same parity (or else any sum of two of them would be even), so somewhere among them is a switch pair. Since each switch pair in row n − 1 can contribute to at most two odd numbers in row n in this manner (namely, the two numbers immediately below the members of the pair), the result follows.