31屆imo組合試題及精準答案

31屆imo組合試題及精準答案考試時間：______分鐘總分：______分姓名：______第一題設集合A={1,2,3,...,n},n≥3。定義A上的一個二元關系R如下：對于任意a,b∈A，若a-b是3的倍數，則(a,b)∈R。試判斷R是否為等價關系，并說明理由。第二題在一個無向圖中，每個頂點的度數均為3。若該圖有12個頂點，問是否存在一個頂點刪除方案，使得余下的圖中包含一個3個頂點的團（即一個三角形）？若存在，請給出一個構造方法；若不存在，請證明之。第三題將一個4x4的棋盤的每個方格都染成紅色或藍色。求證：無論如何染色，總存在一個2x2的正方形子板，其中包含顏色相同的四個方格。第四題考慮以下數學游戲：游戲者A和B輪流在集合{1,2,3,...,2n}中選擇一個數，選擇的數不能與之前已選中的數相同。當游戲者無法進行選擇時（即所有數都被選完），該游戲者輸掉比賽。游戲開始時，A先手。若n=5，游戲者A是否存在一個必勝策略？請說明理由。第五題對于給定的正整數k和n(n≥k)，定義H(k,n)為所有滿足以下條件的k元組(a?,a?,...,a?)的個數：每個a?∈{1,2,...,n}，且a?≤a?≤...≤a?。例如，當k=3,n=4時，H(3,4)=4，因為滿足條件的3元組有(1,1,1),(1,1,2),(1,2,2),(1,2,3)。(1)求H(2,n)和H(3,n)的表達式。(2)證明：對于任意正整數k和n，H(k,n)=C(n+k-1,k)，其中C(m,r)表示從m個不同元素中取出r個元素的組合數。第六題在一個圓周上放置n個棋子，編號為1,2,...,n。游戲者A和B輪流進行操作，每次操作可以選擇一個棋子，并將其沿順時針或逆時針方向移動任意步數（可以移動到任意未被占據的位置，前提是該位置已被占據則不允許），然后取下該棋子。最后一個無法進行操作的玩家輸掉比賽。游戲開始時，A先手。若n=6，游戲者A是否存在一個必勝策略？請說明理由。第七題給定一個n邊形（n≥3），其內部不含任何對角線。在它的所有頂點和邊中，選取一部分點，使得：①沒有三個點共線；②任何兩個相鄰的頂點之間，或者這兩點所在的邊（如果它們是相鄰頂點）上，都至少有一個被選取的點。求證：被選取的點至少有?n/2?個。第八題設S={1,2,...,2n}。一個S的子集T被稱為“完美集”當且僅當對于S中的任意兩個不同的元素a,b∈T，都有a+b≠c對于T中的所有c∈T成立。求證：S中存在一個大小為n的完美集。試卷答案第一題解：R不是等價關系。理由：R具有自反性和對稱性。但R不具有傳遞性。反例：取a=1,b=4,c=7。則1-4=-3是3的倍數，4-7=-3也是3的倍數，所以(1,4)∈R且(4,7)∈R。但1-7=-6是3的倍數，所以(1,7)?R。因此，R不是等價關系。第二題解：不存在。證明：假設存在一個頂點刪除方案，使得余下的圖中包含一個3個頂點的團。設余下的團為{u,v,w}。由于原圖中每個頂點的度數為3，且原圖有12個頂點，所以原圖中每個頂點都至少與另外2個頂點相鄰。在刪除操作后，u,v,w仍然是相互連接的（形成團），這意味著在刪除之前，u,v,w必須兩兩相鄰（即每對頂點之間都有邊相連）。考慮原圖中與u相鄰的另外兩個頂點，設為x和y。由于u,v,w形成團，所以u,v,w之間都有邊。同樣，v和w的相鄰頂點中必須包含u和另一個頂點（設為v'和w'）。w的相鄰頂點中必須包含u和另一個頂點（設為w''）。此時，頂點總數已超過12，或者頂點x,y,v',w',w''中存在重復，矛盾。因此，不存在這樣的頂點刪除方案。第三題解：設棋盤的行從上到下編號為1到4，列從左到右編號為1到4。考察棋盤上位于第1行和第2行的8個方格，將它們分為4組：((1,1),(2,2)),((1,2),(2,1)),((1,3),(2,4)),((1,4),(2,3))。根據鴿巢原理，這4組中至少有一組中的兩個方格顏色相同。若(1,1)和(2,2)顏色相同，則2x2子板{(1,1),(1,2),(2,1),(2,2)}中有四個同色方格。若(1,1)和(2,2)顏色不同，則它們分別設為顏色A和顏色B。考慮第3行和第4行的8個方格，同樣將它們分為4組：((3,1),(4,2)),((3,2),(4,1)),((3,3),(4,4)),((3,4),(4,3))。由于第1行和第2行中存在同色方格對，結合第3行和第4行，必有同色2x2子板。具體來說，若第1行和第2行同色的方格對位于第j列(j=1,2,3,4)，則第3行和第4行中位于第j列的兩個方格必然與第1行和第2行中對應位置的方格顏色不同（否則會形成同色2x2子板）。因此，第3行和第4行中與第j列不重合的另外兩列(j'≠j)必然存在同色方格對。設這兩列為k和l。則2x2子板{(1,k'),(2,k'),(1,l'),(2,l')}中有四個同色方格。因此，無論如何染色，總存在一個2x2的正方形子板，其中包含顏色相同的四個方格。第四題解：A存在必勝策略。采用反向歸納法。當n=1時，A只能選1，B選2，A輸。當n=2時，A選1，B選2或3，A輸；A選2，B選1或3，A輸；A選3，B選1或2，A輸。A無勝策。當n≥3時，A首選3。若B選1，則集合變為{2,4,...,2n}。B必須選一個奇數（否則A可以選一個偶數使B無數可選），設B選2k-1(1<k≤n)。此時集合為{2,4,...,2k-2,2k+1,...,2n}。集合大小為2n-1。B為了獲勝，需要迫使A在下一步面對一個類似n=2的情況。B可以選擇2k+1。此時集合為{2,4,...,2k-2,2k+2,...,2n}。A的選擇將迫使B在下一步面對n=2的情況。例如，若A選2k，B選2k+2；若A選2k-2，B選2k+2。總之，無論A如何選擇，B總能下一步選一個偶數，使得A面對一個包含2n-1個數的集合{2,4,...,2k-2,2k+2,...,2n}，其中包含奇數2k-1和2k+1。這個集合可以表示為{2j|1≤j≤k-1,j+k≥2}∪{2j|k+1≤j≤n}。大小為(k-1)+(n-k)=n-1。A只能選一個偶數，設為2m。B可以選2m+2（如果存在）。若2m+2≤2n，則B選2m+2。集合變為{2,4,...,2m-2,2m+2,...,2n}，大小為n-2。B迫使A面對n=2的情況。若2m+2>2n，則B選2m-2。集合變為{2,4,...,2m-4,2m,...,2n}，大小為n-2。B同樣迫使A面對n=2的情況。因此，當n≥3時，B總能迫使A在下一步面對一個n=2的情況。而我們已經知道當n=2時A無勝策，這意味著當n≥3時A有勝策。因此，A存在必勝策略，即第一步選3。第五題解：(1)H(2,n)=n+1。滿足條件的2元組(a?,a?)滿足a?≤a?且a?,a?∈{1,2,...,n}。可以按a?從小到大枚舉：當a?=1時，a?只能取1，共1個；當a?=2時，a?可以取1或2，共2個；...；當a?=n時，a?可以取1,2,...,n，共n個。總和為1+2+...+n=n(n+1)/2。但也可以這樣考慮：將{1,2,...,n}放入n+1個位置（n個數的位置加上一個“小于所有數”的虛擬位置和一個“大于所有數”的虛擬位置），要求每個數占據一個位置，且所有數從左到右排列。從n+1個位置中選擇2個位置放置兩個數，有C(n+1,2)=(n+1)n/2種方法。這與H(2,n)的值n(n+1)/2相同。因此H(2,n)=n+1。H(3,n)=n+n-1+n-2+...+1=n(n+1)(n+2)/6。滿足條件的3元組(a?,a?,a?)滿足a?≤a?≤a?且a?,a?,a?∈{1,2,...,n}。可以按a?從小到大枚舉：當a?=1時，a?=a?=a?=1，共1個；當a?=2時，a?,a?∈{1,2}，共C(2,2)=1個；當a?=3時，a?,a?∈{1,2,3}，共C(3,2)=3個；...；當a?=n時，a?,a?∈{1,2,...,n}，共C(n,2)=n(n-1)/2個。總和為1+1+3+...+n(n-1)/2=ΣC(k,2)=C(n+1,3)=n(n+1)(n+2)/6。同樣，也可以將{1,2,...,n}放入n+2個位置（n個數的位置加上兩個虛擬位置），要求每個數占據一個位置，且所有數從左到右排列。從n+2個位置中選擇3個位置放置三個數，有C(n+2,3)=n(n+1)(n+2)/6種方法。因此H(3,n)=n(n+1)(n+2)/6。(2)證明：將{1,2,...,n}放入n+k-1個位置（n個數的位置加上k-1個虛擬位置），要求每個數占據一個位置，且所有數從左到右排列。從n+k-1個位置中選擇k個位置放置k個數，有C(n+k-1,k)種方法。每一種選擇對應一個滿足a?≤a?≤...≤a?且a?∈{1,2,...,n}的k元組(a?,a?,...,a?)。反之，任何一個滿足條件的k元組(a?,a?,...,a?)都唯一確定了一種將{1,2,...,n}放入n+k-1個位置的方法，方法是：在n+k-1個位置上，將a?放在第1個位置，a?放在第a?+1個位置，...，a?放在第a???+1個位置，其余位置放置虛擬標記。因此，H(k,n)=C(n+k-1,k)。第六題解：A存在必勝策略。采用反向歸納法。當n=1時，A選1，B無法移動，A勝。當n=2時，A選1，B選2，A無法移動，A勝；A選2，B選1，A無法移動，A勝。A總是勝。當n=3時，A選1，B選2或3，A選另一個未被選的，B無法移動，A勝；A選2，B選1或3，A選另一個未被選的，B無法移動，A勝；A選3，B選1或2，A選另一個未被選的，B無法移動，A勝。A總是勝。當n=4時，A選1，B選2,3,或4。若B選2，A選3，B選4，A選2，B無法移動，A勝；若B選2，A選3，B選1或4，A選2，B無法移動，A勝；若B選2，A選4，B選1或3，A選3，B無法移動，A勝；若B選3，A選1,2,或4。若B選1,4，A選2，B選3，A選1，B無法移動，A勝；若B選1,4，A選2，B選3，A選4，B無法移動，A勝；若B選1,4，A選4，B選2或3，A選1，B無法移動，A勝；若B選2,4，A選1,3。若B選1,3，A選2，B無法移動，A勝；若B選1,3，A選4，B選2，A選1，B無法移動，A勝；若B選2,4，A選1,3。若B選1,3，A選4，B選2，A選1，B無法移動，A勝；若B選2,4，A選3，B選1，A選2，B無法移動，A勝。當n=5時，A采用如下策略：首先選3。若B選1，則集合為{2,4,5}。B必須選一個奇數，設為2k-1(1<k≤3)。此時集合為{2,4,5}中去掉2k-1，剩下{2,4,5}\{2k-1}。B的選擇將迫使A在下一步面對一個類似n=3的情況。例如，若B選1，則集合為{2,4,5}，A選2，B選4，A選5，B無法移動，A勝；若B選1，A選2，B選5，A選4，B無法移動，A勝；若B選1，A選5，B選2，A選4，B無法移動，A勝。若B選2，則集合為{1,4,5}，A選1，B選4，A選5，B無法移動，A勝；若B選2，A選1，B選5，A選4，B無法移動，A勝。若B選4，則集合為{1,2,5}，A選1，B選2，A選5，B無法移動，A勝；若B選4，A選1，B選5，A選2，B無法移動，A勝。若B選5，則集合為{1,2,4}，A選1，B選2，A選4，B無法移動，A勝；若B選5，A選1，B選2，A選4，B無法移動，A勝。總之，當B在第一步選1后，A總能迫使B在下一步面對一個n=3的情況，而我們已經知道當n=3時A總是勝。若B不選1，則B選2,4,或5。若B選2，集合為{1,3,4,5}，A選1，B選3,4,或5。若B選3，集合為{1,2,4,5}，A選2，B選4或5。若B選4，集合為{1,2,3,5}，A選2，B選3或5。若B選5，集合為{1,2,3,4}，A選2，B選3或4。若A選2后，B選4或5，集合為{1,3}或{1,3}，A選1，B無法移動，A勝。若A選2后，B選3，集合為{1,4,5}，A選1，B選4或5。若B選4，集合為{1,5}，A選1，B無法移動，A勝。若B選5，集合為{1,4}，A選1，B選4，A選5，B無法移動，A勝。若B選4，集合為{1,2,3,5}，A選2，B選3或5。若B選3，集合為{1,2,5}，A選1，B選2或5。若B選5，集合為{1,2,3}，A選1，B選2或3。若A選2后，B選3，集合為{1,5}，A選1，B無法移動，A勝。若A選2后，B選5，集合為{1,2,3}，A選1，B選2或3。若B選2，集合為{1,3}，A選1，B無法移動，A勝。若B選3，集合為{1,2}，A選1，B無法移動，A勝。若B選5，集合為{1,2,3}，A選1，B選2或3。若A選2后，B選2，集合為{1,3}，A選1，B無法移動，A勝。若A選2后，B選3，集合為{1,2}，A選1，B無法移動，A勝。若B選5，集合為{1,2,3}，A選1，B選2或3。若A選2后，B選2，集合為{1,3}，A選1，B無法移動，A勝。若A選2后，B選3，集合為{1,2}，A選1，B無法移動，A勝。總之，當n=6時，A存在必勝策略，即第一步選3。第七題解：設被選取的點集為S。要證明|S|≥?n/2?。考慮每個邊e={u,v}。由于沒有對角線，u和v是相鄰頂點。根據條件②，集合S中要么包含u，要么包含v（或兩者都包含）。因此，每條邊至少有一個端點被S中的點覆蓋。考慮頂點集V和邊集E的基數關系。原圖有n個頂點，每條邊連接兩個頂點。如果每條邊恰好有一個端點在S中，則|S|=|E|=n。但題目要求的是“至少”有?n/2?個點被選取。考慮一個頂點v。v的度數為3，因此有3條邊與v相鄰。根據條件②，這3條邊中至少有2條邊的一個端點在S中（因為如果只有1條或0條邊的一個端點在S中，則會有2或3個相鄰頂點不在S中，這與條件②矛盾）。這意味著每個頂點至少被S中的點“覆蓋”一次（可以是通過其相鄰的邊）。現在，我們將每個頂點v對應一個數cnt(v)，表示有多少條邊以v為端點且另一個端點在S中。由于每個頂點的度數為3，且每條邊至少有一個端點在S中，所以對于所有頂點v∈V，有Σcnt(v)=3|E|。由于每條邊至少貢獻1到Σcnt(v)，且每條邊最多貢獻2到Σcnt(v)（如果兩條端點都在S中），我們有Σcnt(v)≥|E|。結合Σcnt(v)=3|E|，得到3|E|≥|E|，即2|E|≥0，這是顯然的。更精確地，我們有2|E|≤Σcnt(v)≤3|E|。由于每個cnt(v)≥1（因為每條邊至少有一個端點在S中），Σcnt(v)≥|V|=n。因此，2|E|≤n≤3|E|。由于沒有對角線，|E|=3n/2。將|E|=3n/2代入不等式2|E|≤n，得到n≤3n/2，即2n≤3n，顯然成立。將|E|=3n/2代入不等式n≤3|E|，得到n≤3*(3n/2)=9n/2，即2n≤9n/2，即4n≤9n，即5n≤9n，即n≤9/5*n，這總是成立。因此，Σcnt(v)=3|E|=9n/2。由于Σcnt(v)≥|S|，所以|S|≥9n/2。由于每個頂點至少貢獻1到Σcnt(v)，我們有Σcnt(v)≥2|E|=3n。因此|S|≥3n。由于|S|是整數，且3n≥n，所以|S|≥?n/2?。例如，可以構造一個正六邊形（n=6），邊為{1,2},{2,3},{3,4},{4,5},{5,6},{6,1}。將頂點1,3,5選入S，|S|=3=?6/2?。每條邊恰好有一個端點在S中（例如，{1,2}的1在S中，{1,2}的2不在S中）。滿足條件。因此，被選取的點至少有?n/2?個。第八題解：采用構造法。證明S中存在一個大小為n的完美集。構造方法如下：將S={1,2,...,2n}的元素分成n組：A?={1,2,...,n},A?={n+1,n+2,...,2n}。令T=A?∪A?={1,2,...,