一道数据划分问题

mathe

转自:http://www.aoshoo.com/bbs1/dispbbs.asp?boardID=63&ID=11218&page=1 感觉这道题目不错： 对于正整数Ｎ，{1, 2, …, 3N}这个集合，可以分成三个Ｎ元集合Ａ、Ｂ、Ｃ，且 ｃ_ｉ＝ａ_ｉ＋ｂ_ｉ（ｉ＝1，2，…，Ｎ），其中 ｃ_ｉ,ａ_ｉ,ｂ_ｉ 表示Ａ、Ｂ、Ｃ中的元素， 的充要条件是：Ｎ＝４Ｋ＋１或Ｎ＝４Ｋ，Ｋ为自然数。

mathe

For this problem, I have tried to use computer to search result for N=4K or N=4K+1. It seems that we could always take $a_t=t, 1<=t<=N$ In other words, it means for any 2N continue integers (where N=4K or 4K+1) we could always partition them into two sets B and C with same size so that $c_t - b_t=t , 1<=t<=N$

guetsxjm

只想得到必要性： 若有$c_i = a_i + b_i$（i＝1，2，…，N），则 $S_c = \sum_{i=1}^{N}c_i$ = $1/2$ * $3N*(1+3N)/2$ = $3N*(1+3N)/4$ 很显然: $S_c$是正整数,则有：3N|4或(1+3N)|4, 从而有 N＝4K+1 或 N＝4K，K为自然数;

guetsxjm

原帖由 mathe 于 2008-2-15 10:41 发表 For this problem, I have tried to use computer to search result for N=4K or N=4K+1. It seems that we could always take $a_t=t, 1

对于 $a_t$ = t (t = 1...N)也不尽然,只要满足集合C中的元素之和是总和的一半即可，划分方式并不唯一； 如：正整数集合：{1,2,3,4,5,6,7,8,9,10,11,12},可以写成： 6 = 2+4， 10= 1+9， 11= 3+8， 12= 5+7；

mathe

必要性很简单。 充分性需要通过构造来证明，总算想出一种构造方法了。 以 N=4k为例： $(12k-2t)-(8k-t)=(4k-t), 0<=t<=2k$ $(8k-t)-(4k+1+t)=(2(k-t)+1), 1<=t<=k$ $(12k-2t-1)-(8k+2t+1)=2(2k-2t-1), 0<=t<=k-1$ 上面3组数正好构成了$c_i-b_i=a_i$ 对于N=4k+1,构造方法完全类似。

mathe

上面方法有误。 不过现在对于N的4进制表示中每位都是0和1的情况已经构造出来了，但是其他情况还在考虑之中

mathe

原帖由 guetsxjm 于 2008-2-16 01:20 发表 对于 $a_t$ = t (t = 1...N)也不尽然,只要满足集合C中的元素之和是总和的一半即可，划分方式并不唯一； 如：正整数集合：{1,2,3,4,5,6,7,8,9,10,11,12},可以写成： 6 = 2+4， 10= 1+9， 11= 3+8， 12= 5+7； ...

我是发现总是存在解使得$a_t$ = t ，而不是说所有的解总是$a_t$ = t 。 证明充分性的方法在于构造解，所以只要构造满足$a_t$ = t 的解就可以。这个比盲目构造可以减轻一些难度

mathe

对于我提到一个相关命题: P(N): 任意连续的2N个整数，可以分成两个元素相等的数列B,C使得$C_k-B_k=k, 1<=k<=N$ 那么P(N)在N = 0,1 (mod 4)时成立。 对于这个命题，我现在的进展时 如果P(N)成立，那么P(3N+1),P(4N),P(4N+1)均成立。 先把这部分贴出来，然后就先停一停，我要开始花点时间写编译器方面的题材。

mathe

1.如果P(N)成立，那么P(4N)也成立。 对于8N个连续整数,不妨假设它们就是1,2,...,8N $(8N ) -(4N )=(4N )$ $(8N-2)-(4N-1)=(4N-1)$ $ ... $ $(4N+2)-(2N+1)=(2N+1)$ $(2N) - (1) =(2N-1)$ $(2N-1) - (2) = (2N-3)$ $ ... $ $(N+1)- (N) = (1) $ 通过上面的指派(等号后面为k的指派成$c_k-b_k=k$) 8N个整数中余下4N+1,4N+3,....,8N-1 (2N个连续奇数),差值余下2,4,...,2N (N个最小偶数) 由于P(N)成立，存在数组e,d使得$(e_t)-(d_t)=t (1<=t<=N)$,而且e,d的并集构成1,2,...,2N 所以$(4N+2e_t-1)-(4N+2d_t-1)=2t$ 于是我们可以指派$c_{2t}=4N+2e_t-1,b_{2t}=4N+2d_t-1$ 正好完成上面的指派过程，所以P(4N)成立

mathe

对于如果P(N)成立那么P(4N+1)也成立的构造过程几乎同上面过程相同，所以这里就不继续详细写出了，下面证明 如果P(N)成立，那么P(3N+1)也成立。 如果P(N)成立，那么我们存在指派 $c_t-b_t=t, (1<=t<=N)$,其中左边$c_t,b_t$正好使用1~2N之间的整数。 $(5N+2)-(2N+1)=(3N+1)$ $(5N+1)-(2N+2)=(3N-1)$ $ .... $ $(4N+2)-(3N+1)=(N+1)$ 同样 $(6N+2)-(3N+2)=(3N )$ $(6N+1)-(3N+3)=(3N-2)$ $ .... $ $(5N+3)-(4N+1)=(N+2)$ 我们可以看出，上面两个指派过程左边正好用了2N+1到6N+2之间所有数，右边正好用了N+1到3N+1之间所有数， 加上前面P(N)中的指派过程，正好完成了P(3N+1)的指派问题。所以P(3N+1)也成立。