十道题以内，考试时间一个小时，半小时后可离场
样题
（10分）龟兔赛跑 在一个环形跑道上，兔子对乌龟说：“我走一步相当于你走三步。”乌龟很不屑，说：“我走一步也相当于你走三步。”问：跑道有几步长（跑道大于 3 步，以乌龟步计量，可能有多种情况）？ 答案：4步或8步 remark. 这道题有群论的背景。4步和8步的情况分别对应 $C_4\rtimes C_2\cong D_4$，$C_8 \rtimes C_2$ 。若设 $a$ 是其中 $C_4$ 或 $C_8$ 的生成元，$b$ 是 $C_2$ 中的非平凡元，则它们满足关系 $bab^{-1}=a^3$ ，因此是三倍的速率。
（20分）维京海盗 老水手讲述了一个传说 是关于一名最恐怖的掠夺者 他非常野蛮 不仅抢走你所有的宝物 他还要拐走你最宝贝的女儿 ... 公元8到11世纪，维京人曾一度成为欧洲的海上霸主。维京海盗凶狠而直率，传说在海上劫掠战斗中，他们会用抓钩拉近两船距离再搭上跳板，在跳板上展开1v1战斗，首位出场的往往是队列中的最强者。 现为这样的海战建立数学模型。用正整数来代表一个战士的战斗力，每一方交战前先将战士们按出场顺序排成一队，交战时从队列最前端开始比较战斗力，每一回合战斗力低者战败出场（该方队列下一人立即补充），战斗力高者留下但战斗力减1（负伤），战斗力相同则均战败出场。循环往复，直到某一方没有人再能入场为止。如下是一场典型的战斗（一行记录一个回合的战况，左右两边分别是敌我双方，战斗从开始到结束历经4个回合） $$\begin{align} 2\quad 2\quad \underline2\quad&vs\quad \underline3\quad 2\quad 1 \ 2\quad\underline2\quad&vs\quad \underline2\quad2\quad1 \ \underline2\quad&vs\quad \underline2\quad1 \ &vs\quad 1 \end{align}$$ (1)（8分）假设现在你正作为指挥官面临一场海战，敌人的战斗力为 $9，6，10，9，4，10，7，4$，并且以该顺序出战。而你的战士们战力为 $10，8，8，8，7，2，2，2$。请你调整他们的出战顺序（重排这列数），从而能够战胜强敌。 (2)（12分）如果上题中的指挥官喝醉了，随机乱排，战胜强敌的概率是多少呢？ 答案： （1）（唯一）$2，2，8，10，7，2，8，8$ （2）$\dfrac{1}{1120}$. 首先注意到强敌确实挺强，因此排法唯一。概率是该排法的出现概率除以排列总数，由于2，8 各出现了 3 次，计算得概率为 $\dfrac{3!\cdot 3!}{8!}=\dfrac{1}{1120}$。 remark 1. 这个解法，人找起来并不费力。但是是否有一种多项式时间的算法确保找到它？ remark 2. 这是个我初中时发明的游戏，那时（很草率地）认为先出小的再出大的（即递增排列）总是最优的。但实际上不是。
（20分）两人石子连线游戏 在一条河的两岸分别摆放着 n 和 m 颗石子。每一回合，先由参与游戏的玩家 A 选择其中任意一颗石子（在河的任意一边），再由玩家 B 选择该石子对岸的一颗石子将它们连线。要求连过线的石子不能再被选择，连线不能相交。游戏在玩家 B 无法合适地进行连线时结束。玩家 A 的目标是使得游戏回合数尽可能少，而玩家 B 则相反。如下图，该游戏进行了三个回合，第三回合当玩家 A 选择石子后，玩家 B 无法找到剩余的红色石子连线并保证连线不相交。现假设玩家 A 和 B 都绝顶聪明（即每一步都是最优决策）。 ![[Pasted image 20221015161714.png]] (1)（5分）若河两岸的石子数分别为 1000，1000，游戏结束时连了几道线？ (2)（15分）若河两岸的石子数分别为 1000，1001，游戏结束时连了几道线？ 答案： （1）1000 （2）$[log_21000]=9$ remark. 这个游戏其实是 Ehrenfeucht Fraïssé Game 的有限全序集版本。它是模型论（数理逻辑的一个分支）的重要工具。游戏的过程相当于在用一阶逻辑的语言辨别两个集合的不同。题目中的例子对应于“存在元素 x 满足 存在元素 y 满足 y>x 且存在元素 z 满足 y>z>x”，这个命题在 5 个元素的全序集中为真，在只有 3 个元素时为假。这样的命题使用的变量的个数恰好是游戏中连线的个数 + 1。
（30分）堵车问题 N 辆汽车在一条狭长（不允许车辆并排行驶或超车）的小路上排成一列。我们给每辆汽车一个随机（各不相同）的初始速度，并且要求它们以该速度匀速同向行驶。为避免追尾，当一辆汽车由于速度比前面的快而即将撞上前面的汽车时，令其减慢车速使得与前面的汽车速度一致。如此，经过足够长时间后，所有汽车的车速都固定下来，汽车们自然地分成几个车速不同的车队（但每个车队内部车速相同）。 (1)（5分）N 辆汽车分成 N 个车队的概率是多少？ (1)（8分）3 辆汽车分成的车队数目的数学期望值是多少？ (3)（17分）N 辆汽车分成的车队数目的数学期望值是多少？ 答案： （1）$\dfrac{1}{N!}$ （2）$\dfrac{11}{6}$ （3）$\sum_{n=1}^{n=N}\frac{1}{n}$（调和级数）
（20分）Polynomial 1.0 某公司新研发了一种叫 Polynomial 1.0 的编程语言，用它写出的程序以 -10 到 10 的整数为输入和输出，程序主体是一个整系数多项式，其中包含常数，输入变量，中间变量，和输出变量。程序运行时会搜索从 -10 到 10 的所有可能的中间变量和输出变量的取值，如果代入后多项式的值为0，程序立即结束并返回输出变量的值。若没有搜索到任何结果则自动返回 None. 如 $x-2a$ ，其中 $x$ 是输出变量，$a$ 是输入变量，若输入 $a=2$，让 程序运行，会发现 $x=4$ 时刚好让多项式值为0，因此程序返回4。这个程序的效果就是 "乘以2" 又如 $(x(x-1)(x-2)(x-3)(x-4))^2 + (a - 5m - x)^2$ ，其中 m 是中间变量。若输入 $a=13$，程序运行时发现代入 $x=3,m=2$ 会让多项式值为0。因此程序返回3。这个程序的效果是“除以5的余数” (1) （5分）写一个程序（多项式），若输入1，返回0，若输入0，返回1 (2) （5分）写一个程序，若输入偶数，返回1，若输入奇数，返回0 (3) （10分）写一个程序，若输入（正）质数，返回1，否则返回0（提示：cheat） 答案（不唯一，但基本唯一）： (1) $1-x-a$ (2) $(x(x-1))^2+(a-(2m+1)-x)^2$ (3) $((a-2)(a-3)(a-5)(a-7)x)^2+(a(a-1)(a+1)(a-4)(a+4)(a-6)(a+6)(a-8)(a+8)(a-10)(a+10)(x-1))^2$
之后会上传部分题目。