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,...,