*[[Problem 106:http://projecteuler.net/problem=106]] 「特殊和集合:メタ検査」 [#s9d036d9]
大きさ n の集合 A の要素の和を S(A) で表す. 空でなく共通要素を持たないいかなる 2 つの部分集合 B と C に対しても以下の性質が真であれば, A を特殊和集合と呼ぼう.
>
i. S(B) ≠ S(C); つまり, 部分集合の和が等しくてはならない.~
ii. B が C より多くの要素を含んでいればこのとき S(B) > S(C) となる.

本問題に対しては, 与えられた集合は &tex{n}; 個の単調増加する要素を含み, かつ第二のルールをすでに満たしているものと仮定しよう.

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

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

注意: この問題は [[Problem 103]] と [[105>Problem 105]] に関連している.

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS