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 103105 に関連している.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2009-04-10 (金) 20:10:17 (3113d)