読者です 読者をやめる 読者になる 読者になる

数学塾variée@吉祥寺

数学塾の中の人の日記

敵は3人ずつ(2017 香港TST)

数学/数オリ 解いてみた

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

2017年(?)の香港のTSTの問題です。

見るからにグラフ理論の問題です。人を◯,敵対関係を実線,友好関係を破線であらわしてグラフを描きつつ考えました。

「友人の敵は敵」がわかりにくいので,実験が必要でしょう。ここで「実線が1本の三角形は存在しない」をつかんでおくと,実例を作るときに楽です。グラフ理論の知識なしで解ける問題でした。

f:id:variee:20161005142548p:plain

くわしいことはpdfを見てください。

解いてみた035.pdf - Google ドライブ