APP下载

反3平均集的性质与构造

2015-03-23周洋洋

关键词:上界对偶平均数

周洋洋,姚 兵,许 进

(1.北京大学信息科学技术学院,北京100871;2.西北师范大学数学与统计学院,甘肃兰州730070)

反3平均集的性质与构造

周洋洋1,姚 兵2,许 进1

(1.北京大学信息科学技术学院,北京100871;2.西北师范大学数学与统计学院,甘肃兰州730070)

一个反3平均k-集包含k个互不相同的整数,最小整数为零,且S中任意4个互不相同的元素a,b,c,d满足a+b+c≠3d.反3平均问题是对k≥4,确定反3平均数η*(k)=min{max(S)|S是反3平均k-集}.给出反3平均数η*(k)的性质和若干界,以及可算法化的反3平均集构造方法,进而得到反3平均集的一些性质.

反3平均集;反3平均数;对偶集

1 基本概念

本文仅考虑整数集.包含k个整数的集合S叫做k集,S的最大元素和最小元素分别记为max(S)和min(S).记号[m,n]表示集合{m,m+1,m+2,…,n},其中m和n均为整数,且满足0≤m<n.我们提出以下问题:

反3平均问题 对任意的整数k≥4,一个反3平均k集S包含k个互不相同的整数,最小整数为零,且任意4个互不相同的整数a,b,c,d满足a+b+c≠3d.数η*(k)=min{max(S)|S是反3平均k-集}叫做反3平均数.反3平均问题是确定反3平均k集和反3平均数η*(k).

显然,反3平均k集不完全相同于Sidon集[1].已有许多关于集合的重要研究,如自相似集、独立集、多重分数分解以及集合的广义平均问题等[2-6].下面给出本文要用到的一些概念.

定义1 对于k≥4,如果一个整数k集合S中任意4个互不相同的整数a,b,c,d满足a+b+c≠3d,且min(S)=0,则称S为反3平均k集.称一个反3平均k集X是最佳的,如果max(X)=η*(k).

定义2 一个集T的对偶集T*定义为T*={M-x|x∈T},其中M=max(T)+min(T).如果T=T*,则称T为自对偶集.如果T≠T*,但存在T的一个最小r子集T′,使得T\T′是自对偶集,我们就说集T是r自对偶集.

集{0,1,2,3,5,6,7,8}是1个自对偶集.集合T={0,2,3,5,7,9,11,12}是2自对偶集,因为T′={2,11}是T的最小集合,使得T\T′={0,3,5,7,9,12}是自对偶集.对于k≥4,令Anti3(k)是全体反3平均k集的集合.易见,Anti3(k)为非空集合.例如,对每一个整数k≥4,集合Sk={2i-1-1|i∈[1,k]}是反3平均k集.反设Sk不是反3平均k集,则存在i,j,s,t∈[1,k],使得(2i-1-1)+(2j-1-1)+(2s-1-1)=3(2t-1-1).不妨设i<j<s,则2i-1(1+2j-i+2s-i)=3·2t-1,于是,得1+2j-i+2s-i=3· 2t-i,而这是一个矛盾的式子.

2 反3平均数的性质和界

为证明主要的定理,我们需要下列引理.

引理1

(1)一个非负整数集合是反3平均集当且仅当它的对偶集是反3平均集.

(2)设S是反3平均k集,则集合{sx+t|x∈S}也是反3平均k集,其中k≥4,s≥1及t≥0.

证明结论(1)必要性 取反3平均k集S={a1,a2,…,ak},k≥4.假设S的对偶集S*={bi=M-ai|ai∈S}不是反3平均k集,这里M=max(S).则有互不相同的bi,bj,bs,bt∈S*,使得bi+bj+bs=3bt,从而有互不相同的ai,aj,as,at∈S,使得(M-ai)+(M-aj)+(M-as)=3(M-at),即ai+aj+as=3at,这与S是反3平均k集矛盾.

充分性 注意到S是S*的对偶集,即S=(S*)*,所以充分性证明同上.

结论(2)可由反3平均k集的定义直接推出.

注1 根据引理1,如果基数|Anti3(k)|是奇数,则集合Anti3(k)至少包含一个自对偶集,这是因为在Anti3(k)中反3平均集和它们的对偶集成双成对地出现.

引理2

(1)对整数k≥4,η*(k)<η*(k+1);k≥6,k<η*(k)<η*(k+1).

(2)设m=k1+k2,其中k1,k2≥4,则η*(k1)+η*(k2)<η*(m).

证明(1)k≥6时,由反3平均数的定义可直接推得不等式η*(k)>k.k≥4时,假定集合S={b1,b2,…,bk+1}是最佳反3平均(k+1)集,其中bi<bk+1=η*(k+1),i∈[1,k].显然,集合S′=S\{bk+1}也是一个反3平均集,这是因为S′⊂S.所以η*(k)≤max(S′)<bk+1=η*(k+1).

(2)设S(m)={b1,b2,…,bk1,bk1+1,…,bm}是最佳反3平均m集,使得bi<bi+1(i∈[1,m-1])和bm=η*(m),其中m=k1+k2,k1,k2≥4.根据引理1,有反3平均k1集S1={b1,b2,…,bk1}和反3平均k2集S2={x-bk1+1|x∈S(m)\S1}.显然,η*(k1)≤bk1=max(S1),η*(k2)≤bm-bk1+1=max(S2).于是,有η*(k1)+η*(k2)≤bk1+bm-bk1+1<bm=η*(m),即结论(2)得证.

引理3 对一个固定的整数k≥6,如果η*(k)≤N,则对整数n≥2,有

证明根据引理2,显然有N≥k.令S1={bi|i∈[1,k]}是最佳反3平均k集,其中0=b1<b2<…<bk-1<bk=η*(k).对η*(nk)(k≥6)中的n≥2运用数学归纳法证明.

当n=2时,令M2=32-1(2N+1)-(N+2)=5N+1.有集合T2k=S1∪S2,其中S2={M2-bi|bi∈S1}.注意到T2k有2k个元素,且max(T2k)=M2.下面证明T2k是反3平均2k集.假设T2k不是反3平均集,也就是说,存在互不相同的xi,xj,xs,xt∈T2k,使得显然,根据引理1,不存在满足(2)式的互不相同的xi,xj,xs,xt∈S1,或者互不相同的xi,xj,xs,xt∈S2.

情形A1 在(2)式中,x1,xj,xs∈S1和xi∈S2.则有xi+xj+xs=3(M2-bi),其中bt∈S1.因而,得矛盾式15N+3=xi+xj+xs+3bt<6bk=6η*(k)≤6N.

情形A2 在(2)式中,xi,xj,xs∈S1和xt∈S2.则有xi+xj+(M2-bt)=3xt,其中bs∈S1.于是得到xi+xj+5N+1=3xt+bs<4bk=4η*(k)≤4N,这显然是错误的.

情形A3 在(2)式中,xi,xj∈S1和xs,xt∈S2.则有xi+xj+(M2-bs)=3(M2-bt),其中bs,bt∈S1.得到矛盾式10N+2+bs=2M2+bs=xi+xj+3bt<5bk=5η*(k)≤5N.

情形A4 在(2)式中,xi,xt∈S1和xj,xs∈S2.则有xi+(M2-bj)+(M2-bs)=3xt,其中bj,bs∈S1.因而,得到矛盾式10N+2+xi=2M2+xi=3xt+bj+bs<5bk=5η*(k)≤5N.

情形A5 在(2)式中,xi∈S1和xj,xs,xt∈S2.则有xi+(M2-bj)+(M2-bs)=3(M2-bt),其中bj,bs,bt∈S1.得到矛盾式5N+1+bj+bs=M2+bj+bs=xi+3bt<4bk=4η*(k)≤4N.

情形A6 在(2)式中,xt∈S1和xi,xj,xs∈S2.则有(M2-bi)+(M2-bj)+(M2-bs)=3xt,其中bi,bj,bs∈S1.然而,这会导致矛盾式15N+3=3M2=3xt+bi+bj+bs<6bk=6η*(k)≤6N.

上述讨论说明(2)式不成立,即对互不相同的xi,xj,xs,xt∈T2k,总有xi+xj+xs≠3xt.

在第(n-1)步中,有集合Sn-1={Mn-1-bi|bi∈S1},其中Mn-1=3n-2(2N+1)-(N+2),n>2.假定引理成立,也就是说(n-1)k集是反3平均集,且满足

情形B1 在xr+xp+xq=3xw中,有xr,xp,xq∈X和xw∈Sn.则有xr+xp+xq=3(Mn-bw),其中bw∈S1.所以3Mn=xr+xp+xq+3bw≤Mn-1+Mn-1-1+Mn-1-2+3N=3Mn-1-3+3N,即Mn≤Mn-1+N-1.于是,又有3n-1(2N+1)-(N+2)≤3n-2(2N+1)-(N+2)+N-1,这导致2·3n-2(2N+1)+1≤N(n≥3),矛盾.

情形B2 在xr+xp+xq=3xw中,有xr,xp,xw∈X和xq∈Sn.则有xr+xp+(Mn-bq)=3xw,其中bq∈S1.所以xr+xp+Mn=3xw+bq≤3Mn-1+N,于是xr+xp+3n-1(2N+1)-(N+2)≤3(3n-2(2N+1)-(N+2))+N,即xr+xp+N+4≤0.这显然是错误的.

情形B3 在xr+xp+xq=3xw中,有xr,xp∈X和xq,xw∈Sn.因此,对不相同的bq,bw∈S1,有xr+xp+(Mn-bq)=3(Mn-bw).从而有2Mn≤2Mn+bq=xr+xp+3bw≤Mn-1+Mn-1-1+3N=2Mn-1+3N-1,即2(3n-1(2N+1)-(N+2))≤2(3n-2(2N+1)-(N+2))+3N-1,进而导致矛盾式子3n-2(8N+4)+1≤3N(n≥3).

情形B4 在xr+xp+xq=3xw中,有xr,xw∈X和xp,xq∈Sn.因此,对互不相同的bp,bq∈S1,有xr+(Mn-bp)+(Mn-bq)=3xw.所以xr+2Mn=3xw+bp+bq≤3Mn-1+N+N-1,即xr+2(3n-1(2N+1)-(N+2))≤3(3n-2(2N+1)-(N+2))+2N-1,而这又导致矛盾的式子xr+3n-1(2N+1)+(N+2)+1≤2N(n≥3).

情形B5 在xr+xp+xq=3xw中,有xr∈X和xp,xq,xw∈Sn.因此,对互不相同的bp,bq,bw∈S1,有xr+(Mn-bp)+(Mn-bq)=3(Mn-bw),即Mn<Mn+bp+bq=xr+3bw≤Mn-1+3N,从而导致矛盾式子3n-2(4N+2)<3N(n≥3).

情形B6 在xr+xp+xq=3xw中,xw∈X和xr,xp,xq∈Sn.因此,对互不相同的br,bp,bq∈S1,有(Mn-br)+(Mn-bp)+(Mn-bq)=3xw,于是3Mn=3xw+br+bp+bq≤3Mn-1+N+N-1+N-2=3Mn-1+3N-3,而这导致矛盾式子Mn≤Mn-1+N-1.

根据归纳假设,我们证得Tnk是反3平均集.于是,有η*(nk)≤max(Tnk)=Mn.(1)式得证.

定理1 设整数k≥4和n≥0,则

证明当n=0时,不等式(3)成立.当n>0时,对k≥4,有η*(k)<η*(2n-1·k).根据引理3中的不等式(2),有

连续运用上面的递推不等式,可得

定理得证.

基于反3平均数η*(4)=3,η*(5)=4和不等式(3),有

3 反3平均集的构造

定理2 设S={bi|i∈[1,k]}是最佳反3平均k集,且0=b1<b2<…<bk-1<bk=η*(k),则有反3平均(2k)集U,使得max(U)=4bk-1,即η*(2k)≤4η*(k)-1.此外,当S是自对偶集时,U也是自对偶集.

证明注意到,k≥4,bk≥3.基于S,可构造集合T={3bk+bi-1|bi∈S}.下面证明集合U=S∪T是反3平均集.显然,max(U)=4bk-1.假设存在互不相同的xi,xj,xs,xt∈U,使得xi+xj+xs=3xt.

情形C1 若xi,xj,xs∈S和xt∈T,则有xi+xj+xs=3(3bk+bt-1),其中bt∈S.简化后得9bk=xi+xj+xs-3bt+3≤bk+bk-1+bk-2+3=3bk,于是6bk≤0,矛盾.

情形C2 若xi,xj,xt∈S和xs∈T,则有xi+xj+(3bk+bs-1)=3xt≤3bk,其中bs∈S.从而得到矛盾式子3≤xi+xj+bs≤1.

情形C3 若xi,xj∈S和xs,xt∈T,则有xi+xj+(3bk+bs-1)=3(3bk+bt-1),其中bs,bt∈S.简化后,有xi+xj+bs=6bk+3bt-2.如果bt≥b2≥1,则3bk>xi+xj+bs=6bk+3bt-2≥6bk+1,矛盾.如果bt<b2,即bt=0,又得6bk-2=xi+xj+bs<3bk.于是3bk<2,这显然是不可能的.

情形C4 若xi,xt∈S和xj,xs∈T,则有xi+(3bk+bj-1)+(3bk+bs-1)=3xt,其中bj,bs∈S.这又导致错误的式子6bk<xi+bj+bs+6bk-2=3xt≤3bk.

情形C5 若xi∈S和xj,xs,xt∈T,则有xi+(3bk+bj-1)+(3bk+bs-1)=3(3bk+bt-1),其中bj,bs,bt∈S.简化后,有3bk+3bt-1=xi+bj+bs.如果bt≥b2≥1,则3bk+2≤3bk+3bt-1=xi+bj+bs<3bk,矛盾.如果bt<b2,即bt=0,我们又得到错误的式子3bk-1=xi+bj+bs≤bk+bk-1+bk-2=3bk-3.

情形C6 若xt∈S和xi,xj,xs∈T,则有(3bk+bi-1)+(3bk+bj-1)+(3bk+bs-1)=3xt,其中bi,bj,bs∈S.于是,又得到一个矛盾的式子9bk≤9bk+bi+bj+bs-3=3xt≤3bk.

当S是自对偶集时,对每一个bi∈S,有bk-bi∈S.考察x∈U:

若x=bi∈S,则max(U)-bi=4bk-1-bi=3bk+(bk-bi)-1∈T⊂U;若x=3bk+bi-1∈T,有max(U)-(3bk+bi-1)=4bk-1-3bk-bi+1=bk-bi∈S⊂U.这说明U是自对偶集.

综上所述,U是反3平均集,所以有η*(2k)≤max(U)=4η*(k)-1.

定理3 设S={bi|i∈[1,k]}是反3平均k集,其中max(S)=bk;集合T={aj|j∈[1,m]}是反3平均m集,max(T)=am.

(1)当am≤bk时,存在反3平均(k+m)集U,使得max(U)=3bk+am.

(2)当am<bk<2am时,存在反3平均(k+m)集V,使得max(V)=5am+bk.

证明(1)当am≤bk时,我们构造一个新集合U=S∪T′,其中T′={3bk+aj|aj∈T}.显然,max(T)=3bk+am.下面证明U是反3平均(k+m)集.假设U不是反3平均集,则存在互不相同的xi,xj,xs,xt∈U,使得xi+xj+xs=3xt.

情形D1 若xi,xj,xs∈S和xt∈T′,则得xi+xj+xs=3(3bk+at),其中at∈T.简化后得9bk+3at=xi+xj+xs≤bk+bk-1+bk-2=3bk-3,即6bk+3at+3≤0,这显然是错误的.

情形D2 若xi,xj,xt≤S和xs∈T′,则有xi+xj+(3bk+as)=3xt,其中as∈T.而3xt≤3bk,因此,我们得到错误的式子xi+xj+as≤0.

情形D3 若xi,xj∈S和xs,xt∈T′,则有xi+xj+(3bk+as)=3(3bk+at),其中as,at∈T.简化后得到矛盾的式子6bk+3at=xi+xj+as<2bk+am≤3bk.

情形D4 若xi,xt∈S和xj,xs∈T′,则有xi+(3bk+aj)+(3bk+as)=3xt,其中aj,as∈T.进一步,xi+aj+as+6bk=3xt≤3bk,仍然矛盾.

情形D5 若xi∈S和xj,xs,xt∈T′,则xi+(3bk+aj)+(3bk+as)=3(3bk+at),其中aj,as,at∈T.简化后得到矛盾的式子9bk+3at=xi+aj+as+6bk<7bk+2am≤9bk.

情形D6 若xt∈S和xi,xj,xs∈T′,则(3bk+ai)+(3bk+aj)+(3bk+as)=3xt,其中ai,aj,as∈T.于是有9bk+ai+aj+as=3xt≤3bk,显然错误.

综上所述,U是反3平均(k+m)集,且max(U)=3bk+am.

(2)对am<bk<2am,构造集合V=T∪S′,其中S′={5am+bi|bi∈S},显然,max(V)=5am+bk.可用相同于结论(1)的证明方法证得:对互不相同的yi,yj,ys,yt∈V,有yi+yj+ys≠3yt.因此,V是反3平均(k+m)集,且max(V)=5am+bk.

例1 根据定理3,基于集合S1={0,1,2,4}和T1={0,1,2,3}可以产生一个反3平均8集U1={0,1,2,4,12,13,14,15};基于集合S2={0,1,3,5,6,7}和T2={0,1,2,3,4}能够产生一个反3平均11集U2={0,1,3,5,6,7,21,22,23,24,25}.

利用定理2和定理3的证明方法,可以得到下面的结论.

推论1 (1)对n>m≥4,有

(2)如果S是定理3中的反3平均自对偶k集,则U=S∪{3bk+x|x∈S}是反3平均自对偶(2k)集.

(3)设k=n+m,n>m≥4,如果对整数λ≥2,有η*(n)<(λ-1)η*(m),则

例2 基于反3平均自对偶4集S(4)={0,1,2,3},利用引理3和定理3的证明方法,我们可以构造一个反3平均自对偶8集S(8)={0,1,2,3,9,10,11,12}.为方便起见,称S(4)为根.那么,我们可以构造出以S(4)为根的无穷多个反3平均自对偶集

其中S(20·4)=S(4).由上面的(6)式可以导出

注意到,不等式(7)中的上界小于(4)式中第一个不等式的上界.

例3 集合S(5)={0,1,2,3,4}是最佳反3平均自对偶5集,利用定理3的证明方法,我们能够构造出以S(5)为根的无穷多个反3平均自对偶集.

其中S(20·5)=S(5).进而

易见,不等式(9)中的上界小于(4)式中第二个不等式的上界.

[1] FAN AIHUA,ZHANG YIPING.Local inequalities for sidon sums and their applications[J].Acta Mathematica Scientia,2005,25B:305-316.

[2] GUO HONGWEN,DENG AIJIAO.Multifractal decomposition of certain recursive sets without the open set condition[J].Acta Mathematica Scientia,2001,21B(3):369-374.

[3] HU DIHE.The structure and approximation of A S self-similar set[J].Acta Mathematica Scientia,2003,23B(2):201-207.

[4] YAO BING,YAO MING,CHENG HUI.On generalized antiaverage problem[J].Ars Combinatoria,2010,XCVI:145-157.

[5] YUAN JINJIANG.Independent-set-deletable factor-critical power graphs[J].Acta Mathematica Scientia,2006,26B(4):577-584.

[6] ZHANG XIAOQUI,LIU PANYAN.The regularity of random graph directed self-similar sets[J].Acta Mathematica Scientia,2004,24B(3):485-492.

Properties and construction of anti-3-average sets

ZHOU Yang-yang1,YAO Bing2,XU Jin1

(1.School of Electronics Engineering and Computer Science,Peking University,Beijing 100871,China;2.College of Mathematics and Statistics,Northwest Normal University,Lanzhou 730070,China)

For each integer k≥4,an anti-3-average k-set Sis a set having k nonnegative integers and the smallest one being zero such that no distinct a,b,c,d∈S holds a+b+c=3d.Anti-3-average problem is to find the anti-3-average numberη*(k)=min{max(S)|Sis an anti-3-average k-set}.Some properties and bounds ofη*(k)are obtained,and some methods for constructing larger anti-3-average sets are provided.

anti-3-average set;anti-3-average number;dual set

O 157.5 [学科代码] 110·7470 [

] A

(责任编辑:陶理)

1000-1832(2015)01-0012-05

10.16163/j.cnki.22-1123/n.2015.01.003

2013-06-18

国家自然科学基金资助项目(61163054;61163037;61363060).

周洋洋(1991—),女,硕士研究生,主要从事图与组合优化研究.

猜你喜欢

上界对偶平均数
融合有效方差置信上界的Q学习智能干扰决策算法
S-Nekrasov矩阵的的上界估计
R2上对偶Minkowski问题的可解性
对偶延迟更新风险模型的占位时
一个三角形角平分线不等式的上界估计
配之以对偶 赋之以精魂
一道经典不等式的再加强
不一样的平均数
关注加权平均数中的“权”
平均数应用举隅