2023年英国奥林匹克数学竞赛BMO试题.pdf

2023-2024BMO第一轮考题解答

2023-2024英国数学奥林匹克竞赛（BMO）第一轮于11月15日进行，以下是6道考题及相

应的解答。

第1题：

一个不靠谱的打字员可以保证，当他们尝试输入一个由不同字母组成的单词时，在他们的输

入中单词的每个字母都会恰好出现一次，而且每个字母的出现最多被推后一个位置（尽管可

能被提前多个位置）。因此，当试图输入MATHS时，打字员可以打出MATHS、MTAHS或

TMASH，但不能输入ATMSH。

确定、并证明OLYMPIADS这个单词在该打字员输入中可能出现的不同拼写的数量。

解答：

先理解一下题目。以MATHS为例，MATHS是正确的拼写方式；在MTAHS中，A被推后一

位，T被提前一位；在TMASH中，M、A和H各被推后一位，T被提前两位，S被提前一位。

这3种拼写方式是符合题意；而ATMSH不可能出现，因为M被推后了两位。

从简单情况入手，如果单词中只有1个字母A，那么只有A这1种拼写方式，也就是正确的拼写

方式。

如果有2个字母A和B，那么有AB、BA这2种拼写方式，其中AB为正确的拼写方式。

现在考虑添加字母C，对于正确拼写AB来说，C可以添加在任何一个位置，因此产生了3种新

的拼写：ABC、ACB和CAB，其中ABC是三个字母正确的拼写方式。

对于BA来说，C只能添加在最后，否则A被退后2个位置，因此产生BAC这样1种新的拼写。

因此，对于3个字母的单词来说，符合题意的拼写方式一共有3+1=4种。

再考虑添加字母D，对于ABC来说，D可以添加在任何位置，对应于4种拼写；对于BAC，因

为C在最后一位，所以D可以添加在C的前面或后面，对应于2种拼写；对于ACB和CAB，D

只能添加到最后，否则B被退后了2个位置，所以各对应于1种拼写。

因此，对于4个字母的单词来说，符合题意的拼写方式一共有4+2+1+1=8种。

至此，我们可以猜想：对于n个字母的单词来说，符合题意的拼写方式一共有2n-1种。

我们用数学归纳法来证明这个猜想。

当n=1是，猜想显然成立。

假设当n=k时，猜想也成立，即对于k个字母的单词来说，符合题意的拼写方式一共有2k-1

种。

现在考虑n=k+1时的情况，假设在正确的拼写中，这k+1个字母顺次为LLL…

123

LL。

kk+1

我们以字母Lk+1的不同位置来遍历所有符合题意的拼写方式。

如果Lk+1位于拼写的最后，那么根据假设，前面k个字母一共有2k-1种符合题意的拼写方式。

如果L位于拼写的倒数第2位，那么根据题意，它后面的字母只能是L，它的位置被推后了

k+1k

一位，如果换做其他字母，这个字母将被推后了不止一个位置。这样，在Lk+1之前还有k–

1个字母，它们一共有2k-2种符合题意的拼写方式。

类似地，如果Lk+1位于拼写的倒数第i位，那么根据题意，它后面的字母有i–1个，顺次是Lk-

…LL，这i–1个字母及其顺序都只有这一种排列的可能，否则将至少出现一个字母被

i+2k-1k

推后了不止一个位置的情况。这样，在Lk+1之前还有k–i+1个字母，它们一共有2k-i种符合

题意的拼写方式。

以此类推，直到L位于拼写的第2位，它后面的k–1个字母顺次为L…LL，其中每个字

k+12k-1k

0

母都被推后了一位。L前面只有一个字母即L，对应于2种拼写方式。

k+11

最后，还有一种拼写方式，即L位于拼写的第1位，它后面的k个字母顺次为L…L