$30$ 个人排成矩形,身高各不相同.把每列最矮的人选出,这些人的身高中最高的设为 $a$;把每行最高的人选出,这些人的身高中最矮的设为 $b$.
【难度】
【出处】
2008年上海交通大学冬令营选拔测试
【标注】
  • 题型
    >
    组合数学
    >
    组合证明
  • 题型
    >
    组合数学
    >
    组合证明
  1. $a$ 是否有可能比 $b$ 高?
    标注
    • 题型
      >
      组合数学
      >
      组合证明
    答案
    不可能
    解析
    不可能.证明如下:
     情形一若 $a,b$ 为同一人,有 $a = b$;
     情形二若 $a,b$ 在同一行、列,则有 $a \leqslant b$;
     情形三若 $a,b$ 不在同一行、列,如图,\[\begin{array}{|c|c|c|c|c|}\hline &&&& \\ \hline &&&& \\ \hline &x&&b& \\\hline &&&& \\ \hline &a&&& \\ \hline &&&& \\ \hline \end{array}\]记 $a$ 所在列与 $b$ 所在行相交的人为 $x$.因为 $a$ 为 $\left( {a,x} \right)$ 列最矮的人,所以有 $a < x$;又因为 $b$ 为 $\left( {b,x} \right)$ 行最高的人,所以有 $b > x$.于是有 $a < x < b$.
    综上,不可能有 $a > b$.
  2. $a$ 和 $b$ 是否可能相等?
    标注
    • 题型
      >
      组合数学
      >
      组合证明
    答案
    有可能
    解析
    有可能,不妨令 $30$ 个人身高由矮至高分别为 $1,2,3, \cdots ,30$,如图所示,\[\begin{array}{|c|c|c|c|c|}\hline 1&7&13&19&25 \\ \hline 2&8&14&20&26 \\ \hline 3&9&15&21&27 \\\hline 4&10&16&22&28 \\ \hline 5&11&17&23&29 \\ \hline 6&12&18&24&30 \\ \hline \end{array}\]此时有 $a = b = 25$.
题目 问题1 答案1 解析1 备注1 问题2 答案2 解析2 备注2
0.109872s