2022 北京大学图灵班选拔考试

笔试

1. 问你能否将有限个单位正方形摆放在平面上使得

   • 任意两个正方形至多有一个顶点重合
   • 每个正方形的每个顶点都与其他某个正方形的顶点重合

2. 求$(\frac{1+\sqrt{5}}{2})^{12}$的整数部分

3. 对于一个加法乘法群，要求你利用

   • 乘法结合律、交换律、对加法的分配律、逆元
   • 加法结合律、逆元

   来证明加法的交换律

4. 给出一个$n$个非空数集$a_i \subseteq \mathbb N$构成的序列$a_1, \ldots, a_n$。其中$|a_i| = i + 1$。我们称该序列的一个特征分划为一个数集$\{x_1, x_2, \ldots, x_n\}$且满足$x_i \in a_i$（$x_i$互不相同）。

   1. 特征分划的方案数最坏情况下有多少个（至少有多少个）。
   2. 在特征分划的方案数最少时$a_1, a_2, \ldots, a_n$满足的条件。

5. Alice 和 Bob 博弈。Alice 先选一个数$m$，然后 Bob 选一个数$n$（$n >m$），并构造一个$n$个点的竞赛图。Alice 如果能从中选出$m$个不同的点，满足不存在某个点$x$到这$m$个点都有出边，那么 Alice 赢，否则 Bob 赢。问是否有人存在必胜策略。

考场答案

1. 不会
2. 暴力计算，好像化简到中间某个步骤的时候把加号改成减号可以得到一个界
3. 构造$(a+1)(b+1)$，然后展开的时候用两种方式。
4. 简单题
5. 猜的$m = 2$时甲必胜，然后做一些伪证。