部屋割りの問題                     戻る

 242名の生徒がすべて4人以下の仲良しグループに分かれているものとする。

 これらのグループを崩さずに、17人まで収容できる部屋のいくつかに割り振りたい。

 仲良しグループの人数構成がどのような形であっても、最低何部屋あればいいだろうか?

ただし、グループ同士の関係は考えないものとする。



































(答) 男の子ではあまりないと思うが、女の子だと、グループが違うとほとんど交流がなく、
   話すこともないらしい。ましてや、同じクラスの男の子なのに、「あの子は誰?」という
   ことも...。それ位、女の子にとってグループは絶対であり、ひとつの不可侵な世界
   なのだ。
    この問題は、そのようなグループ同士をある制約条件のもとにまとめていく問題。

   答えは、「最低 16 部屋用意すれば十分」かな?(←あまり、自信がない...f(^^;)

   グループがすべて単独の1人だと、一つの部屋に17人収容できるので、

      242÷17=14・・・4  から、 15部屋以上は必ず必要である。

   一番能率が悪い入れ方は、グループの人数が4人以下なので、各部屋に3人ずつの
  空きが出る場合である。

   14×17=238 なので、一見、 17+1=18部屋必要であるように思われるが、
  実はそうでもない。

   グループの人数が2人以上について、14人の構成を考えると、

     4442  4433  33332  332222  2222222

  といろいろパターンがあり、グループの入れ替えを行い無駄を省いて、必要とされる部
  屋数も少し減らすことが出来る。

   実は、「各部屋には必ず15人以上収容できる」ということが次のようにして示される。

  各グループの人数が多い順に部屋に収容していくものとする。ある部屋で、14人まで
 しか収容できないとすると、次に入るべきグループの人数は、4人のはず。ところが、こ
 れは、上記の14人のパターンで、人数の多い順に部屋に入れていることに矛盾する。

  したがって、 15の部屋に15人以上入れれば、

       15×15=225   242−25=17

 より、17人以下の残った生徒をもう一つの部屋に入れればよい。

  以上から、必要とされる部屋の最小数は、16 である。

(参考文献: 中本敦浩 著  エレガントな解答をもとむ 
                           数学セミナー’03 9月号 (日本評論社))


 当HPがいつもお世話になっているHN「FN」さんが、上記の問題の一般化を考えられた。
                                      (平成22年6月16日付け)

 n人の生徒がすべて4人以下の仲良しグループに分かれているものとする。これら

のグループを崩さずに、17人まで収容できる部屋のいくつかに割り振りたい。仲良し

グループの人数構成がどのような形であっても、最低何部屋あればいいだろうか?

ただし、グループ同士の関係は考えないものとする。



 n=242の場合とほとんど同じです。そこでされてる議論で尽くされてます。それを一般的
な形に表現するだけです。

 n を15で割ったときの商を q、余りを r とする。即ち、n=15q+r (0≦r<15)

  このとき、   r≧3 ならば、q+1部屋

          r≦2 ならば、q部屋
 (ただし、q=0 のときは1部屋)

 である。このことを、1つの式で書くならば、

  [|n−3|/15]+1部屋  (ただし、[x] は、x を超えない最大の整数)

となる。実際に、

  [|n−3|/15]+1=[|15q+r−3|/15]+1=[|q+(r−3)/15|]+1

において、 3≦r<15 ならば、 0≦(r−3)/15<1 なので、

   [|n−3|/15]+1=q+1

 0≦r≦2 ならば、 −1<(r−3)/15<0 なので、

   [|n−3|/15]+1=(q−1)+1=q

 ここで、 n=1、2 でも成り立つようにするために絶対値がついている。

例 n=242 のとき、 242÷15=16・・・2 なので、公式により、16部屋あればよい。

(証明)

(1) n=15q+r (r≧3) のとき、q個の部屋に入らないこと
  
(入らない場合があるということ)

  3人ずつの5q+1のグループと残りr−3人(r−3人はどんなグループでもよい)のときを

 考える。r−3人は無視して考えて、すべて3人ずつのグループだから、1部屋に15人しか

 入らない。q個の部屋には、15q人しか入らない。従って、q個の部屋には入らない。

(2) n=15q+r (r≦2)のとき、q個の部屋に入ること
  
(どんな場合も必ず入るということ)

  各グループを人数が多い順に並べておいて各部屋に入れる上限まで入れていく。その

 とき最後の部屋は除いて各部屋には必ず15人以上入る。

  実際に、そうでないとすると、ある部屋で14人しか入れないことになるがそのとき次に

 入るべきグループの人数は4人のはず。(そうでないならそのグループはその部屋に入る

 はず) ところが、そうであれば、4人のグループだけで14人になることになり矛盾。

  各部屋には15人以上入るから、15q人は、q個の部屋に入る。残っているのはせいぜ

 い2人で、そしてそのときは15人の部屋があるからそこに残ったせいぜい2人をいれれ

 ばよい。

(コメント) 「各部屋には必ず15人以上収容できる」ということから「15」という数字が重要
      ですね。人数を15で割って余りが2以下なら部屋の数を増やさずに収容できます
      が、余りが3以上だと、収容しきれず、やむなく1部屋増えるという感覚です。

※FNさんからの補足です。

 (1)の r≧3 は15以上も含む。(2)の r≦2 は同様にマイナスも含む。

 そこで、n=15q+r (3≦r<15)のときは、(1)より、q個の部屋には入らない。

   n=15(q+1)−15+r

 として、(2)より、q+1個の部屋に入る。

 n=15q+r (0≦r≦2)のときは、(2)より、q個の部屋に入る。

   n=15(q−1)+15+r

 として、(1)より、q−1個の部屋に入らない。


 さて、次に17人を m人にしよう。mが4以上とするのは当然でしょう。そこで次の問題を
考えてください。

 n、m は自然数で、m は4以上とする。n人の生徒がすべて4人以下の仲良しグル

ープに分かれているものとする。これらのグループを崩さずに、m人まで収容できる

部屋のいくつかに割り振りたい。仲良しグループの人数構成がどのような形であって

も、最低何部屋あればいいだろうか?ただし、グループ同士の関係は考えないものと

する。



 FNさんから続報をいただきました。(平成22年11月17日付け)

 上記は、以前に私が出した問題ですが、答えを用意していたわけではありません。再度考
えてみて、出題したとき考えていただろうことよりは、はっきりしてきました。

 m=17のときの解答は、大雑把に言うと、[n/15]+α (αは、0か1) です。もちろん、ど

ういうときにαが0または1になるかを示す必要がありますが大体の所としては、[n/15]+α

です。(もう少し正確に言えば、大体 [(n−3)/15]+1です。)

 m=16でも、[n/15]+αです。もちろん、αは0か1ですが、m=17のときと全く同じ式と

いうわけではありません。

 m=18では、[n/16]+αです。

 m=16、17のときは、3人のグループが大部分であるときが一番無駄が多く、m=18の

ときは、4人のグループが大部分であるときが一番無駄が多いことからきます。

 m=17のときの式として、 [|n−3|/15]+1 のような不自然な式を書いています。これ

は、n=1、2のようなつまらないケースを気にしたものです。このようなケースを気にしないた

めに、n≧m≧4 としておきましょう。



   以下工事中