这题怎么解答? 第1页

很多答题者似乎都没有看清题目. 虽然此类表述在组合数学中是常见的, 但可能接触得不多的人容易曲解题意吧.

证明: 记T= . 对于集合T, 定义

先说明C不小于T .

为此, 取51个数为T, 49个数为0. 这100个数被划分为集合A与B, |A|=|B|=50, 若A与B中T出现的次数相同, 则T的总个数为偶数, 矛盾. 所以A与B中T出现次数至少相差1, 所以|S(A)-S(B)|不小于T, 所以C至少为T.

再证明C可以为T.

反设结论不成立, 设这100个数为 . 设A与B为这100个数的划分, 且A与B元素个数相同, 且使得|S(A)-S(B)|最小. 因为结论不成立, 故有|S(A)-S(B)|>T.

不妨设S(A)>S(B). 称满足 的(i, j)对为"好对". 则由排序知 . 若好对满足 , 则在A中删除 添加 得到A' , 在B中删除 添加 得到B'(下文称此操作为(i, j)交换), 则有

又

于是 与最小性矛盾.

故好对满足

(I)若不存在好对, 则对任意 都有 , 称(i, j)为平衡对, 进行(i, j)交换, 交换后对A,B实际取值无影响, 但平衡对个数会减少. 不断操作直到不存在平衡对, 即A中最大元素不大于B中最小元素, 记为A<B, 此时 矛盾.

(II)存在好对, 设其中之一为(i, j), 有 , 且前者属于A, 后者属于B. 易知全部100个数中没有一个在[1-T,T]之间, 否则由(1)矛盾. 设100个元素中有a个小于1-T称为小数, 有(100-a)个大于T称为大数, 则因为100数和为50有 得a=50

显然小数中既有A元素又有B元素, 大数同样. 设A中的小数构成集合 , A中的大数构成集合 , 类似定义 . 显然大数间不存在好对, 小数间也不存在好对. 同(I)可知通过调整可使得 . 设 , 则 .

所以 得 ,

又 得

所以a=26

将 中所有数用其平均值u代替, 同样 用w代替, 用v代替, 用t代替, 此时新的集合依然满足条件, 且S(A)-S(B)大小不变. 则

若方程组有解, 利用调整法(考虑u,v,w,t的相空间), 可设解在(u, w)=(0, 0)或(v, t)=(1,1)或(u, t)=(0, 1)时取到, 前两种情况都有(u,w,v,t)=(0,0,1,1), 48u+52v-50=2>1矛盾, 第三种情况有 矛盾. 综上, 方程组无解, 矛盾.

所以C=T时结论成立.

利用同样的方法可以证明把原题100换成4k时,

希望有人能推广到2t的情况(上面的情况就是t为偶数时), 我实在没力气了, 知乎回答问题真累, 我终于明白数学家为什么至今还在手写了...