Problem 201

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))を求めよ.

最新の20件

アクセス数

合計：1018 今日：2 昨日：3