|
n個の相異なる正整数a(1),a(2),……..,a(n)が与えられている。
集合{a(1),a(2),……..,a(n)}の空集合Φ
以外のすべての部分集合(すなわち2^n-1個の部分集合)を考える。
さらに各部分集合に関してすべての要素の総和を求めるとき、
それらの中には少なくともn(n+1)/2個の異なる値が存在することを示せ。
解答
・わたしの…
a(1)<a(2)<…<a(n) と考える...
少なくともn種類は異なる…
a(1)+a(n)
a(2)+a(n)
…
a(n-1)+a(n) のn-1個は異なる
a(1)+a(2)+a(n)
a(2)+a(3)+a(n)
…
a(n-2)+a(n-1)+a(n) のn-2個は異なる
so…
同様に,,,
最後は…a(1)+a(2)+…+a(n) の1個は異なる
so…
n+(n-1)+(n-2)+…+1=n(n+1)/2 個は異なるものがある ^^
QED
易問では…^^;…? ↑
これでは言えてませんでしたぁ ^^; Orz…
・鍵コメ様からのコメント Orz〜
例えば,a(k)+a(k+1)+a(n) (k=1,2,3,…,n-2)のうちに
a(n-1)+a(n)と等しいものがあることはあり得て, このn+(n-1)+(n-2)+…+1通りはすべて異なる保証がありません. たしかにそうでしたわ ^^;;…
↓
・再考ぉ〜 ^^;v
以下のように考えればよかったわけですわね ^^
a(1),a(2),…,a(n)のn個
a(1)〜a(n-1)の1個とa(n)との和…n-1個
a(1)〜a(n-2)の1個とa(n-1)+a(n)との和…n-2個
a(1)〜a(n-3)の1個とa(n-2)+a(n-1)+a(n)との和…n-3個
…a(1)+a(2)+…+a(n)…1個 |

- >
- Yahoo!サービス
- >
- Yahoo!ブログ
- >
- 練習用


