平野塾@吉祥寺

敵は3人ずつ，友人の敵は敵（2017 香港TST）

数オリ

問題概略
実験前の準備
小さな n で実験

問題概略

$n$ 人の委員からなる委員会がある。どの 2 人の委員も友好関係または敵対関係にあり，どの委員もちょうど 3 人ずつと敵対関係にある。また，友人の敵は敵である。 $n$ として考えられる値をすべて求めよ。
https://artofproblemsolving.com/community/c6h1294021p6857837

解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。

drive.google.com

実験前の準備

2017 年の香港の Team Selection Test の問題です。

人を点（ $\circ$ ），敵対関係を実線，友好関係を破線であらわすことにします。

「友人の敵は敵」がわかりにくいので，3人の場合で実験してみます。
人間関係は $2^3=8$ 通り考えられますが，「友人の敵は敵」ルールをみたすのは 5 通りだけです。
実線が 1 本の三角形は存在しません。

f:id:variee:20211112200640p:plain

次に辺の数を数えます。
敵対関係をあらわす実線は各委員から 3 本ずつ出ています。ダブルカウントを考えて，全部で $\frac{3n}{2}$ 本。
$n$ は偶数です。

小さな n で実験

$n=4$ のときはすべて実線（敵対関係）です。

f:id:variee:20211112200652p:plain

$n=6$ のときもうまくいきます。

f:id:variee:20211112200706p:plain

$n=8$ のときはうまくいきません。
「実線が 1 本の三角形は存在しない」ルールにより図の A, B, C から 4 本以上の実線が出てしまうからです。下図では例として C からの実線のみ書いてあります。

f:id:variee:20211112200719p:plain

これを一般化すると $n\geqq 8$ はすべて不適であることが証明できます。

各委員を $\mathrm{P_1}$ ～ $\mathrm{P}_{n}$ であらわし， $\mathrm{P_1}$ が $\mathrm{P_2}$ , $\mathrm{P_3}$ , $\mathrm{P_4}$ と敵対関係にあるとします。

$\mathrm{P_5}$ 〜 $\mathrm{P}_{n}$ の $n-4$ 人は $\mathrm{P_1}$ と友好関係にあるので， $\mathrm{P_1}$ の敵 $\mathrm{P_2}$ と敵対しています。

$\mathrm{P_2}$ から見ると $\mathrm{P_1}$ に加えて $\mathrm{P_5}$ 〜 $\mathrm{P}_{n}$ の計 $n-3$ 人は敵です。

$\mathrm{P_2}$ の敵は 3 人ですから

$n-3\leqq 3\Leftrightarrow n\leqq 6$

これは $n\geqq 8$ と矛盾します。結局，求める人数は 4 人か 6 人です。

variee.hatenablog.com