◆ 6. キューダ さん

重さが異なる 5 つのおもり A，B，C，D，E と，天びんがありました。 A 君は B 君に向かって， 「君なら何回天びんを使って，おもりを重い順に並べかえられる?」 と聞きました。B 君は少し考え， 「うーん，… 8 回かな」 と答えました。それに対し，A 君は 「7 回あれば，十分なんだよ」 と答え，おもりを天びんにのせ始めました。 最初の 3 回は次のような操作をし，次のような結果を得ました。 1 回目　A と B を比べ　A＞B (A の方が B よりも重い)　が判明 2 回目　C と D を比べ　C＞D　が判明 3 回目　A と C を比べ　A＞C　か判明 以下同様にして，おもりを 1 つずつ比較する操作を (確実に 7 回以内で終わるように) 繰り返しましたが，なんと 6 回目の比較が終わったとき，A 君は 「運が良かったこともあるけど，6 回で終わっちゃった」 と言って，重い順番に並べかえました。 さて，A 君の出した結論は何でしょうか。可能性があるものをすべて答えてください。 (天秤使いの妙技)

▼ 解説 5 個のおもりの並び順は 5!＝120 通り。また，27＝128 よって，5!＜27 が成り立つため，「うまく」天びんを使えば 7 回で可能となるのである。 しかし，120 と 128 はとても近い値であるため，「常に」無駄な比較を行わないことが要求される。その結果，比較する手順がかなり限定されることになる。 最初は 120 通りの可能性があり，これを 1 回目の比較で 60 通りに減らし，以下，30 通り，15 通りと減らしていく。ところが，4 回目に 15 通りが 9 通りか 6 通りに絞られるような比較を行ってしまうと，「確実に 7 回以内で終わる」という条件を満たせなくなるので失敗となる。なぜなら，もし 9 通りに絞られてしまうと，9＞23 なので，残り 3 回の比較では確定できなくなるからである。したがって，4 回目は 15 通りが 8 通り以内，すなわち，8 通りか 7 通りへ絞られるような比較を行わなければならない。そして，4 回目以降の比較による解の候補数の変移は，以下の 4 パターンが考えられる。 15 通り → 8 通り → 4 通り → 2 通り → 確定 15 通り → 7 通り → 4 通り → 2 通り → 確定 15 通り → 7 通り → 3 通り → 2 通り → 確定 15 通り → 7 通り → 3 通り → 確定 この問題では 6 回の比較で確定したということから， 15 通り → 7 通り → 3 通り → 確定 というパターンに限られる。 さて，最初の 3 回の比較の結果，可能性がある順番 (重い順) は以下の 15 通り。 ABCDE　　ABCED　　ABECD ACBDE　　ACBED　　ACDBE ACDEB　　ACEBD　　ACEDB AEBCD　　AECBD　　AECDB EABCD　　EACBD　　EACDB 4 回目に比較する必要がある組合せは以下の 6 組。 (A，E)，(B，C)，(B，D)，(B，E)，(C，E)，(D，E) (1 回目と 3 回目の結果から，A＞D は明らか。) この 6 組の比較のうち，上記 15 通りの場合を 8 通りまたは 7 通りに絞ることができるのは (C，E) の比較に限られ，7 通りになるのは E＞C となる以下の場合である。 ABECD AEBCD　　AECBD　　AECDB EABCD　　EACBD　　EACDB 5 回目に比較する必要がある組合せは以下の 4 組。 (A，E)，(B，C)，(B，D)，(B，E) (他の組合せの大小はすでに確定) この 4 組の比較のうち，上記 7 通りの場合を 4 通りまたは 3 通りに絞ることができるのは (A，E) と (B，C) の比較で，3 通りになるのはそれぞれ E＞A，B＞C となる以下の場合である。 E＞A のとき　　EABCD　　EACBD　　EACDB B＞C のとき　　ABECD　　AEBCD　　EABCD よって，6 回目の比較で確定するのは 5 回目 E＞A の場合: 6 回目 B＞C のとき EABCD，　D＞B のとき EACDB 5 回目 B＞C の場合: 6 回目 E＞A のとき EABCD，　B＞E のとき ABECD したがって，答えは ABECD，EABCD，EACDB の 3 通り。