2024-2025年BMO1试题解答

教育   2024-11-25 22:49   江苏  


本周三1120日,英国数学奥林匹克竞赛(BMO)举行了第一轮比赛。以下是本次竞赛的试题及解答。

先给出答案:在3 ≤ n ≤ 12这个范围内,34681012是快乐的。

我们声称:3和所有大于2的偶数都是快乐的;所有大于3的奇数都不是快乐的。

下面给出证明。

n = 3是快乐的。简单用一个例子,当124这三个数围成一圈时,显然每一对相邻的数字对都存在倍数关系。n = 3时不存在不相邻的数字对。

n = 4也是快乐的。用一个例子,当254360这四个数围成一圈时,显然每一对相邻的数字对都存在倍数关系。这个例子中不相邻的数字对有两对{2, 3}{54, 60},其中一对是两个质数,另一对是这两个质数乘积的两个倍数,只要这两个倍数足够大,它们之间就不存在倍数关系。

n = 2kk > 2时也是快乐的。用Ni表示第i个位置上的数字,我们用一个复杂一些的例子,在132– 1k个奇数位上放置k个不同的质数,即N2i – 1 = pi;在242kk个偶数位上放置相邻两个位置上奇数的乘积,即

对于1 ≤ i < kN2i = pipi + 1;对于i = kN2k = pp1

每一对相邻的数字对中必然有一个在偶数位,有一个在奇数位,偶数位上数字是奇数位上数字的倍数;同时,在每一对不相邻的数字对中,两个数字分别有两个不同质数的因子,所以它们之间不可能存在倍数关系。

因此,k > 2时,n = 2k都是快乐的。

n = 2k – 1k > 2时都不是快乐的。当k > 2时,对于任意连续的三个数字a, bc{ac}是一对不相邻的数字对,ac之间不存在倍数关系。

情形1a|b时,b不可能整除c,否则存在a|c。因此,a|bc|b。我们用a+b-c来表示,其中“+”表示左边数字整除右边数字,“-”表示右边数字整除左边数字。

情形2b|a时,c不可能整除b,否则存在c|a。因此,b|ab|c。我们用a-b+c来表示。

综上,如果n = 2k – 1是快乐的,那么在这2k – 1对连续数字的关系中,“+”“-”交替出现,即“+”“-”的个数相等。但另一方面“+”“-”的总数等于2– 1,是一个奇数。矛盾。因此n = 2k – 1不是快乐的。

证明完毕。

魔术师手中的牌堆即正整数{1, 2, 3, …, n}的一个排列a1, a2, a3, …, an

令观众写下的初始数为x,那么根据游戏规则,他在黑板上依次写下:

a1x
a2a1 + x
a
3a2 + a1x

anan – 1 + an– 2 – … – (-1)– 1a1 + (-1)nx

最后一个数字和初始数字之和为0,即

anan – 1 + an – 2 – … – (-1)n – 1a1 + (-1)nx + x = 0

n为偶数时,anan – 1 + an – 2 – … – a1 + 2x = 0。因为魔术师事先不知道x的大小,所以他不能保证这个等式成立。

n为奇数时,anan – 1 + an – 2 – … + a1 = 0,这个等式与x无关,如果魔术师可以使得牌堆中奇数位置上牌点数之和等于偶数位置上牌点数之和,那么魔术即可成功。

n = 2k – 1,上述条件相当于将集合{1, 2, 3, …, 2k – 1}分为两个互补的子集,其中一个子集元素个数为k – 1,另一个子集元素个数为k,两个子集元素之和相等。

易知,所有2k – 1个正整数之和为k(2k – 1),上述条件的必要条件为:k(2– 1)为偶数,即k为偶数。

我们声称,k为偶数同样是上述条件的充分条件,即对于任意偶数k{1, 2, 3, …, 2k – 1}一定可以分为两个元素个数分别为k – 1k的子集,其元素之和相等。

这个命题可以简单通过数学归纳法证明。

k = 2时,{1, 2, 3}可以分为{1, 2}{3},显然两个子集的元素之和相等。

假设当k = 2t时,集合{1, 2, 3, …, 4t – 1}可以分为S1S2S1S2两个子集的元素个数分别为4t – 14t,且其元素之和相等。

考虑k = 2(t + 1)的情况,此时集合为{1, 2, 3, …, 4t – 1, 4t, 4t + 1, 4t + 2, 4t + 3},将后四个元素两两分入S1S2中,即4+ 1, 4t + 2分入S1中,4t, 4t + 3分入S2中,这样得到的新的两个子集的元素个数分别为4t + 14+ 2,且其元素之和也相等。

命题对于k = 2(t + 1)也成立。

根据数学归纳法,命题对于所有偶数k = 2t都成立。

因此,对于任意正整数t,当n = 4t – 1时,魔术师都可以使用特定排列的牌堆使得魔术成功。

我们声称Rhian有必胜的策略。

先讨论游戏结束的条件。

n > 1时,它都可以写作1 ∙ n,从而可以使用n – 1来替代n,游戏可以继续。

n = 1时,它只能写作1 ∙ 1,两个数字相同,游戏无法继续。

因此,谁能够在黑板上写下1,谁就能获胜。

回溯一步,当谁在黑板上写下2,谁就失去了胜利,因为2 = 1 ∙ 2,他的对手可以在黑板上写下1

注意到,奇数只能写出两个奇数的乘积,而两个奇数的差一定为偶数,所以拿到奇数的人不论如何分解因子,他在黑板上只能写下偶数。

而偶数始终可以写成偶数本身和1的乘积,两者的差一定为奇数,拿到偶数的人可以简单地使用这个办法在黑板上写下一个奇数。

比较黑板上头一个数字n = ab和下一个数字|b|的大小,将两个数字平方后相减,得到

n2 – (|ab|)2= a2b2ab2 + 2ab = (a2 – 1)(b– 1) + 2ab – 1

因为ab都是不小于1的整数,所以上式一定大于0,即黑板上的数字是严格递减的,在有限回合后,这个数字一定会变成1,游戏结束。

在游戏的开始,Rhian得到的106是一个偶数,按照上述策略在游戏过程中他可以在黑板上写下一个又一个更小的奇数;而Jack在每个回合中得到的都是一个奇数,他没有办法改变局面,不得不一直在黑板上写下一个又一个更小的偶数……直到Rhian写下1Jack无法将1分解成两个不同的因子,Rhian从而确保获得胜利。

AM延长线上取点D,使得BD = AB

BD = ABMDB = PAB = MCP

又有DB = AB = CPDMB = CMP

所以DMB CMP

DM = CM = BM BDM = DBM

CPM = DBM = BDM = PCM

PM = CM = BM

CPB = CPM + BPM = PCM + PBM = 180˚/2 = 90˚

得证。

因式分解,n6 – 1 = (n – 1)(n + 1)(n2n + 1)(n2 + n + 1)

如果p|(n– 1),那么要么p|(– 1)(n + 1),要么p|(n2n + 1)(n2 + n + 1),这两个条件中至少有一个被满足。

如果p|(– 1)(n + 1),那么要么p|(n – 1)n最小的条件下n = p + 1;要么p|(n + 1)n最小的条件下n = p – 1。两者综合起来,n最小的条件下,p|(n + 1)

如果p|(nn + 1)(n2 + n + 1),那么要么p|(n2n + 1)n最小的条件下(– 1)n = p – 1;要么p|(n+ n + 1)n最小的条件下n(n + 1) = p – 1。即p – 1可以表示为连续两个自然数的乘积。两者综合起来,显然n(+ 1) = p – 1n更小。因此,在n最小的条件下,p|(n2 + n + 1)

综合以上,当n为满足p|(n6 – 1)条件的最小的正整数时,要么p|(+ 1),要么p|(n+ n + 1),这两个条件中至少有一个被满足。

由以上因式分解可知,(n2n + 1)|(n6 – 1),将n + 1替代n,有

[(n + 1)2 – (n + 1) + 1]|[(n + 1)6 – 1)]

即,(n2 + n + 1)|[(n + 1)6– 1)]

同理,(n – 1)|(n6 – 1) n + 2替代n,有

(n + 1)|[(n + 2)6 – 1)]

因此,当p|(+ 1)时,有p|[(+ 2)6 – 1)];当p|(n2 + n + 1)时,有p|[(+ 1)6 – 1)]

因此,当n为满足p|(n6 – 1)条件的最小的正整数时,p|(n + 1)p|(n2 + n + 1)中至少有一个被满足,从而p|[(+ 2)6 – 1)]p|[(n + 1)6 – 1)]中至少有一个成立,即(n + 2)6 – 1(+ 2)6 – 1)中至少有一个能够被p整除。

得证。

这道题难度最大,同样也最有意思。这道组合题利用了两次抽屉原理。

4 × 4 × 4的立方体视为82 × 2 × 2的小立方体,每个小立方体由8个单位立方体组成。

考虑对每个小立方体中的8个单位立方体进行黑白染色,如下图所示,将无边相连的单位立方体染为同一种颜色,这样我们得到黑色和白色各4个单位立方体,易知每两个颜色相同的单位立方体的中心之间的距离为√2

对于每种颜色的4个单位立方体,其中心组成了一个正四面体,它们之间的距离都相等。

第一次使用抽屉原理:因为单位立方体(方糖)有3种口味,所以在每种颜色的正四面体的4个顶点中,至少有1对单位立方体的口味是相同的。我们把这对口味相同、中心相距为√2的单位正方体称为同味对。

这样,对于每个2 × 2 × 2的小立方体,至少存在2对同味对(黑色和白色各至少1对)。

回到4 × 4 × 4的立方体,它由8个小立方体组成,因此一共至少存在16对同味对。对于任意一同味对中的两个单位立方体,其口味相同,且中心之间的距离为√2

第二次使用抽屉原理:因为单位立方体(方糖)有3种口味,而4 × 4 × 4的立方体中至少有16对同味对,所以16对同味对中至少有6对同味对的口味相同。

这等同于,在4 × 4 × 4的立方体中至少存在12个单位立方体,它们口味相同,且中心之间的距离相等。

证明完毕。


往期精彩文章:

数学科普:

数学竞赛:

数学教育:

数学文化:


敬请关注“唯思客俱乐部”,分享、点赞、在看我们的文章:

数学竞赛之窗
数学奥林匹克问题研究,问题探讨,竞赛信息
 最新文章