問題概略
人の委員からなる委員会がある。どの 2 人の委員も友好関係または敵対関係にあり,どの委員もちょうど 3 人ずつと敵対関係にある。また,友人の敵は敵である。 として考えられる値をすべて求めよ。
https://artofproblemsolving.com/community/c6h1294021p6857837
解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。
実験前の準備
2017 年の香港の Team Selection Test の問題です。
人を点(),敵対関係を実線,友好関係を破線であらわすことにします。
「友人の敵は敵」がわかりにくいので,3人の場合で実験してみます。
人間関係は 通り考えられますが,「友人の敵は敵」ルールをみたすのは 5 通りだけです。
実線が 1 本の三角形は存在しません。
次に辺の数を数えます。
敵対関係をあらわす実線は各委員から 3 本ずつ出ています。ダブルカウントを考えて,全部で 本。
は偶数です。
小さな n で実験
のときはすべて実線(敵対関係)です。
のときもうまくいきます。
のときはうまくいきません。
「実線が 1 本の三角形は存在しない」ルールにより図の A, B, C から 4 本以上の実線が出てしまうからです。下図では例として C からの実線のみ書いてあります。
これを一般化すると はすべて不適であることが証明できます。
各委員を ~ であらわし, が , , と敵対関係にあるとします。
〜 の 人は と友好関係にあるので, の敵 と敵対しています。
から見ると に加えて 〜 の計 人は敵です。
の敵は 3 人ですから
これは と矛盾します。結局,求める人数は 4 人か 6 人です。