日期:2018年6月28日


2017CaMO-3


问题: 已知集合S_n=\{1, 2, \cdots, n\}, T_nS_n的一个非空子集, 若T_n的元素的平均数等于T_n的中位数, 则称T_n是“平衡的”. 求证: 对所有正整数n, “平衡”子集T_n的个数是奇数.

(2017年加拿大数学奥林匹克第3题)

分析: 考虑配对思想.

证明: AS_n的任一平衡子集, 则S_n的子集A'=\{n+1-a\mid a\in A\}也是平衡的.

A\ne A', 则得到S_n的一对平衡子集.

A=A', 则得到S_n的一个平衡子集. 我们称这样的子集为回文子集.

所以只要证明S_n的非空回文子集有奇数个.

因为每个非空回文子集是

    \[\{1,n\},\{2,n-1\},\cdots,\left\{\left\lfloor\dfrac{n+1}2\right\rfloor,\left\lceil\dfrac {n+1}2\right\rceil\right\}\]

(特别地, 当2\nmid n时, \left\lfloor\dfrac{n+1}2\right\rfloor=\left\lceil\dfrac {n+1}2\right\rceil, 此集合是单元素集)的并集, 所以S_n2^{\left\lfloor\frac{n+1}2\right\rfloor}-1个非空回文子集.

对所有正整数n, \left\lfloor\dfrac{n+1}2\right\rfloor>0, 所以2^{\left\lfloor\frac{n+1}2\right\rfloor}-1是一个奇数.

从而“平衡”子集T_n的个数是奇数.