MathLabs

第6問

66 問が出題された数学コンテストにおいて、どの二問の組についても、その両方を解いた参加者が全体の 25\frac25 より多かった。さらに、66 問すべてを解いた参加者はいなかった。このとき、ちょうど 55 問を解いた参加者が少なくとも 22 人いることを示せ。
ステップ 6/6: ただ一つの (k+1)(k+1) 項を避ける分割を選ぶ
ざっくり言うと

一つの分割 {a,b,c}∪{d,e}\{a,b,c\}\cup\{d,e\} の合同式には十五個の tt のうち七個しか現れないので、その七個すべてが kk に等しくなるように分割を必ず選べる。すると合同式は k≡1+6k(mod3)k\equiv 1+6k\pmod3、すなわち 0≡1(mod3)0\equiv1\pmod3 となる。

k≡1+6k(mod3) ⟹ 1≡0(mod3)(contradiction)k\equiv 1+6k\pmod 3\ \Longrightarrow\ 1\equiv 0\pmod 3\quad(\text{contradiction})
詳しい解説

ステップ3より、十五個の tt のうち十四個は kk に等しく、ただ一個だけが k+1k+1 に等しい。例外の (k+1)(k+1) 項がある tet_e ならば、{a,b,c}⊂{1,2,3,4,5}∖{e}\{a,b,c\}\subset\{1,2,3,4,5\}\setminus\{e\} を選び残りの添字を dd とする。例外の項がある txyt_{xy} ならば、{x,y}\{x,y\} が {d,e}\{d,e\} でも {a,b,c}\{a,b,c\} の部分集合でもないように(すなわち x∈{a,b,c}x\in\{a,b,c\}、y∈{d,e}y\in\{d,e\} となるように){a,b,c}\{a,b,c\} を選ぶ。いずれの場合も、例外の項は tde,ta,tb,tc,tab,tbc,tcat_{de},t_a,t_b,t_c,t_{ab},t_{bc},t_{ca} の中に現れないので、これら七つはすべて kk に等しい。するとステップ5より k≡1+6k(mod3)k\equiv 1+6k\pmod3、すなわち 0≡1(mod3)0\equiv1\pmod3 となり矛盾する。したがって少なくとも 22 人の参加者が 55 問を解いた。