ホーム >> 組合せ >> $5$ つの島と橋と船
hide or visible

問題の説明

たとえば,$5$ つの島の関係が下の図のようになっていたとしましょう.船で行き来できる箇所が $4$ つあり,橋がかかっている箇所が $6$ つあります.

この場合は橋を使えば,どの島から別の島へもたどりつけることがわかります.(この場合は船では不可能です)また,たとえば $5$ つの島の関係が下の図のようになっていたとします.
この場合は,船のみでも,橋のみでもどの島から別のどの島へもたどりつくことができます.

このように,$5$ つの島がどんな関係であったとしても,橋または船のどちらか一方のみを用いて,どの島から別のどの島へもたどりつけることを示すのが問題です.

ヒント・考え方

簡単のため,島を◯で表し,$2$ つの島に橋がかかっていることを赤い辺で表し,$2$ つの島を船で行き来できることを青い辺で表すことにしましょう.

すると,問題は,『$5$ つの◯について,どの $2$ つの◯もまたはの辺のいずれかで結ばれているとき,赤い辺または青い辺のどちらか一方のみを用いて,どの◯から別の◯へもたどりつけることを示せ』というように変換されます.

たとえば,島の数が $3$ つだとすると,題意の主張が成り立つことは簡単に確認できます.実際,ありうる状態は以下の図ですべてなので,いずれの場合も主張が成り立つことがわかります.

では島の数が $4$ つや $5$ つの場合はどうでしょうか,いきなり $5$ つの場合を考えるのが難しければ,まずは島の数が $4$ つの場合を考えてみてください.

解答例

より一般に,島の数が $n$ 個 ($n\ge 2$) であるとき,題意が成り立つことを数学的帰納法で示します.
まず,$n=2$ のとき,$2$ つの島は橋で結ばれているか,船で行き来できるかなので,いずれにせよ題意は成り立ちます.

$n=k$ のとき,題意が成り立つと仮定して,$n=k+1$ のときに題意が成り立つことを示します.$k+1$ 個の島に $1,2,...,k+1$ の番号をつけます.いま,仮定より,$1,2,...,k$ 番の島は橋または船のどちらか一方のみを用いて,どの島から別のどの島へもたどりつけます.たとえば橋のみでどの島から別のどの島へもたどりつけるとしましょう.以下,$2$ 通りの場合分けを行います.

($i$) $k+1$ 番目の島から,$1,2,...,k$ 番の島へすべて船で行き来できるとき
このときは条件から,($k+1$ 番の島を経由すれば) すべての島を船のみで行き来できます.

($ii$) $k+1$ 番目の島から,$1,2,...,k$ 番の中のある島に橋がかかっているとき
この場合は,$1,2,...,k$ 番の島々は仮定より橋で行き来でき,さらに条件より $k+1$ 番の島と $1,2,...,k$ 番の中のある島も橋で行き来できるので,結局, $1,2,...,k+1$ の島はすべて橋のみで行き来できます.

$1,2,...,k$ 番の島が船のみで行き来できる場合も同様にして示せます.
以上より,$n=k+1$ のときも題意が成り立ちます.


帰納法を用いなくても島の数が $5$ つの場合ならばがんばって場合分けなどすれば解けるかと思います.