|
あきさんが住む A 町から TORA さんが住む B 町へ行く道が 2 本，B 町からマサルさんが住む C 町へ行く道が 3 本，C 町から Yuh! さんが住む D 町へ行く道が 4 本あります。
A 町から D 町まで数人の人が歩きました。どの道も少なくとも一人は通りました。また，どの 2 人についても，少なくとも 1 本は同じ道を通りましたが，A 町から D 町までの経路がまったく同じであることはありませんでした。
このとき，何人の人が歩いたのでしょうか。考えられうる人数をすべて答えてください。
注意: 途中でもどったりはしません。必ず，A-B-C-D の順に通過します。
|
| ▼ 解説 |
|
AB 間の道を a1，a2，BC 間の道を b1，b2，b3，CD 間の道を c1，c2，c3，c4 と表すと，A から D への経路は次の 24 通りで，A-1〜B-3 の 6 グループに分ける。
A-1: (a1，b1，c1)，(a1，b1，c2)，(a1，b1，c3)，(a1，b1，c4)
A-2: (a1，b2，c1)，(a1，b2，c2)，(a1，b2，c3)，(a1，b2，c4)
A-3: (a1，b3，c1)，(a1，b3，c2)，(a1，b3，c3)，(a1，b3，c4)
B-1: (a2，b1，c1)，(a2，b1，c2)，(a2，b1，c3)，(a2，b1，c4)
B-2: (a2，b2，c1)，(a2，b2，c2)，(a2，b2，c3)，(a2，b2，c4)
B-3: (a2，b3，c1)，(a2，b3，c2)，(a2，b3，c3)，(a2，b3，c4)
まず，「B-2，B-3 に属するどの経路も，A-1 に属する 2 本以上の経路と同じ道を共有しない」ことがわかる。このことは，A-1，A-2 と B-3 のように，番号を重ならないようにして，また，A と B を入れ替えても成り立つ。
(1) A-1 に属する経路が 2 本以上存在すると仮定すると，上記「 」により，B-2，B-3 に属する経路は存在せず，B-1 に属する経路が存在することになる。
さらに，B-1 に属する経路が 2 本以上存在すると，A-2，A-3 に属する経路は存在しない，すなわち，(x，b2，y)，(x，b3，y) のタイプの経路が存在しないことになり，題意に反する。よって，B-1 に属する経路は 1 本だけ存在することになる。
それを (a2，b1，c1) とすると，(a1，b1，c1)，(a1，b1，c2)，(a1，b1，c3)，(a1，b1，c4)，(a1，b2，c1)，(a1，b3，c1)，(a2，b1，c1) の 7 本が存在することになる。このうち，(a1，b1，c1) はあってもなくてもよいが，それ以外の経路は不可欠である。
以上の考察は，どのグループで 2 本以上の経路の存在を仮定しても同様。
(2) どのグループに属する経路も高々 1 本しか存在しないと仮定する。
例えば，(a1，b1，c1) が存在すると仮定すると，c2，c3，c4 を通る経路で可能なのは
A-2: (a1，b2，c2)，(a1，b2，c3)，(a1，b2，c4)
A-3: (a1，b3，c2)，(a1，b3，c3)，(a1，b3，c4)
B-1: (a2，b1，c2)，(a2，b1，c3)，(a2，b1，c4)
であるが，(a2，b1，c2) が存在するとすれば，c4 を含む経路が存在しない，というように，c2，c3，c4 をふくむ経路のうち，存在しないものがある。
したがって，題意を満たすのは (1) の場合で，6 人または 7 人である。
|
|
|
|
