９階建てのマンションに次のような条件を満たすように、エレベータを設置します。
このとき、最低でも何基のエレベーターが必要となるでしょう？ |
２．解答例１(杉本未来さん、sodoさん、清川育男さん、長野美光さん、kuri、有無相生さん、中村明海さん、他)
どのエレベーターも１階と９階は必ず停止するので、２階〜８階までを考えれば良い。このとき、簡単にするため、２階〜８階を１階〜７階と呼ぶことにします。
上図、ケース１、２のように５基あれば条件を満たすことが可能となります。
４基以下では次に示すように無理となるので、最低でも５基必要となることが分かります。
（３基以下では無理なこと）
１階〜７階の、任意の２フロアを選ぶ組み合わせは７Ｃ２＝２１通り。
１基あたり停止できるのは４フロア以下なので、直接行き来できる２フロアの組み合わせは４Ｃ２＝６通り以下。
従って、３基以下では６×３＝１８通り以下となり、全ての組み合わせ２１通りを満たすことができない。（４基では無理なこと）
まず、４フロア停止するエレベーターを１基考えます。
このとき、このエレベーターが停止するフロアをＡグループ、残りをＢグループと呼ぶことにします。便宜上、Ａグループは１、２、３、４階、Ｂグループは５、６、７階と仮定しても一般性を失いません。Ａグループに属するあるフロアからＢグループに属するあるフロアにいくことができる組み合わせは、それぞれ２フロアずつ停止する場合の２×２＝４通り（１フロアと３フロアの組み合わせでは１×３＝３通り）。
このような組み合わせは、Ａグループに４フロア、Ｂグループには３フロアあるので、４×３＝１２通り。よって、残り３基でこの１２通りを実現するためには、３基とも各グループ２フロアずつ停止する必要があります。
このとき、Ａグループの各フロアは、１基につきＢグループの２フロアしか行き来できないので、少なくとも２基のエレベータが停止する必要があります。
Ａグループは４フロアありますから、延べ４×２＝８フロア以上停止することになりますが、残り３基ともＡグループには２フロア停止するので、延べ２×３フロアとなり矛盾します。
よって、４基では条件を満たすことができません。
（４基では無理なことの別証明）
４基では延べ６×４＝２４通りのフロア間の行き来が可能。
全部で２１通り行き来できる必要があるので、重複できる組み合わせは最大２４−２１＝３通り。１基しか停止しないフロアがあれば、そこから全てのフロアへ行き来することは不可能なので、どのフロアとも２基以上のエレベーターが停止します。
また、どのフロアも３基以上のエレベーターが停止すると、延べ７×３＝２１フロア停止することになりますが、１基あたり４フロア以下なので延べ４×４＝１６フロアしか停止できないので矛盾。
以上から、ちょうど２基のエレベーターが停止するフロアがあります。
例えば１、２、３、４階および１、５、６、７階に停止するものとします。
この２基で合計６×２＝１２通りのフロア間の行き来が可能となるので、残りは２１−１２＝９通りです。
また、Ａグループ内、Ｂグループ内はこの２基で行き来可能なので、残りは全てＡグループ、Ｂグループ間の２フロアの行き来となります。
１基のエレベーターが同一グループの２フロアに停止すれば、そのフロア間は既に行き来可能となった組み合わせ、３フロアに停止すればその３フロア間の合計３通りは既に行き来可能となった組み合わせとなります。
従って、（Ａ、Ｂ）＝（２、２）では２通りが重複、（１、３）または（３、１）では３通りが重複した組み合わせので、２基のエレベーターでは最低でも２＋２＝４通りが重複するので、重複可能な３通りを超えます。
よって、４基では不適となります。
答：５基
以上
