文献あり

「数学オリンピックチャンピオンの美しい解き方」に出てくる、その他のさまざまな例の練習問題その1

問題

練習問題6.1

6人の演奏家がある音楽祭に集まった。おのおのの演奏会で、何人かの演奏家はその演奏会で演奏したが、その間他の演奏家は聴衆の一部として聴いた。おのおのの演奏家が聴衆の一部として他の全ての演奏家の演奏を聴く為に、予定に組み込まなければならない演奏会の最少数はどれだけか？

解答

初めに

「聴かなくてもよいので自分に関係ない演奏会があるとして、そのような演奏会をカウントするのか？」
この問いは、考えていくと
自分が演奏するか、必ず避けられない、演奏を聴く演奏会か、のどちらかであることが分かる。

どうやって解くか？

テレンス・タオさんの仰る通りで、一般解を求め、解が正しいことを証明しようとするより、全ての場合を尽くす方が無難だ。

解法

総当たり。変換の成り行きで漢数字を使っている。

一人が演奏すると

6回。

二人なら

ab cd ef
cd cd
ab ab
ef ef
これで

$a\longleftrightarrow b$
$b\longleftrightarrow a$

のような感じで1つの記号に1つの不足がある状態になる。
bdfが演奏し、
aceが演奏すれば条件を満たす。

三人なら

abc def
def abc
bc ef
これで
$b\longleftrightarrow cda$
$c\longleftrightarrow bda$
$a\longleftrightarrow d$
$d\longleftrightarrow a$
$e\longleftrightarrow fda$
$f\longleftrightarrow eda$
となり、
cafが演奏し、bdeが演奏すれば条件を満たす。

四人なら

a b c d e f
cdef
abef
abcd
これで
$a\longleftrightarrow b$
$b\longleftrightarrow a$
$c\longleftrightarrow d$
$d\longleftrightarrow c$
$e\longleftrightarrow f$
$f\longleftrightarrow e$
となり、
bdfが演奏し、aceが演奏すれば条件を満たす。