Problem 106 のバックアップ(No.1)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• Problem 106 へ行く。
  • 1 (2009-04-10 (金) 20:10:17)

Problem 106 「特殊和集合:メタ検査」 †

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

i. S(B) ≠ S(C); つまり, 部分集合の和が等しくてはならない.
ii. B が C より多くの要素を含んでいればこのとき S(B) > S(C) となる.

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

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

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

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