2011年のトルコのジュニア数オリがわかりません。

面白い問題ですね。


＞And at least one of the problems selected by any student is selected by at most one other student.

訳：「どの学生が選んだ２個の問題ペアも，そのうち片方または両方の問題が，自分を含め１人または２人にしか選ばれていない。」


つまり，２部グラフで考えると，辺のうち片方または両方で次数が１または２です。

もしも辺の片方で次数が１または２でない場合，
つまり３以上である場合は，
辺のもう片方の次数が１または２である必要があります。

そうでないと，辺の両方で次数が３以上となり，
「問題ペアのうち少なくとも片方が，最大２人にしか選ばれていない」
という条件に反します。

なので次数３が出てきます。


そのことを述べたのが次の文です。

＞The condition is that, if the degree of one end of any edge is at least 3 then the degree of the other end of the edge is at most 2.

訳：「この条件を２部グラフ上で解釈しなおすと，辺の１つの頂点の次数が３以上であれば，その辺のもう片方の頂点の次数は最大２である。」・・・（☆）

この条件下で，辺の数を最大化すればよいんですね。


＞たとえば数学，物理とも2問だった場合，m1-p1, m1-p2, m2-p1, m2-p2と結ぶ「4人」は…

これは題意の条件を満たしていると思います。


リンク先の解答の結果部分の式は，どうも間違っているようですね。
M側からP側へ引く線と
P側からM側へ引く線と，重複して考えてしまっているような。。。


ためしにたくさんの辺が引けそうな状況を考えてみます。

m1, m2を固定して，
p1, p2, ..., p11へ辺を引くと
11＊２＝22個の辺ができます。
この状況でさらにもう一本，辺をどこに付け加えても
☆の条件から外れます。


別の場合として
p1, p2を固定して，
m1, m2, ..., m20へ辺を引くと
20＊２＝40個の辺ができます。
この状況でさらにもう一本，辺をどこに付け加えても
☆の条件から外れます。


なのでとりあえず学生の数は40人までは増やせるはずですが・・・
これが最大であること，これよりもっと増やせないことの証明が思いつきません。

かといって，どうすればさらに増やせるか
という組み合わせ論的なアイデアもちょっと思いつきません。
ごめんなさい。
（自分はコンピュータ屋さんなので，どうしても計算機で数え上げて最大化しようとしてしまいます。）

ここからが思考力を試す本題の部分なんでしょうね。

いい宿題になったので
何ヶ月か，寝てる時にでも考えてみますね。