一道数据划分问题

mathe

转自:http://www.aoshoo.com/bbs1/dispb ... 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)也成立。