◆東京都 T.Kobayashi さんからの解答。
結論を書けば、16[箱] が必要かつ十分。
まず、390/64=6.09375[g] の袋を 64[袋] 用意した場合、各箱には 4[袋] までしか入らないから、16[箱] は必要である。
さて、7[g]*4[袋]=28[g]＜30[g] だから、袋の数が 64 以下ならば、16[箱] に収めることができる。
袋の数が 65 以上のときは、袋の中で大きいものから 64[袋] 選んできて、4[袋] ずつ16[箱] に収める。
そして残った袋を箱の隙間に詰めていく。
このとき全て詰めることができればそれでよい。
そうでないときは、余った袋は全て、どの箱の隙間よりも大きいから、
箱の隙間の最大値を M[g] として、余った袋を a1, ..., an[g] とすれば、
Min{a1, ..., an}＞M である。
さて、隙間の最大値が M[g] ということは、
各箱に入っている袋の総重量の最小値は 30-M[g] である。
16[箱] 全てを考えれば、箱に収まっている袋の総重量は
480-16M[g] 以上である。
ところで、実際に箱に入っている袋の総重量は、
390-(a1+...+an)[g] である。
したがって、
390-(a1+...+an)≧480-16M ⇔16M-(a1+...+an)≧90
| となり、Min{a1, ..., an}＞M より、M＞ | 90 16-n | となる。 |
ここで n≧1 だから、M＞6 である。
最初の 64[袋] は大きいものから選んできたのだから、
390≧(64+1)Min{a1, ..., an}＞65M＞390
となり、これは矛盾である。
すなわち、16[箱] で足りないことはありえない。