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


http://www.artofproblemsolving.com/community/c6h487007p2728815

Each student chooses 1 math problem and 1 physics problem among 20 math problems and 11 physics problems.

No same pair of problem is selected by two students.

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

At most how many students are there?

第3文は「最大2人に選ばれた問題が少なくとも1問ある」だと思うのですが,どうやら違うらしいのです。上記サイトの解答例では学生を数学と物理の2部グラフの辺ととらえ,次のように述べています。

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.

次数3が出てくる理由がわかりません。また,この後に続く解答によると
((数学の問題数)+(物理の問題数)-4) x 2
が答えなのだそうです。これが正しいとすると,たとえば数学,物理とも2問だった場合,m1-p1, m1-p2, m2-p1, m2-p2と結ぶ「4人」は不可となります。

なぜこうなるんでしょうか? 正しい解釈は?

回答の条件
  • 1人1回まで
  • 13歳以上
  • 登録:2015/09/03 23:46:46
  • 終了:2015/09/10 23:50:03

ベストアンサー

id:language_and_engineering No.1

lang_and_engine回答回数170ベストアンサー獲得回数632015/09/04 09:13:04

ポイント100pt

面白い問題ですね。


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

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


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

もしも辺の片方で次数が1または2でない場合,
つまり3以上である場合は,
辺のもう片方の次数が1または2である必要があります。

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

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


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

>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部グラフ上で解釈しなおすと,辺の1つの頂点の次数が3以上であれば,その辺のもう片方の頂点の次数は最大2である。」・・・(☆)

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


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

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


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


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

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


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


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

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

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

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

id:variee

回答ありがとうございます。おかげさまで本文の訳がわかりました。at leastはそこにかかるのか……

2015/09/04 09:23:13
id:language_and_engineering

もし解けたらぜひ,ここで教えてくださると嬉しいです!

2015/09/04 10:49:00

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません