第6問

6

問が出題された数学コンテストにおいて、どの二問の組についても、その両方を解いた参加者が全体の

\frac25

より多かった。さらに、

6

問すべてを解いた参加者はいなかった。このとき、ちょうど

5

問を解いた参加者が少なくとも

2

人いることを示せ。

ステップ 1/6:

5

問解答者一人と

4

問解答者

(n-1)

人に標準化する

前のステップ次のステップ

ざっくり言うと

$5$ 問解答者が高々一人の反例があれば、トップの一人が $5$ 問、他の全員が $4$ 問になるまで正解を追加しても各ペアの解答数は増えるだけなので、反例は保たれたまま完全に剛な形になる。

n=1+\sum_{i=1}^5 a_i+\sum_{1\le i<j\le 5}b_{ij}

詳しい解説

背理法のため、 $5$ 問を解いた参加者は高々一人と仮定する。参加者に正解を追加しても各ペアの解答数は増えるだけで仮定は破られないので、一般性を失わず、一人の参加者が問題 $1,2,3,4,5$ を解き（問題 $6$ を落とし）、他のすべての参加者が $4$ 問を解いたとしてよい。残りの $n-1$ 人のうち、問題 $6$ と問題 $i$ を落とした人数を $a_i$ （ $1\le i\le5$ ）、問題 $6$ を解き問題 $i,j$ を落とした人数を $b_{ij}$ （ $1\le i<j\le5$ ）とおくと、 $n=1+\sum_{i=1}^5 a_i+\sum_{1\le i<j\le5}b_{ij}$ となる。