周洋洋，姚 兵，許 進(jìn)

（1.北京大學(xué)信息科學(xué)技術(shù)學(xué)院，北京100871；2.西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅蘭州730070）

反3平均集的性質(zhì)與構(gòu)造

周洋洋1，姚 兵2，許 進(jìn)1

（1.北京大學(xué)信息科學(xué)技術(shù)學(xué)院，北京100871；2.西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅蘭州730070）

一個(gè)反3平均k－集包含k個(gè)互不相同的整數(shù)，最小整數(shù)為零，且S中任意4個(gè)互不相同的元素a，b，c，d滿足a＋b＋c≠3d.反3平均問題是對k≥4，確定反3平均數(shù)η＊（k）＝min｛max（S）｜S是反3平均k－集｝.給出反3平均數(shù)η＊（k）的性質(zhì)和若干界，以及可算法化的反3平均集構(gòu)造方法，進(jìn)而得到反3平均集的一些性質(zhì).

反3平均集；反3平均數(shù)；對偶集

1 基本概念

本文僅考慮整數(shù)集.包含k個(gè)整數(shù)的集合S叫做k集，S的最大元素和最小元素分別記為max（S）和min（S）.記號［m，n］表示集合｛m，m＋1，m＋2，…，n｝，其中m和n均為整數(shù)，且滿足0≤m＜n.我們提出以下問題：

反3平均問題 對任意的整數(shù)k≥4，一個(gè)反3平均k集S包含k個(gè)互不相同的整數(shù)，最小整數(shù)為零，且任意4個(gè)互不相同的整數(shù)a，b，c，d滿足a＋b＋c≠3d.數(shù)η＊（k）＝min｛max（S）｜S是反3平均k－集｝叫做反3平均數(shù).反3平均問題是確定反3平均k集和反3平均數(shù)η＊（k）.

顯然，反3平均k集不完全相同于Sidon集［1］.已有許多關(guān)于集合的重要研究，如自相似集、獨(dú)立集、多重分?jǐn)?shù)分解以及集合的廣義平均問題等［2－6］.下面給出本文要用到的一些概念.

定義1 對于k≥4，如果一個(gè)整數(shù)k集合S中任意4個(gè)互不相同的整數(shù)a，b，c，d滿足a＋b＋c≠3d，且min（S）＝0，則稱S為反3平均k集.稱一個(gè)反3平均k集X是最佳的，如果max（X）＝η＊（k）.

定義2 一個(gè)集T的對偶集T＊定義為T＊＝｛M－x｜x∈T｝，其中M＝max（T）＋min（T）.如果T＝T＊，則稱T為自對偶集.如果T≠T＊，但存在T的一個(gè)最小r子集T′，使得T＼T′是自對偶集，我們就說集T是r自對偶集.

集｛0，1，2，3，5，6，7，8｝是1個(gè)自對偶集.集合T＝｛0，2，3，5，7，9，11，12｝是2自對偶集，因?yàn)門′＝｛2，11｝是T的最小集合，使得T＼T′＝｛0，3，5，7，9，12｝是自對偶集.對于k≥4，令A(yù)nti3（k）是全體反3平均k集的集合.易見，Anti3（k）為非空集合.例如，對每一個(gè)整數(shù)k≥4，集合Sk＝｛2i－1－1｜i∈［1，k］｝是反3平均k集.反設(shè)Sk不是反3平均k集，則存在i，j，s，t∈［1，k］，使得（2i－1－1）＋（2j－1－1）＋（2s－1－1）＝3（2t－1－1）.不妨設(shè)i＜j＜s，則2i－1（1＋2j－i＋2s－i）＝3·2t－1，于是，得1＋2j－i＋2s－i＝3· 2t－i，而這是一個(gè)矛盾的式子.

2 反3平均數(shù)的性質(zhì)和界

為證明主要的定理，我們需要下列引理.

引理1

（1）一個(gè)非負(fù)整數(shù)集合是反3平均集當(dāng)且僅當(dāng)它的對偶集是反3平均集.

（2）設(shè)S是反3平均k集，則集合｛sx＋t｜x∈S｝也是反3平均k集，其中k≥4，s≥1及t≥0.

證明結(jié)論（1）必要性 取反3平均k集S＝｛a1，a2，…，ak｝，k≥4.假設(shè)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＊）＊，所以充分性證明同上.

結(jié)論（2）可由反3平均k集的定義直接推出.

注1 根據(jù)引理1，如果基數(shù)｜Anti3（k）｜是奇數(shù)，則集合Anti3（k）至少包含一個(gè)自對偶集，這是因?yàn)樵贏nti3（k）中反3平均集和它們的對偶集成雙成對地出現(xiàn).

引理2

（1）對整數(shù)k≥4，η＊（k）＜η＊（k＋1）；k≥6，k＜η＊（k）＜η＊（k＋1）.

（2）設(shè)m＝k1＋k2，其中k1，k2≥4，則η＊（k1）＋η＊（k2）＜η＊（m）.

證明（1）k≥6時(shí)，由反3平均數(shù)的定義可直接推得不等式η＊（k）＞k.k≥4時(shí)，假定集合S＝｛b1，b2，…，bk＋1｝是最佳反3平均（k＋1）集，其中bi＜bk＋1＝η＊（k＋1），i∈［1，k］.顯然，集合S′＝S＼｛bk＋1｝也是一個(gè)反3平均集，這是因?yàn)镾′?S.所以η＊（k）≤max（S′）＜bk＋1＝η＊（k＋1）.

（2）設(shè)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.根據(jù)引理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），即結(jié)論（2）得證.

引理3 對一個(gè)固定的整數(shù)k≥6，如果η＊（k）≤N，則對整數(shù)n≥2，有

證明根據(jù)引理2，顯然有N≥k.令S1＝｛bi｜i∈［1，k］｝是最佳反3平均k集，其中0＝b1＜b2＜…＜bk－1＜bk＝η＊（k）.對η＊（nk）（k≥6）中的n≥2運(yùn)用數(shù)學(xué)歸納法證明.

當(dāng)n＝2時(shí)，令M2＝32－1（2N＋1）－（N＋2）＝5N＋1.有集合T2k＝S1∪S2，其中S2＝｛M2－bi｜bi∈S1｝.注意到T2k有2k個(gè)元素，且max（T2k）＝M2.下面證明T2k是反3平均2k集.假設(shè)T2k不是反3平均集，也就是說，存在互不相同的xi，xj，xs，xt∈T2k，使得顯然，根據(jù)引理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，這顯然是錯(cuò)誤的.

情形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.然而，這會導(dǎo)致矛盾式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，這導(dǎo)致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.這顯然是錯(cuò)誤的.

情形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，進(jìn)而導(dǎo)致矛盾式子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，而這又導(dǎo)致矛盾的式子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，從而導(dǎo)致矛盾式子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，而這導(dǎo)致矛盾式子Mn≤Mn－1＋N－1.

根據(jù)歸納假設(shè)，我們證得Tnk是反3平均集.于是，有η＊（nk）≤max（Tnk）＝Mn.（1）式得證.

定理1 設(shè)整數(shù)k≥4和n≥0，則

證明當(dāng)n＝0時(shí)，不等式（3）成立.當(dāng)n＞0時(shí)，對k≥4，有η＊（k）＜η＊（2n－1·k）.根據(jù)引理3中的不等式（2），有

連續(xù)運(yùn)用上面的遞推不等式，可得

定理得證.

基于反3平均數(shù)η＊（4）＝3，η＊（5）＝4和不等式（3），有

3 反3平均集的構(gòu)造

定理2 設(shè)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.此外，當(dāng)S是自對偶集時(shí)，U也是自對偶集.

證明注意到，k≥4，bk≥3.基于S，可構(gòu)造集合T＝｛3bk＋bi－1｜bi∈S｝.下面證明集合U＝S∪T是反3平均集.顯然，max（U）＝4bk－1.假設(shè)存在互不相同的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.這又導(dǎo)致錯(cuò)誤的式子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，我們又得到錯(cuò)誤的式子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.于是，又得到一個(gè)矛盾的式子9bk≤9bk＋bi＋bj＋bs－3＝3xt≤3bk.

當(dāng)S是自對偶集時(shí)，對每一個(gè)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 設(shè)S＝｛bi｜i∈［1，k］｝是反3平均k集，其中max（S）＝bk；集合T＝｛aj｜j∈［1，m］｝是反3平均m集，max（T）＝am.

（1）當(dāng)am≤bk時(shí)，存在反3平均（k＋m）集U，使得max（U）＝3bk＋am.

（2）當(dāng)am＜bk＜2am時(shí)，存在反3平均（k＋m）集V，使得max（V）＝5am＋bk.

證明（1）當(dāng)am≤bk時(shí)，我們構(gòu)造一個(gè)新集合U＝S∪T′，其中T′＝｛3bk＋aj｜aj∈T｝.顯然，max（T）＝3bk＋am.下面證明U是反3平均（k＋m）集.假設(shè)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，這顯然是錯(cuò)誤的.

情形D2 若xi，xj，xt≤S和xs∈T′，則有xi＋xj＋（3bk＋as）＝3xt，其中as∈T.而3xt≤3bk，因此，我們得到錯(cuò)誤的式子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.進(jìn)一步，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，顯然錯(cuò)誤.

綜上所述，U是反3平均（k＋m）集，且max（U）＝3bk＋am.

（2）對am＜bk＜2am，構(gòu)造集合V＝T∪S′，其中S′＝｛5am＋bi｜bi∈S｝，顯然，max（V）＝5am＋bk.可用相同于結(jié)論（1）的證明方法證得：對互不相同的yi，yj，ys，yt∈V，有yi＋yj＋ys≠3yt.因此，V是反3平均（k＋m）集，且max（V）＝5am＋bk.

例1 根據(jù)定理3，基于集合S1＝｛0，1，2，4｝和T1＝｛0，1，2，3｝可以產(chǎn)生一個(gè)反3平均8集U1＝｛0，1，2，4，12，13，14，15｝；基于集合S2＝｛0，1，3，5，6，7｝和T2＝｛0，1，2，3，4｝能夠產(chǎn)生一個(gè)反3平均11集U2＝｛0，1，3，5，6，7，21，22，23，24，25｝.

利用定理2和定理3的證明方法，可以得到下面的結(jié)論.

推論1 （1）對n＞m≥4，有

（2）如果S是定理3中的反3平均自對偶k集，則U＝S∪｛3bk＋x｜x∈S｝是反3平均自對偶（2k）集.

（3）設(shè)k＝n＋m，n＞m≥4，如果對整數(shù)λ≥2，有η＊（n）＜（λ－1）η＊（m），則

例2 基于反3平均自對偶4集S（4）＝｛0，1，2，3｝，利用引理3和定理3的證明方法，我們可以構(gòu)造一個(gè)反3平均自對偶8集S（8）＝｛0，1，2，3，9，10，11，12｝.為方便起見，稱S（4）為根.那么，我們可以構(gòu)造出以S（4）為根的無窮多個(gè)反3平均自對偶集

其中S（20·4）＝S（4）.由上面的（6）式可以導(dǎo)出

注意到，不等式（7）中的上界小于（4）式中第一個(gè)不等式的上界.

例3 集合S（5）＝｛0，1，2，3，4｝是最佳反3平均自對偶5集，利用定理3的證明方法，我們能夠構(gòu)造出以S（5）為根的無窮多個(gè)反3平均自對偶集.

其中S（20·5）＝S（5）.進(jìn)而

易見，不等式（9）中的上界小于（4）式中第二個(gè)不等式的上界.

［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 ［學(xué)科代碼］ 110·7470 ［

］ A

（責(zé)任編輯：陶理）

1000－1832（2015）01－0012－05

10.16163／j.cnki.22－1123／n.2015.01.003

2013－06－18

國家自然科學(xué)基金資助項(xiàng)目（61163054；61163037；61363060）.

周洋洋（1991—），女，碩士研究生，主要從事圖與組合優(yōu)化研究.