seegeのまとめサイト

もっと早く教えてくれよって思った内容を書いていきたいと思います。

【今週のお題】パッキング問題について

今週のお題「2024年にやりたいこと」

パッキングとは?

パッキングという分野について興味が出てきた。

ある決まった形状の物を、限られた空間に効率よく詰めていくのがパッキング。

きっかけは、以下の問題。

【出典】小遣い「1年目は5000円で年1000円ずつ増」「半年で2500円、半年ごと250円増」どっちが得か…答えに大人も愕然 2cm×100.5cmの長方形の箱に直径1cmの乾電池が201本入る謎 | PRESIDENT Online(プレジデントオンライン)

普通に考えれば、100.5㎝÷1㎝ ≒ 100(小数点以下切り捨て)

これが2行作れるので、100×2=200 になるので、200本と答えたくなる。

しかし、だったら、なぜ、100㎝にしなかったのだろうか?

100.5が、この問題のポイントであるのは間違いない。

配置パターン?

普通は下図のように四角形の中に円を配置していこうとする

しかし、これだと隙間(黄色部分)が多くなってしまう。

これを下図のように三角形の中に配置していくと両サイドの隙間は大きくなるがその他での隙間は明らかに小さくなる。

実際に四角に配置するパターンと、三角に配置するパターンで比較してみると、下図のようなイメージになる。

三角で配置した場合、0.5㎝長くすると200個目で0.5個配置できる隙間ができる。

このため、100㎝だと収まらないが、0.5㎝長く100.5cmにすることで201個目が入る隙間ができる。


四角のパターンでは、どれだけ配置していっても無駄に隙間だけが増えていくが、三角のパターンで配置していけば、配置すればするほど、端の隙間は増えていく。

一見すると、四角で配置した方が効率が良さそうだが、実際は違った。

限られた空間に効率よく詰めるという作業を、これまで自分は数学的なアプローチではなく、直感的に行ってきたので、パッキング問題の考え方は自分にとっては凄く新鮮だった。

ざっと、調べた感じだと情報量が多い分野ではなさそうなので、最初は苦労するかもしれないが、今年は、是非、パッキング問題に関わってみたいと思う。