PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 106 / 特殊和集合:メタ検査

大きさ n の集合 A の要素の和を S(A) で表す。空でなく共通要素を持たないいかなる 2 つの部分集合 B と C に対しても以下の性質が真であるときA を特殊和集合と呼ぶ。

  1. S(B) ≠ S(C):部分集合の要素の総和は異なる
  2. B が C より多くの要素を含んでいれば S(B) > S(C)

本問題に対しては,与えられた集合は n 個の単調増加する要素を含み,かつ第二のルールをすでにみたしているものとする。

n = 4 の集合から得ることができる 25 個の可能な部分集合の対のうち,1 個の対のみが 同一性(第一のルール)をテストされる必要がある。
同様に n = 7 のときは 966 個の部分集合の対のうち 70 個のみがテストされる必要がある。

n = 12 に対して得られる 261625 個の部分集合の対のうち,同一性をテストされる必要があるものは何個か。

注意:この問題は Problem 103 と 105 に関連している*1

本家:Problem 106 - Project Euler
日本語訳:Problem 106 - PukiWiki

n=4 のとき

「n = 4 (中略) 25 個の可能な部分集合の対のうち~」を理解するのにかなり時間がかかりました。

A の要素を小さい方から順にa1, a2,..., an とします。この問題で考えているのは部分集合そのものではなく,部分集合の対なので
「25個ある」=「添字の組の選び方が25通りある」
です。

また,この25という数字は問題文中の「第二のルールをすでにみたしているものとする」を無視した場合の全組み合わせ数のことでした。実際に調べなければならない組はもっと少ないです。

  • ルール2 により,要素の個数が異なる集合を比較する必要はない
  • 要素数1の集合も比較する必要がない

結局,n=4 のとき考えなければならないのは要素数2の場合だけです。
二項係数を C(n, k) のように書くと

 C(4,2)\times C(2,2)/2=\text{3 通り}

あります。

  • {1, 2}, {3, 4}
  • {1, 3}, {2, 4}
  • {1, 4}, {2, 3}

a1 < a3, a2 < a4 より1つ目のケースは調べる必要がありません。
2つ目も同様。
3つ目は a1 < a2, a4 > a3 より調べる必要があります。問題文中の「1 個の対のみ」はこれのことです。

一般化

要素数を k として,選んだ添字を

  • {x1, x2, ..., xk} (x1< x2< ... < xk)
  • {y1, y2, ..., yk} (y1< y2< ... < yk)

とします(x1< y1)。

x2< y2, x3 < y3, ..., xk < yk がすべて成立すれば調べる必要がなく,少なくとも1つが不成立なら調べる必要があります。

調べなくてよいケースの方を数えましょう。これは1から 2k までの整数を2段に並べるときに「右の数は左より大きい」「下の数は上より大きい」をみたす並べ方と同じだけあり,カタラン数 Ck で与えられます。

 C_k=\displaystyle \frac{{}_{2k} C_{k}}{k+1}

x1 ~ yk に使う数字の選び方が C(n, 2k) 通りあるので,要素数 k で調べなくてよいケースの個数は次のとおりです。

 \displaystyle \frac{{}_{2k} C_{k}}{k+1}\cdot {}_{n} C_{2k}

これを組み合わせの総数から引きます。要素数が k で調べなければならないものの個数は次のようになります。

 f(n,k)= \displaystyle  {}_{n} C_{k} \cdot {}_{n-k} C_{k}\cdot \frac{1}{2} - \frac{{}_{2k} C_{k}}{k+1}\cdot {}_{n} C_{2k}
 = \displaystyle  \frac{(k-1)\, n!}{2\cdot (k+1)!\, k!\, (n-2k)!}

これの和をとりました。





*1:実際にはほぼ関係ない。