問題6828(IMO short list 1997)
ある小人の部落では複雑なつつきあいが観察される. このつつきあいでは, X が Y をつつき, Y が Z をつつくからと言って, X がZ をつつくとは限らない.
しかし, つつきあいは以下の単純な規則を満たしている.
(a) どの2人の小人 X, Y についても, X が Y をつつくか, Y が X をつつくかのいずれかである.
(b) どの2人の小人 X, Y についても, X と Y 両方をつつく小人 Z が丁度1人いる.
(c) どの2人の小人 X, Y についても, X と Y につつかれる小人 W が丁度1人いる.
この部落には何人の小人がいるか?
解答
・わたしの…
試行錯誤で…^^;
外部に6点内部に1点の計7点なら可能そう…^^;…?
・鍵コメT様のもの Orz〜
以下のようにしました.
Xをつつく小人をXの親分,Xにつつかれる小人をXの子分と呼ぶことにする. また,Xが親分をa人,子分をb人もつとき,Xの点数をb-aとする.
ある2人の小人A,Bの点数の合計は, 共通の親分(1人だけ)について-2,共通の子分(1人だけ)について+2, AB相互で,+1-1=0,それ以外の相手について0なので, どの2人も,点数の合計は0. よって,点数は全員0に限る. したがって,各小人はn人の親分とn人の子分をもち,小人の総数は2n+1人.
各小人はnC2通りの2人組に対して,共通の親分となる. のべ(2n+1)C2人の共通の親分がいるから, (2n+1)C2=(2n+1)*nC2,すなわち(2n+1)n=(2n+1)n(n-1)/2. これより,n=3となって,人数は7に限る.
実際,例えば *ABCDEFG A0++-+-- B-0++-+- C--0++-+ D+--0++- E-+--0++ F+-+--0+ G++-+--0 (X行Y列が,+のときXはYの親分,-のときXはYの子分) が条件を満たす.
*熟読玩味ぃ〜^^;v
|