反3平均集的性质与构造

周洋洋，姚 兵，许 进

（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—），女，硕士研究生，主要从事图与组合优化研究.