$2013$ 个白球和 $2014$ 个黑球任意排成一列,求证:无论如何排列,都至少有个黑球,其左侧(不包括它自己)的黑球和白球的个数相等(可以为 $0$).
【难度】
【出处】
2013年湖南省高中数学竞赛
【标注】
  • 数学竞赛
    >
    简单组合
    >
    简单组合
  • 方法
    >
    思考方式
    >
    构造半不变量
  • 题型
    >
    组合数学
    >
    组合证明
【答案】
【解析】
记 $f(k)$ 为第 $k$ 个黑球左侧(不包括它自己)的黑球数 $x_k$ 和白球数 $y_k$ 之差,即\[f(k)=x_k-y_k,k=1,2,\cdots,2014.\]情形一 $f(1)=0$,则第一个球为黑球即符合题意,命题成立.
情形二 $f(1)\ne 0$,则第一个球为白球,此时 $f(1)\leqslant -1$,又 $f(n+1)\geqslant 0$,而\[|f(k+1)-f(k)|=1,\]于是必然存在 $2\leqslant m\leqslant 2014$,$m\in\mathbb Z$,使得\[f(m)=0,\]因此命题成立.
答案 解析 备注
0.114477s