趣题:奇怪的自然数集划分

    给定一个集合S和数n,从集合S中取出两个不同的数a,b满足a+b=n的总方案数叫做“集合S中关于n的互补数对个数”。是否有可能把全体非负整数划分为A、B两个集合,使得对于任意一个n,集合A和集合B中关于n的互补数对的个数都相同?

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
    答案是肯定的。此处,神奇的二进制再次在看似与它毫不相干的地方显示出自己独特的力量。把所有数写成二进制,有偶数个数字“1”的数归入A集合,有奇数个数字“1”的归入B集合。为了证明A、B中关于n的互补数对个数相同,我们在这两组互补数对间建立一个一一对应的关系。假设A集合中有两个数a1,a2满足a1+a2=n,那么找出a1和a2的二进制表达中右起第一个数码不同的地方(由于a1≠a2,因此这一定能办到)。把两个数字各自在该位置上的数码对换一下,“0”变成“1”,“1”变成“0”。新的两个数就是b1和b2。显然,b1和b2都属于B集合,并且b1+b2=n。

    有趣的是,这种划分方法是唯一的(无妨设0∈A)。为了证明这一点,我们只需要施归纳于n:假设为了满足关于1,2,…,n-1的互补数对个数相同的条件,从0到n-1这n个数的位置是唯一确定的,现在考虑(为了满足关于n相等的条件)n应该放到哪边。假设在没有n的时候,两个集合关于n的互补数对分别有c(A)和c(B)个。把n放进集合B里之后c(A)和c(B)都不变,但把n放进集合A后c(A)会加一(因为0在A里)。因此,n最多属于其中一个集合,不可能出现两边都可以的情况。

8 条评论

  • yuye_abc

    没有占到沙发……

    ps:wp加一个wap插件吧,大家一起用手机看看……

  • ruoeren

    那单纯把数划分成奇数和偶数不也可以吗?
    对于n为奇数,方案数都为0
    对于n为偶数,方案数都是n/2

    有什么问题,请指教

    回复:n=2就不行,{0,2}里有一个,{1}里没有。

  • wangyuantao

    按照你的构造方法跑下来,A={0,3,5,7,…2k+1,…},B={1,2,4,6,8,…,2k,…}对么?另外,唯一性的证明很有启发性,赞!不过我觉得不是很严谨,按照你的思路,归纳终点应该是n恰属于其中一个集合,而不是你最终导出的“最多属于其中一个集合”。另外,这个归纳的思路我也觉得不是很有把握,按照标准的集合划分唯一的证明方法,应该假设A’和B’也是非负整数全体的一个划分,使得0属于A’,往证A=A’,其中A是你算法构造的那个集合。反证法假设A不等于A’,则A与A’对称差非空,从中取最小元n,然后想办法导出矛盾。不过恕后生才疏学浅,没证下去,望指教~

  • 九点圆

    f(x)+g(x)=1/(1-x)
    f(x)^2-f(x^2)=g(x)^2-g(x^2)
    f(x^2)-g(x^2)=f(x)^2-g(x)^2=(f(x)-g(x))/(1-x)
    f(x)-g(x)=(1-x)…(1-x^2^n)*(f(x^2^(n+1))-g(x^2^(n+1)))
    (f,g)(x^2^(n+1))->1(say)
    f(x)-g(x)->1/(1+x)

  • 九点圆

    correction:f(x^2^(n+1))->1,g(x^2^(n+1))->0

  • cervelo

    有想法就去验证,让大家多学习,多参考参考。

  • ernest

    Evil 和 Odious 數,很漂亮的一個東西。

发表评论

42  +    =  48