『６人の村人』

『６人の村人』解答

◆広島県　清川　育男さんからの解答。

　ヒントをもとに考えました。

視覚的にとらえた方が理解しやすいので、六角形の頂点に反時計回りに、A,B,C,D,E,F、６人の村人を配置して考えます。
そこで、出来るだけ仲良しの組が多くなるようにする。

仲良しの関係にある２人は青線、絶交関係にある２人は赤線で結ぶ。

図前者の関係を(A,B)=(B,A)=(+)、
後者の関係を(A,B)=(B,A)=(-)とする。

６人から３人をとる組み合わせは、6Ｃ3＝２０。
６人から２人をとる組み合わせは、6Ｃ2＝１５。

1)(A,B,C) (A,B)=(+),(B,C)=(+)とすると(A,C)=(-)。

2)(B,C,D) (B,C)=(+),(C,D)=(+)とすると(B,D)=(-)。

3)(C,D,E) (C,D)=(+),(D,E)=(+)とすると(C,E)=(-)。

4)(D,E,F) (D,E)=(+),(E,F)=(+)とすると(D,F)=(-)。

5)(E,F,A) (E,F)=(+),(F,A)=(+)とすると(E,A)=(-)。

6)(F,A,B) (F,A)=(+)とすると
1)から(A,B)=(+)であるから(F,B)=(-)となる。

1),3),5)から(A,C)=(-),(C,E)=(-),(E,A)=(-)であるから
7)(A,C,E)は３人とも絶交関係にある。

2),4),6)から(B,D)=(-),(D,F)=(-),(F,B)=(-)であるから
8)(B,D,F)は３人とも絶交関係にある。

9)(A,B,D) (A,B)=(+),(B,D)=(-)であるから(A,D)=(+)となる。

10)(A,B,E) (A,B)=(+),(E,A)=(-)であるから(B,E)=(+)となる。

11)(A,C,D) (A,C)=(-),(C,D)=(+),(A,D)=(+)。

12)(A,C,F) (A,C)=(-),(F,A)=(+)であるから(C,F)=(+)となる。

13)(A,D,E) (A,D)=(+),(D,E)=(+),(E,A)=(-)。

14)(A,D,F) (A,D)=(+),(D,F)=(-),(F,A)=(+)。

15)(B,C,E) (B,C)=(+),(B,E)=(+),(C,E)=(-)。

16)(B,C,F) (B,C)=(+),(C,F)=(+),(F,B)=(-)。

17)(B,D,E) (B,D)=(-),(D,E)=(+),(B,E)=(+)。

18)(B,E,F) (B,E)=(+),(E,F)=(+),(F,B)=(-)。

19)(C,D,F) (C,D)=(+),(D,F)=(-),(C,F)=(+)。

20)(C,E,F) (C,E)=(-),(E,F)=(+),(C,F)=(+)。

以上のように仲良しの組が最大９組あっても、少なくとも２組の絶交関係にある３人がいることになる。
仲良しのペア９組。絶交のペア６組。

７人の村人の場合。

同様に七角形の頂点にA,B,C,D,E,F,Gの村人を配置して考える。

仲良しのペア１０組。絶交のペア１１組。絶交関係にある３人は少なくとも４組ある。

【コメント】

人数が８人の場合は、少なくとも８組、
人数が９人の場合は、少なくとも１３組が絶交状態になります。

一般的な求め方を考えても、面白いかも知れませんね。

◆広島県　清川　育男さんからの解答。

　数列サイトで調べてみました。

0,0,0,0,0,2,4,8,13,20,28,39,52,.........

一般式は、

［(ｎ−１)(ｎ−２)(ｎ−３)
２５		］
となっていました。

［　］はガウスの記号。

【コメント】

非常に面白い数列ですね。
私の能力では見つけるのは無理ですから、とても問題にはできませんね。

◆大阪府　yosit さんからのコメント。

清川さんの解答はこれでよいのでしょうか？
６点を，長さ３のループが生じないように線でむすぶときの，『極大な場合』（それ以上むすぶと長さ３のループが生じる場合） すべてについてたしかめる必要があるのではないでしょうか？

『極大な場合』は以下の５通りで，いずれも，たがいにむすばれていない３つ組が２組以上あることがたしかめられます．

　『６人の村人』へ

　数学の部屋へもどる