反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—），女，碩士研究生，主要從事圖與組合優化研究.