フルーツをM個ずつ詰めたパッケージをN個作りたい。その時に何種類のフルーツを用意すればよいのだろう?

ただし、フルーツ詰め合わせは次の条件を満たしている必要がある。

• 1つのパッケージに同じフルーツは入れない
• パッケージ同士で同じフルーツが2つ以上重複してはいけない

例えばM=3,N=4で詰め合わせを作成する場合は下図のパターンが最小値となり、解は6種類となる。

解を求めるステップは次の2つに場合分けすることで求めることができます。

M >= N の場合

M >= N パッケージ数N個よりフルーツM個の方が多い場合は1つ目のパッケージにm種類、2つ目のパッケージに直前で利用したフルーツの種類のうち1種類を再利用してm-1種類、次はm-2種類という具合に増やせるのでその種類の解は等差数列の和で求められるます。

初項がa,公差がd,項数がnであるような等差数列の和は次のように表せる。

$S = 1/2n(2a + (n - 1)d)$

詳しくは 等差数列の和の公式の例題と証明など を参考に

M < N の場合

次にM < Nの場合を考えてみます。まず、 m + 1 = nのとき、以下のように１つのフルーツを最大2回利用することを考えてみます。たとえば、m=6、n=7のときに「１」を2回利用すると1行目に「1, 2, 3, 4, 5, 6」と2行目に「1, 7, 8, 9, 10, 11」という2つのパッケージができます。そして、残りの5個のパッケージに対して、ここで利用した2 ~ 11の10種類を利用します。残りの 4x5個も同様にm+1=nの長方形となるので、再帰的に探索可能になります。

ただし、この方法で得られた種類数が最小値とは言えません。最小値を求めるには同じフルーツが利用されている個数に注目し、条件を満たした上で均等にフルーツを配布することをめざします。

このときの求めるパターン数は「利用されている数」の逆数の和になります。

$(1/3 + 1/3 + 1/1) + (1/3 + 1/2 + 1/2) + (1/3 + 1/2 + 1/2) + (1/3 + 1/2 + 1/2) + (1/3 + 1/2 + 1/2) = 7$

この2つの方法で求めた解が一致するときに最小値の種類といえます。