第四届丘成桐中学数学奖获奖论文-关于两集合元素相加问题的初步研究_百

2023年12月13日发(作者：昼短夜长)

-

关于两集合元素相加问题的初步研究

陈恩献 陈钱钰 胡诗庭

（温州中学高三（1）班 浙江温州 325014）

指导老师 陈相友

摘要：

本文由一个较为常见的结论出发，研究集合的元素相加这一模型的性质，得到和的个数与两集合元素的书之间的关系，并研究达到一定等量关系的充要条件，在研究和的个数等于两集合元素个数之和的充要条件时，我们从特殊情况入手，逐步推进，最终达到了目标。

一、引言

集合的元素之和是一个深刻而又有趣的话题，其中结论众多。我们注意到其中一个优美的命题（结论一），希望以此为出发点，得到更多让我们感到惊喜的结论。

我们有如下问题：

1、和的取值个数与原集合的元素个数有怎样的关系？

2、和的取值在与原集合元素个数达到某个等量关系的充要条件是什么？

这两个问题将成为我们主要的研究对象。

二、结论与证明

结论一：A和B是R的两个非空子集，且设C=A+B={a+b|a∈A，b∈B}则|C|≥|A|+|B|-1。

证明：设|A|=m，|B|=t，t≥m。

记A={x1,x2,……,xm},B={y1,y2,……,yt}

且x1

考虑下面t+m-1个数

x1+y1

它们互不相同，故|C|≥|A|+|B|-1。

结论一是一个常见结论，它给出了|A+B|的最小值，而|A+B|显然不超过|A|×|B|,|A+B|只能在|A|+|B|-1，|A|+|B|,…,|A|×|B|中取值，但我们发现事实上|A+B|可取遍|A|+|B|-1，|A|+|B|,…,|A|×|B|中的全部值，于是得出了结论二。

结论二：A和B是R的两个非空子集，且设C=A+B={a+b|a∈A，b∈B}则|C|可取遍|A|+|B|-1，|A|+|B|,…,|A|×|B|中的全部值。

证明：不妨设|A|=m，|B|=t，t≥m。

先看|c|=m×t的情形，采用直接构造

不妨令B={1,2，…，t}，Amt={1,t+1,2t+1,…,(m-1)t+1}

则C=Amt+B={2,3，…，mt+1}，为证明此，我们给出下面的引理

引理一：A＇∈N+,A＇={a1,a2},B={1,2,…,t},a2≥a1+n

则A＇+B={a1+1，a1+2，…，a2+t}

引理一的证明：以下这串数列中的数均是A＇+B中的数a1+1,

a1+2,…,

a1+t,

a2+1,

a2+2,…,

a2+t。

∵（a2+1）-(a1+t)=

a2-a1+1-t≥t+1-t=1. ∴它取遍a1+1,…,

a2+t中所有整数，引理一得证。

下面回到原命题，由引理一易得Amt+B={2,3,…,mt+1},则|Amt+B|=mt，我们试图经过调整Amt，依次得到Amt−1，Amt−2,…Am+t−1,使|Ak+B|=k

记xk=maxx，yk=maxy,

Ak =Ak+1{xk+1}∪{yk+1}

x∈Aky∉Aky

由此可知Ak中相邻两元素差的绝对值不超过t

设Ak={xk,1,xk,2,…,

xk,m},1=xk,1

由引理

Ak+B={xk,1+1,

xk,1+2,…,

xk,m+t},

|Ak+B|=xk,m+t-1=xk-1+t=xk+1-2+t=|Ak+1+B|-1=…=|Amt+B|-mt+k=k

结论二得证！

得到结论二之后，我们希望得到|C|=|A+B|=k的充要条件，我们先尝试了|C|=m+t-1的情形，得到了结论三。

结论三：结论一中，当|C|=|A|+|B|-1时（|B|≥2）,A,B中的元素均构成等差数列，且两数列公差相同。

证明：采用与结论一相同的记法，考虑下面t+m-1个数

x1+y1

比较①与②中的t+m-1个数

易知它们一一对应, 故可推得y2-x2=y1-x1, y3-x3=y1-x1,……，ym-xm=y1-x1 ,(m<=t);

令y1-x1=d,由于将集合B中的数都减去一个相同的数时，结论不变，故可将B中每个都减去d，则变换后B中前m个数为{x1,x2,……,xm},

由结论一，集合{x1,x2,……,xm}和自身相加所得的集合至少2m-1个元素，它们都不超过2xm，当然也都小于xm+ym+1,

又xm+ ym+1

故|c|≥2m-1+t-m=m+t-1等号成立时，我们有

集合{x1,x2,……,xm}与自身相加只得到2m-1个数，考虑下面2m-1个数

2x1

∵x1+x2<2x2

x1+x2

∴2x2=x1+x3 ∴x1,x2,x3成等差数列。

同理可得x1,x2,……,xm成等差数列，即集合A中的数构成等差数列，由①又知B中数也成等差数列，且公差与A相等，

又当A中的数和B中的数都构成等差数列时，显然它们相加所得集合中有|A|+|B|-1个元素，结论三得证！

结论三中|B|≥2是必要的，否则A集合元素可任取，不一定要构成等差数列，我们发现|C|=|A|+|B|-1的成立条件比较严格，那么放松一步，当|C|=|A|+|B|的情况又如何呢？经过研究，这一情况比较复杂，我们先给出A=B即一个集合自身相加的情况。

结论四：A是R的一个非空子集，|A|=n（n>3）记集合x={x+y|x，y∈A}则使x恰有2n个元素的A为{a，a+d,a+2d, …,a+（n-2）d，a+nd}或{a,a+2d,a+3d, …,a+（n-1）d，a+nd}。

证明：由于将A中的元素同时加上（或减去）一个数后结论不变。故可不妨设A中的最小元素为0，又将A中元素同时乘一个数（非零）后结论仍不变，故可不妨设A中最大元素为1，则我们只需证明满足要求的n元集合为{0,23n−112, ,…, ,1}或{0,, ,…,

nnnnnn−2,1}

n设A={x1,x2, …,

xn}下面这串数列是x中的元素

2x1

这是X中2n-1个不同的数，而|x|=2n-1，设余下的一个数为C

且xk−1+xk

则集合{x1,x2,…,xk}和{x1,x2,…,xk−1}相加之后恰有2k-2个元素 集合{xk+1，…,,

xn}和{xk,

xk+1,…,

xn}相加后恰有2n-2k个元素

由结论三可知

x1,x2,x3,…,xk构成等差数列，xk,xk+1,…,

xn也够成等差数列

但公差不等，否则由结论三可知，x中只有2n-1个数

下面分两种情况讨论

1°若xk−1+xk

∵xk−1+xk

∴c=xk−1+xk+1

若k>2则由于xk−1+xk−2

故xk−2+xk+1=2xk−1或xk−1+xk

若xk−2+xk+1=xk−1+xk则xk−1-xk=xk−1-xk

矛盾！

故xk−2+xk+1=2xk−1 则xk+1 –xk−1=xk−1 –xk−2

而xk+1 –xk−1 >xk—xk−1=xk−1 –xk−2 矛盾！

故k=2 , c=x1+x3

因为x1+x3

若x1+x4=x2+x3

x2—x1=x4—x3矛盾！

若x1+x4=2x3 则x4—x3=x3—x1>x3—x1=x4—x3 矛盾！

所以x1+x4=2x2,

x1—x2=x2—x4=2(x2—x3)

所以这个数列为{0,23n−1, ,…, ,1}

nnn12n−2, ,…, ,1}

nnn2°若 2xk

由证明过程知n〉3是必需的，下面我们将运用结论会得到更一般的结论五。

结论五：A，B 是Ｒ的两个非空子集（Ａ，Ｂ不相同）,|A|=n , |B|=n, n>3,记集合Ｃ＝｛x+y︳x∈A,y∈B｝ 则使Ｃ恰有２n个元素的Ａ，Ｂ应满足

Ａ＝｛d,2d,……,kd,(k+2)d,……(n+1)d｝（1≤k≤n-1）

Ｂ＝｛d,2d……nd｝

或Ａ＝｛d,2d……nd｝

Ｂ＝｛d,2d……kd,(k+2)d,……(n+1)d｝（1≤k≤n-1）

以及Ａ，Ｂ中元素分别加上（或减去）一个实数的集合．

证明：设Ａ＝｛x1,x2……,

xn｝ Ｂ＝｛

y1,y2……,

yn ｝

x1

y1

则有x1+y1

⑤中共有2n-1个不同的数。设集合C中不在⑤中出现的一个数为c。

1°x1+y1＜c＜x1+y2，记B＇={y2，…，yn}则A与B′相加得到的新集合至少出现2n-2个不同的数，它们都大于c和x1+y1，故集合C中至少出现2n-2+1+1=2n个数，故A+B′只有2n-2个元素

由结论三知，数列{x1，x2，…，xn}，{y2，y3…，yn}成公差相等的等差数列,

将A,B同时加（或减）一个数结论不变

故可不妨设x2=y2，x3=y3，…，xn=yn，xi=id（i=1,2，…，n）

∵y1+x1＜y2+x1=3d ∴x1+y1不出现在A+B′中

若y1+x2在A+ B′中 ，则y1+x2=3d 即y1=d。此时C中只有2n-1个元素，矛盾!

∴x1+y1,y1+x2均不在A+ B′中，∴y1+x3在A+ B′中，∴只能是y1+x3=3d，∴y1=0.

此时A：{d，2d，…，nd} B：{0，2d，3d，…，nd},经检验，符合要求。

2°xn−1+yn

A={d,2d,…,(n-1)d,(n+1),B={d,2d,…,(n-1)d,nd}

3°xk−1+yk−1

记A1={x1,x2,…xk−1},A2={xk−1,xk,…,

xn}

B1={y1,y2,…,

yk−1},B2={yk,

yk−1,…,

yn}

则|A1+B1|≥2k-3,|A2+B2|≥2n-2k+2,而2k-3++2n-2k+2+1=2n,

∴只能是|A1+B1|=2k-3,|A2+B2|=2n-2k+2

由结论三，A1,B1中的数构成公差相等的等差数列，A2,B2中的数构成公差相等的等差数列，与前面类似的，可设x1=y1,

x2=y2,…,

xk−1=yk−1 ∵2xk−1

① 若xk+xk−1=xk−1+yk,

xk=yk,从而推得A=B

此即为结论四。

②若xk+xk+1=c

由xk−1+yk−1＜c＜xk−1+yk知xk−1+yk−1＜xk+xk−1＜xk−1+yk

由k≥3，我们考虑xk+xk−1

∵xk−2+yk−1=xk−2+xk−1＜xk+xk−2＜xk+xk−1

∴xk+xk−1=2xk−1即xk-xk−1=xk−1-xk−2

∴集合A中的数成等差数列

下面再考虑yk+xk−2

∵xk−2+xk−1＜xk−2+yk＜xk−1+yk

∴xk−2+yk=2xk−1或xk+xk−1 若xk−2+yk=2xk−1

则xk−1-xk−2=yk-xk−1 ∴xk−1-xk−2=xk-xk−1 ∴xk=yk 从而A=B

但此时|A+B|=2n-1

若xk−2+yk=xk+xk−1即yk-xk−1=xk-xk−2=2(xk-xk−1)

∴此时A={d,2d,…,nd} B={d,2d,…kd,（k+2)d,…,(n+1)d}(1≤k≤n-1)

4°若xk−1+yk＜c＜xk+yk (2≤k≤n-1)

此时可与3°完全类似推得A={d,2d,…kd,（k+2)d,…,(n+1)d}(1≤k≤n-1)B={d,2d,…,nd}

综合1°，2°，3°，4°可得结论五。

最后给出|A+B|=|A|+|B|最一般的情况，我们将用结论三，四，五推出结论六。

结论六：A,B是R的两个非空子集 A={x1,x2,…,

xt}其中x1＜x2＜…＜xt

B={y1,y2,…,

yn}其中y1＜y2＜…＜ym ,m≥t,C=A+B={x+y|x∈A，y∈B}

则使|c|=k+m的充要条件是A={d,2d,…,td},B={d,2d,…kd,（k+2)d,…,(m+1)d}(1≤k≤m-1)或A={d,2d,…kd,（k+2)d,…,(t+1)d}(1≤t≤k-1),B={d,2d,…,md}或A={d,2d,…,(t-1)d,（t+1)d},B={d,2d,…,(m-1)d,(m+1)d}以及A,B分别加上（或减去）一个数的集合。

证明：必要性显然。设B1={y1,y2,…,

yt},B2={yt+1,…,

ym} |A+B1|≥2t-1对于x∈A+B1，则x≤xt+yt＜xt+yt+1＜xt+yt+2＜…＜xt+ym

记C1=A+B1，C2={xt+yi|t+1≤i≤m}，则C1∩C2=空集

（∴|C|≥|C1∪C2|=|C1|+|C2|≥2t-1+m-t=t+m-1，又|C1|+|C2|≤t+m）欲使|C|=t+m只有|C1|=2t,|C2|=m-t，或|C1|=2t-1,|C2|=m-t+1

1°若|C1|=2t-1,|C2|=m-t+1

由结论三，我们可设x1=d,

x2=2d,…,

xt=td,

y1=x1,y2=x2,…,

yt=xt

记不出现在C1∪C2的C中的数为a。

考虑数yt+1+xt−1

① 若a≠yt+1+xt−1，则xt−1+yt+1∈C1，由于xt−1+yt+1=(t-1)d+yt+1＞(t-1)d+yt=(2t-1)d而maxx≤2td,∴只能xt−1+yt+1=2td,即yt+1=(t+1)d

x∈C1② 若a=yt+1+xt−1，再考虑数yt+1+xt−2,由于xt−1+yt+1＞xt−1+yt=(2t-2)d

∴xt−1+yt+1=(2t-1)d或2td，若yt+1=(t+1)d,则yt+1+xt−1=2td∈C1，矛盾！

故yt+1=(t+2)d，类似地，再考虑yt+2+xt−1得yt+2=(t+3)d,…,

ym=(m+1)d,

对第①种情况作类似讨论得A={d,2d,…,td}，B={d,2d,…,kd,(k+2)d,(k+3)d,…,(m+1)d}(t≤k≤m-1)

2°若|C1|=2t,|C2|=m-t+1

则由结论五，可分为以下3种情况

①xi=id（1≤i≤t）且存在k（1≤k≤t-1）使yk=kd ，yk+1= （k+2）d

此时完全类似1°可得yt=（t+1）d（t≥k+1）

②yi=id（1≤i≤t）且存在k（1≤k≤t-2）使xk=kd ，xk+1=（k+2）d

仍类似1°可得yi=di（1≤i≤m）

③yi=id（1≤i≤d）且xt−1=(t-1)d

xt=(t+1)d

此时仍类似1°的讨论可知yi=id（1≤i≤m-1）ym=md或(m+1)d

结合1°，2°结论六证毕。

对|A+B|=|A|+|B|的充要条件我们的做法已非常的繁琐，但是结论还是较严格的，但当|A+B|=k，k足够大时，A与B的性质就不好把握了。例如|A+B|=|A|+|B|时，A,B的条件还是非常宽泛的（例如结论三给出的构造，或用进位制给出构造）但如果用本文的方法做下去将会不胜其烦，我们期待能有更好的方法得出|A+B|=k时的充要条件。

-