第四屆丘成桐中學數(shù)學獎獲獎?wù)撐?關(guān)于兩集合元素相加問題的初步研究_百

2023年12月13日發(fā)(作者：晝短夜長)

-

關(guān)于兩集合元素相加問題的初步研究

陳恩獻 陳錢鈺 胡詩庭

（溫州中學高三（1）班 浙江溫州 325014）

指導老師 陳相友

摘要：

本文由一個較為常見的結(jié)論出發(fā)，研究集合的元素相加這一模型的性質(zhì)，得到和的個數(shù)與兩集合元素的書之間的關(guān)系，并研究達到一定等量關(guān)系的充要條件，在研究和的個數(shù)等于兩集合元素個數(shù)之和的充要條件時，我們從特殊情況入手，逐步推進，最終達到了目標。

一、引言

集合的元素之和是一個深刻而又有趣的話題，其中結(jié)論眾多。我們注意到其中一個優(yōu)美的命題（結(jié)論一），希望以此為出發(fā)點，得到更多讓我們感到驚喜的結(jié)論。

我們有如下問題：

1、和的取值個數(shù)與原集合的元素個數(shù)有怎樣的關(guān)系？

2、和的取值在與原集合元素個數(shù)達到某個等量關(guān)系的充要條件是什么？

這兩個問題將成為我們主要的研究對象。

二、結(jié)論與證明

結(jié)論一：A和B是R的兩個非空子集，且設(shè)C=A+B={a+b|a∈A，b∈B}則|C|≥|A|+|B|-1。

證明：設(shè)|A|=m，|B|=t，t≥m。

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

且x1

考慮下面t+m-1個數(shù)

x1+y1

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

結(jié)論一是一個常見結(jié)論，它給出了|A+B|的最小值，而|A+B|顯然不超過|A|×|B|,|A+B|只能在|A|+|B|-1，|A|+|B|,…,|A|×|B|中取值，但我們發(fā)現(xiàn)事實上|A+B|可取遍|A|+|B|-1，|A|+|B|,…,|A|×|B|中的全部值，于是得出了結(jié)論二。

結(jié)論二：A和B是R的兩個非空子集，且設(shè)C=A+B={a+b|a∈A，b∈B}則|C|可取遍|A|+|B|-1，|A|+|B|,…,|A|×|B|中的全部值。

證明：不妨設(shè)|A|=m，|B|=t，t≥m。

先看|c|=m×t的情形，采用直接構(gòu)造

不妨令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}

引理一的證明：以下這串數(shù)列中的數(shù)均是A＇+B中的數(shù)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中所有整數(shù)，引理一得證。

下面回到原命題，由引理一易得Amt+B={2,3,…,mt+1},則|Amt+B|=mt，我們試圖經(jīng)過調(diào)整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

設(shè)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

結(jié)論二得證！

得到結(jié)論二之后，我們希望得到|C|=|A+B|=k的充要條件，我們先嘗試了|C|=m+t-1的情形，得到了結(jié)論三。

結(jié)論三：結(jié)論一中，當|C|=|A|+|B|-1時（|B|≥2）,A,B中的元素均構(gòu)成等差數(shù)列，且兩數(shù)列公差相同。

證明：采用與結(jié)論一相同的記法，考慮下面t+m-1個數(shù)

x1+y1

比較①與②中的t+m-1個數(shù)

易知它們一一對應(yīng), 故可推得y2-x2=y1-x1, y3-x3=y1-x1,……，ym-xm=y1-x1 ,(m<=t);

令y1-x1=d,由于將集合B中的數(shù)都減去一個相同的數(shù)時，結(jié)論不變，故可將B中每個都減去d，則變換后B中前m個數(shù)為{x1,x2,……,xm},

由結(jié)論一，集合{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個數(shù)，考慮下面2m-1個數(shù)

2x1

∵x1+x2<2x2

x1+x2

∴2x2=x1+x3 ∴x1,x2,x3成等差數(shù)列。

同理可得x1,x2,……,xm成等差數(shù)列，即集合A中的數(shù)構(gòu)成等差數(shù)列，由①又知B中數(shù)也成等差數(shù)列，且公差與A相等，

又當A中的數(shù)和B中的數(shù)都構(gòu)成等差數(shù)列時，顯然它們相加所得集合中有|A|+|B|-1個元素，結(jié)論三得證！

結(jié)論三中|B|≥2是必要的，否則A集合元素可任取，不一定要構(gòu)成等差數(shù)列，我們發(fā)現(xiàn)|C|=|A|+|B|-1的成立條件比較嚴格，那么放松一步，當|C|=|A|+|B|的情況又如何呢？經(jīng)過研究，這一情況比較復雜，我們先給出A=B即一個集合自身相加的情況。

結(jié)論四：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中的元素同時加上（或減去）一個數(shù)后結(jié)論不變。故可不妨設(shè)A中的最小元素為0，又將A中元素同時乘一個數(shù)（非零）后結(jié)論仍不變，故可不妨設(shè)A中最大元素為1，則我們只需證明滿足要求的n元集合為{0,23n?112, ,…, ,1}或{0,, ,…,

nnnnnn?2,1}

n設(shè)A={x1,x2, …,

xn}下面這串數(shù)列是x中的元素

2x1

這是X中2n-1個不同的數(shù)，而|x|=2n-1，設(shè)余下的一個數(shù)為C

且xk?1+xk

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

xn}和{xk,

xk+1,…,

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

由結(jié)論三可知

x1,x2,x3,…,xk構(gòu)成等差數(shù)列，xk,xk+1,…,

xn也夠成等差數(shù)列

但公差不等，否則由結(jié)論三可知，x中只有2n-1個數(shù)

下面分兩種情況討論

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)

所以這個數(shù)列為{0,23n?1, ,…, ,1}

nnn12n?2, ,…, ,1}

nnn2°若 2xk

由證明過程知n〉3是必需的，下面我們將運用結(jié)論會得到更一般的結(jié)論五。

結(jié)論五：A，B 是Ｒ的兩個非空子集（Ａ，Ｂ不相同）,|A|=n , |B|=n, n>3,記集合Ｃ＝｛x+y︳x∈A,y∈B｝ 則使Ｃ恰有２n個元素的Ａ，Ｂ應(yīng)滿足

Ａ＝｛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）

以及Ａ，Ｂ中元素分別加上（或減去）一個實數(shù)的集合．

證明：設(shè)Ａ＝｛x1,x2……,

xn｝ Ｂ＝｛

y1,y2……,

yn ｝

x1

y1

則有x1+y1

⑤中共有2n-1個不同的數(shù)。設(shè)集合C中不在⑤中出現(xiàn)的一個數(shù)為c。

1°x1+y1＜c＜x1+y2，記B＇={y2，…，yn}則A與B′相加得到的新集合至少出現(xiàn)2n-2個不同的數(shù)，它們都大于c和x1+y1，故集合C中至少出現(xiàn)2n-2+1+1=2n個數(shù)，故A+B′只有2n-2個元素

由結(jié)論三知，數(shù)列{x1，x2，…，xn}，{y2，y3…，yn}成公差相等的等差數(shù)列,

將A,B同時加（或減）一個數(shù)結(jié)論不變

故可不妨設(shè)x2=y2，x3=y3，…，xn=yn，xi=id（i=1,2，…，n）

∵y1+x1＜y2+x1=3d ∴x1+y1不出現(xiàn)在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},經(jīng)檢驗，符合要求。

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

由結(jié)論三，A1,B1中的數(shù)構(gòu)成公差相等的等差數(shù)列，A2,B2中的數(shù)構(gòu)成公差相等的等差數(shù)列，與前面類似的，可設(shè)x1=y1,

x2=y2,…,

xk?1=yk?1 ∵2xk?1

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

xk=yk,從而推得A=B

此即為結(jié)論四。

②若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中的數(shù)成等差數(shù)列

下面再考慮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°可得結(jié)論五。

最后給出|A+B|=|A|+|B|最一般的情況，我們將用結(jié)論三，四，五推出結(jié)論六。

結(jié)論六：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分別加上（或減去）一個數(shù)的集合。

證明：必要性顯然。設(shè)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

由結(jié)論三，我們可設(shè)x1=d,

x2=2d,…,

xt=td,

y1=x1,y2=x2,…,

yt=xt

記不出現(xiàn)在C1∪C2的C中的數(shù)為a。

考慮數(shù)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，再考慮數(shù)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

則由結(jié)論五，可分為以下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

結(jié)合1°，2°結(jié)論六證畢。

對|A+B|=|A|+|B|的充要條件我們的做法已非常的繁瑣，但是結(jié)論還是較嚴格的，但當|A+B|=k，k足夠大時，A與B的性質(zhì)就不好把握了。例如|A+B|=|A|+|B|時，A,B的條件還是非常寬泛的（例如結(jié)論三給出的構(gòu)造，或用進位制給出構(gòu)造）但如果用本文的方法做下去將會不勝其煩，我們期待能有更好的方法得出|A+B|=k時的充要條件。

-