兩道組合題思路分析
【注】為方便複制編輯，特提供純文本文檔如下：
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）合乎要求，這正是原解答的構造。
最新文章
-
看墳地風水順口溜與墓地風水口訣100條
3小時前 -
教你把脈知男女
4小時前 -
鄧中甲方劑學講稿—第四章清熱劑—清營涼血—犀角地黃湯
4小時前 -
北京頤和園：養雲軒探秘
4小時前 -
觀點引流大揭秘：如何用鮮明觀點，吸引高客單價用戶
4小時前 -
李辛最新采訪 | 孩子身心問題背後的原因（下）
4小時前 -
針家心悟：針灸如何取穴（純幹貨）
4小時前 -
有哪些非常實用的職場道理，是當了領導以後才明白的
5小時前
熱門文章
-
威士忌高階關于 OB 與 IB，一次給你說透！
1天前 -
為什麼五點鐘要起床答案讓人吃驚！（現在知道還不晚）
1周前 -
美麗中國-2870：中國最大的内陸河，塔裡木河
3天前 -
老張老李侃門球之140篇
3天前 -
這個穴位可以治療多種胃痛腹痛，還可以減肥
1周前 -
診餘雜記（師傳經驗）
5天前 -
二十四山開門放水作竈真訣開門放水作竈直訣——子山
3天前 -
門球技巧 隻需五個字讓你打好門球
3天前
有話要說...