Problem 201 「唯一の和を持つ部分集合」

数の集合Aについて, sum(A)でAの要素の和を表す. 集合B = {1,3,6,8,10,11}を考えよう. Bの3要素の部分集合は20個あり, それぞれ和は以下になる.

  • sum({1,3,6}) = 10,
  • sum({1,3,8}) = 12,
  • sum({1,3,10}) = 14,
  • sum({1,3,11}) = 15,
  • sum({1,6,8}) = 15,
  • sum({1,6,10}) = 17,
  • sum({1,6,11}) = 18,
  • sum({1,8,10}) = 19,
  • sum({1,8,11}) = 20,
  • sum({1,10,11}) = 22,
  • sum({3,6,8}) = 17,
  • sum({3,6,10}) = 19,
  • sum({3,6,11}) = 20,
  • sum({3,8,10}) = 21,
  • sum({3,8,11}) = 22,
  • sum({3,10,11}) = 24,
  • sum({6,8,10}) = 24,
  • sum({6,8,11}) = 25,
  • sum({6,10,11}) = 27,
  • sum({8,10,11}) = 29.

これらの和は1つしか現れない場合もそうでない場合もある. 集合Aについて, U(A,k)で, Aのk要素の集合全体について和を取ったときに1回のみ現れる和の集合を表す. 上の例をとると, U(B,3) = {10,12,14,18,21,25,27,29}であり, sum(U(B,3)) = 156となる.

今, 100個の要素を持つ集合 S = {12, 22, ..., 1002}を考える. Sの50要素の部分集合は100891344545564193334812497256個ある.

50要素の部分集合の和の中で1回のみ現れる和の集合の総和を求めよ. すなわち, sum(U(S,50))を求めよ.


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