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 個の部分集合の対のうち, 同一性をテストされる必要があるものは何個か.

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