第184問の解答


1.問題 [推理]

9階建てマンションに次のような条件を満たすように、エレベータを設置します。
  • 乗り降りできるフロアは、エレベータ1基につき最大6フロアまで
  • 1階最上階は、必ず乗り降りできるようにする
  • どの階からどの階も乗り換えなしで移動できる

このとき、最低でも何基エレベーターが必要となるでしょう?


2.解答例1(杉本未来さん、sodoさん、清川育男さん、長野美光さん、kuri有無相生さん、中村明海さん、他)

どのエレベーター1階9階は必ず停止するので、2階〜8階までを考えれば良い。このとき、簡単にするため、2階〜8階1階〜7階と呼ぶことにします。

参考図1

上図、ケース1、2のように5基あれば条件を満たすことが可能となります。

4基以下では次に示すように無理となるので、最低でも5基必要となることが分かります。

(3基以下では無理なこと)
1階〜7階の、任意の2フロアを選ぶ組み合わせは=21通り
1基あたり停止できるのは4フロア以下なので、直接行き来できる2フロアの組み合わせは=6通り以下。
従って、3基以下では6×3=18通り以下となり、全ての組み合わせ21通りを満たすことができない。

(4基では無理なこと)
まず、4フロア停止するエレベーターを1基考えます。
このとき、このエレベーターが停止するフロアAグループ、残りをBグループと呼ぶことにします。便宜上、Aグループ1、2、3、4階Bグループ5、6、7階と仮定しても一般性を失いません。

Aグループに属するあるフロアからBグループに属するあるフロアにいくことができる組み合わせは、それぞれ2フロアずつ停止する場合の2×2=4通り1フロア3フロアの組み合わせでは1×3=3通り

このような組み合わせは、Aグループ4フロアBグループには3フロアあるので、4×3=12通り。よって、残り3基でこの12通りを実現するためには、3基とも各グループ2フロアずつ停止する必要があります。

このとき、Aグループの各フロアは、1基につきBグループ2フロアしか行き来できないので、少なくとも2基エレベータが停止する必要があります。
Aグループ4フロアありますから、延べ4×2=8フロア以上停止することになりますが、残り3基ともAグループには2フロア停止するので、延べ2×3フロアとなり矛盾します。

参考図2

よって、4基では条件を満たすことができません。

 

(4基では無理なことの別証明)
4基
では延べ6×4=24通りフロア間の行き来が可能。
全部で21通り行き来できる必要があるので、重複できる組み合わせは最大24−21=3通り

1基しか停止しないフロアがあれば、そこから全てのフロアへ行き来することは不可能なので、どのフロアとも2基以上エレベーターが停止します。

また、どのフロア3基以上エレベーターが停止すると、延べ7×3=21フロア停止することになりますが、1基あたり4フロア以下なので延べ4×4=16フロアしか停止できないので矛盾。

以上から、ちょうど2基エレベーターが停止するフロアがあります。
例えば1、2、3、4階および1、5、6、7階に停止するものとします。
この2基合計6×2=12通りのフロア間の行き来が可能となるので、残りは21−12=9通りです。

参考図3

また、Aグループ内、Bグループ内はこの2基で行き来可能なので、残りは全てAグループ、Bグループ間2フロアの行き来となります。

1基のエレベーターが同一グループ2フロアに停止すれば、そのフロア間は既に行き来可能となった組み合わせ、3フロアに停止すればその3フロア間の合計3通りは既に行き来可能となった組み合わせとなります。

従って、(A、B)=(2、2)では2通りが重複、(1、3)または(3、1)では3通りが重複した組み合わせので、2基のエレベーターでは最低でも2+2=4通りが重複するので、重複可能な3通りを超えます。

よって、4基では不適となります。

 

答:5基

以上