两道组合题思路分析
【注】为方便复制编辑，特提供纯文本文档如下：
2016年秋季上海新星数学奥林匹克试题，新颖有趣，且不偏不怪，难度适中。尤其是最后两道组合题，其探索解答的思路非常自然，堪作数学奥林匹克活动的良好素材。故此，今对后面两题的解答作些思路分析，请大家指正！
第5题、设n≥2，A1，A2，…，At是X={1，2，…，n}的所有子集的任一个排列，求
的最大值，其中t=2n，At=A1。
【题感】从目标看，求S的最大值，需建立关于S的不等式“S≤…”。但其S的表达式非常复杂，且无法直接“求和”化简，自然想到先将复杂的表达式通过放缩变形，使其变成容易“求和”的表现形式。这类似于代数中Σ（1/k2）不易“求和”，先将其放缩到Σ（1/k（k-1）），使其变得易于“求和”。
【通项放缩】S的通项为|Ai∩Ai+1|·|Ai∪Ai+1|，它的一般形式为|A∩B|·|A∪B|。注意到Σ|A|、Σ|B|可求（其中A、B跑遍）X的所有子集，自然想到将|A∩B|·|A∪B|放大到f（|A|，|B|）的形式。即建立如下不等式：
|A∩B|·|A∪B|≤f（|A|，|B|）。
【结构联想】注意到不等式左边是“二次式”，所以想到右边也是“二次式”，再注意到Σ|A|2、Σ|B|2也可求，于是将不等式变为
|A∩B|·|A∪B|≤f（|A|2，|B|2）。
先猜想右边是最简单形式的二次对称式|A|2+|B|2，不等式变为
|A∩B|·|A∪B|≤|A|2+|B|2。
【调整参数】但为了等号成立使不等式达到最优，应引入平移、伸缩的调整参数a、b，进一步将不等式变为
|A∩B|·|A∪B|≤a（|A|2+|B|2）+b。……（*）
下面确定参数a、b。为此，令|A\B|=x，|B\A|=y，|A∩B|=z，则不等式（*）化为
（x+y+z）z≤a（x+z）2+ a（y+z）2+b，
ax2+ ay2+（2a-1）（z2+xz+yz）+b≥0，
期望不等式为简单形式，取2a-1=0，则不等式变为
x2+y2+2b≥0。
上式恒成立的充要条件是min（x2+y2）+2b≥0。
由于x、y∈N，且x、y不全为0（A≠B），于是min（x2+y2）=1，所以不等式变成1+2b≥0。为使等号成立，取2b=-1即可。
所以，我们有2|A∩B|·|A∪B|≤（|A|2+|B|2）-1，其中等号在{x，y}={0，1}时成立，此时A、B恰相差一个元素（A、B中的一个是另一个的子集，且元素个数相差1）。
【上界估计】利用上述不等式，显然有
考察S'=Σi=1t|Ai|2，对1≤k≤n，使|Ai|=k的子集Ai有Cnk个，于是
S'=Σi=1n（k2Cnk）=（n2+n）2n-2，
所以，2S≤2S'-t=（n2+n）2n-1-2n，得S≤（n2+n-2）2n-2。
等号在Ai与Ai+1（1≤i≤t）都恰好相差一个元素时成立，这是可能的（一个早期的构造问题，不赘述），故S的最大值为（n2+n-2）2n-2。
第6题、设A1，A2，…，A13是太空中的13颗新星，对任意i、j（1≤i 【题感】此题有明显的图论色彩（当然无需用到图论知识，只是用图描述更直观而已），如果用n个点A1，A2，…，An代表n颗新星（n=13），则题中的路径恰好是一个“哈氏”圈。再注意到条件“Ai、Aj之间的通行花费f（i，j）个太空币，这可用对边AiAj赋值f（i，j）来表示，称为该边的“权”。那么，解题的目标是，恰当对各边都赋一个“权”，使n阶完全图中每个“哈氏”圈各边的“权和”都为2017。 【逐步逼近】这属于一个“赋值型”的构造问题（构造一种赋值方式），其赋值的条件很强，我们将其分解为3个部分来逐步实现： （1）n阶完全图中每个“哈氏”圈各边的“权和”都相等； （2）上述相等的“权和”为2017； （3）各边的“权”互异。 【构造拟对象】先构造满足条件（1）的拟赋值方案。要使每个“哈氏”圈各边的“权和”都相等，自然想到利用“哈氏”圈的共同特征：通过“各顶点”Ai各一次。 由此想到将边AiAj的“权”分解为顶点Ai、Aj的“权”，即定义f（i，j）=g（ai，aj），其中ai是顶点Ai的“权”，则“哈氏”圈各边的“权和”变成“哈氏”圈各顶点的“权和”：G（a1，a2，…，an）。 相对于每个“哈氏”圈，G（a1，a2，…，an）为常数的一个充分条件是，G（a1，a2，…，an）是关于a1，a2，…，an的对称式。这又只需前面的“分解函数”g（ai，aj）关于ai、aj对称，最简单的形式是g（ai，aj）= ai+aj。 此时，每个“哈氏”圈的权和：G（a1，a2，…，an）=2（a1+a2+…+an）。 现在来改进“拟对象”，使其满足（2）。由于2（a1+a2+…+an）为偶数，而2017为奇数，两者不可能相等，需要修改“分解函数”g（ai，aj）的定义，但保持其仍然关于ai、aj对称。 【修正参数】这有两个常见方案，一是引入“平移型”修正参数；二是引入“伸缩型”修正参数。 如果引入“伸缩型”修正参数，定义g（ai，aj）=k（ai+aj），则 G（a1，a2，…，an）=2k（a1+a2+…+an）。 为了使上述值不是偶数，取2k=1，此时， g（ai，aj）=（ai+aj）/2， G（a1，a2，…，an）=a1+a2+…+an。 现在，要使（2）成立，只需a1+a2+…+an=2017。但注意到（ai+aj）/2∈N，所以ai、aj同奇偶，又a1+a2+…+an=2017为奇数，所以取所有ai为奇数。 最后适当选取奇数a1，a2，…，an，使a1+a2+…+an=2017，且各ai+aj（1≤i 【充分条件】注意到这样的事实：对于4个互异的数：ap 于是，设选取的奇数为1=a1 实际上，假设有某两个数的和与另两数的和相等。设4个数为ap 下面依据（*）来构造奇数1=a1 显然，为保证最后的2017-（a1+a2+…+an-1）=an≥an-1+an-2，应使前面的数尽可能小，即a1+a2+…+an-1尽可能小。 此外，为了使ai为奇数，不能取ai=ai-1+ai-2，于是前面的数都取ai=ai-1+ai-2+1（2≤i≤n-1），这样，前面n-1=12个数依次为 1，3，5，9，15，25，41，67，109，177，287，465， 这12个数的和1204，最后取a13=2017-1204=813，则813>287+465合乎（*）的要求。 综上所述，将上述13个数标在新星上，然后令f（i，j）为Ai、Aj上标数的算术平均值，则各f（i，j）（1≤i 如果引入“平移型”修正参数，则定义g（ai，aj）=ai+aj+d，其中d为奇数。为了“权和”不超过2017，可取d<0，但为了使ai+aj+d为正整数，想到取d=-1。以下仿上面（*）的分析，不难知道（a1，a2，…，a13）=（1，2，3，5，8，13，21，34，55，89，144，233，407）合乎要求，这正是原解答的构造。
最新文章
-
揭秘：伤寒汗出病解的方式有哪些
6分钟前 -
洗髓修炼中的：找病、攻病、翻病、愈病！
21分钟前 -
（原创）颤证的经方治疗案。。。
27分钟前 -
中医教你：看指甲上的月牙诊病
39分钟前 -
中药方论（24）
42分钟前 -
仅一味中药就可以降血糖 ，一味中药的单药方！
44分钟前 -
解郁安神颗粒：抑郁症、焦虑症都是因为肝的疏泄功能出现了失调
55分钟前 -
有一种痛苦叫牙疼，有种止疼药叫艾灸！收藏起来，以备不时之需！
1小时前
有话要说...