[問題]集合問題

[問題]集合問題

浩浩 於 星期三 九月 01, 2004 10:14 pm


每一個正整數所形成的集合都有一個"交錯和",定義如下:將此集合中的數,由大到小排列,交錯的加減得到一個結果,稱此集合的交錯和.
ex:集合{1,2,4,6,9}的交錯和為9-6+4-2+1=6,集合{6}的交錯和為6.空集合的交錯和為0
現在試求出{1,2,3,4,5.......2004}的所有子集合交錯和的總和
Fernando Tan
歡迎大家加入: http://tw.club.yahoo.com/clubs/happylearning/

只要我不放棄,夢想就在不遠處

浩浩
版 主
版 主
 
文章: 488
註冊時間: 2004-02-14
來自: 數之領域

J+W 於 星期三 九月 01, 2004 11:38 pm


欲求{1,2,3,4,5.......2004}的所有子集合交錯和的總和

先簡化問題試試

1.先求{1}的所有子集合交錯和的總和=1
{ }=0
{1}=1

2.先求{1,2}的所有子集合交錯和的總和=4
{ }=0
{1}=1
{2}=2
{1,2}=1

3.先求{1,2,3}的所有子集合交錯和的總和=12
{ }=0
{1}=1
{2}=2
{3}=3
{1,2}=1
{2,3}=1
{1,3}=2
{1,2,3}=2

3.再求{1,2,3,4}的所有子集合交錯和的總和=32
{ }=0
{1}=1
{2}=2
{3}=3
{4}=4
{1,2}=1
{2,3}=1
{3,4}=1
{1,3}=2
{2,4}=2
{1,4}=3
{1,2,3}=2
{2,3,4}=3
{1,3,4}=2
{1,2,4}=3
{1,2,3,4}=2

似乎沒有規律?

J+W
版 主
版 主
 
文章: 2165
註冊時間: 2003-12-30

浩浩 於 星期三 九月 01, 2004 11:54 pm


恩恩.....應該有規律
但我的想法是規律存在於每個子集合之中,意思就是每幾個子集合的和為一組這樣分類,應該會有關西吧.......
我也還在嘗試中
Fernando Tan
歡迎大家加入: http://tw.club.yahoo.com/clubs/happylearning/

只要我不放棄,夢想就在不遠處

浩浩
版 主
版 主
 
文章: 488
註冊時間: 2004-02-14
來自: 數之領域

浩浩 於 星期四 九月 02, 2004 12:03 am


剛剛收到另一個討論區給我的解法
Let f(n) be the sum of all the 'alternating sums' of{1,2,3.....n} 's subsets.
To evaluatef(n), we can calculate the 'alternating sums' by separating the subsets into two types: contains  and does not contain .

For those 2^(n-1) subsets which does not contain , the sum of 'alternating sums' will be f(n-1) .
For the remaining2^(n-1)  subsets containing ,  must be the greatest number in the subsets.
Every subsets of these can be expressed as {n}聯集A, where A包含在{1,2,3.....n-1}, and so its 'alternating sum' must equal  minus the 'alternating sum' of A .
Therefore the sum of 'alternating sums' of these subsets= sigma[A包含在(1,2,.....n-1)] [n-alternating sum(A)]=2^(n-1) *n-f(n-1).
Summing up, we get f(n)=2^(n-1)n .
Fernando Tan
歡迎大家加入: http://tw.club.yahoo.com/clubs/happylearning/

只要我不放棄,夢想就在不遠處

浩浩
版 主
版 主
 
文章: 488
註冊時間: 2004-02-14
來自: 數之領域






『數學及時、求救區』