MathLabs

第6問

66 問が出題された数学コンテストにおいて、どの二問の組についても、その両方を解いた参加者が全体の 25\frac25 より多かった。さらに、66 問すべてを解いた参加者はいなかった。このとき、ちょうど 55 問を解いた参加者が少なくとも 22 人いることを示せ。
ステップ 3/6: 十四個のペア数は kk に等しく、残る一個は k+1k+1 に等しい
前のステップ次のステップ
ざっくり言うと

1515 個の整数ペア数はそれぞれ 2n+15\frac{2n+1}{5} 以上であり、その合計は 15⋅2n+1515\cdot\frac{2n+1}{5} をわずか 11 しか上回らない。したがって 2n+15\frac{2n+1}{5} 自身が整数 kk でなければならず、十四個が kk、ただ一個だけが k+1k+1 となる。

∑i=15ti+∑1≤i<j≤5tij=10+6(n−1)=6n+4=15⋅2n+15+1\sum_{i=1}^5 t_i+\sum_{1\le i<j\le 5}t_{ij}=10+6(n-1)=6n+4=15\cdot\frac{2n+1}{5}+1
詳しい解説

1515 個のペア数の総和は、各参加者が解いたペア数を二重に数えたものである。一人の 55 問解答者は (52)=10\binom52=10 ペアを寄与し、n−1n-1 人の 44 問解答者はそれぞれ (42)=6\binom42=6 ペアを寄与するので、∑ti+∑tij=10+6(n−1)=6n+4\sum t_i+\sum t_{ij}=10+6(n-1)=6n+4。一方、1515 個の数はそれぞれ ≥2n+15\ge\frac{2n+1}{5} を満たす整数であり、15⋅2n+15=6n+315\cdot\frac{2n+1}{5}=6n+3 は 6n+46n+4 より 11 小さいだけである。もし 2n+15\frac{2n+1}{5} が整数でなければ、各数は ≥2n+25\ge\frac{2n+2}{5} となって総和が ≥6n+6\ge 6n+6 となり矛盾する。よって k=2n+15k=\frac{2n+1}{5} は整数であり、1515 個のうち十四個は kk、残る一個は k+1k+1 に等しい。