4.19
面积与格点
题面
设想一个平面上布满间距为 \(1\) 的横纵直线，形成由一个个 \(1\times 1\) 正方形组成的网格。任意给一个面积小于 \(1\) 个单位的图形，证明这个图形总能放在网格中而不包含任何一个格点。 #### 题解
将该图形 \(A\) 先随意放置于网格中，之后将每一个彼此分开，位于网格上的 \(A\) 也一起分开，将 \(1\times 1\) 的格子只通过平移堆叠在一起，所有 \(A\) 的部分取并集，由于 \(S_A<1\)，所以一定存在一点满足该点没有被 \(A\) 的部分的并覆盖，我们将该点集还原于原网格，在这个点集的基础上构造新的网格即可。
拓展
Blichfeldt 定理：一个面积为 \(A\) 的闭区域 \(F\) 一定存在大小为 \(\lceil A\rceil\) 的点集，满足点集内部的点两两之间横纵坐标差为整数。
同样将所有网格堆叠在一起，假设最多只存在 \(\lceil A\rceil-1\) 个格点，那么对于所有点而言，每个点最多只被 \(\lceil A\rceil-1\) 个点覆盖，所以 \(S_F\le\lceil A\rceil-1< A\)，矛盾。
Minkowski 定理：坐标平面上任何含 \((0,0)\) 且中心对称的凸包 \(F\) 满足 \(S_F>4\) 一定含有异于原点的整点。
由 Blichfeldt 定理 可知，\(F\) 内至少有 \(2\) 个点满足横纵坐标差为偶数（先放缩），记为 \((x,y),(x+p,y+q)\)，由于中心对称，所以存在 \((-x-p,-y-q)\in F\)，由于 \(F\) 为凸包，取中点得 \((\dfrac{p}{2},\dfrac{q}{2})\in F\)，故存在。
这两个定理都可以拓展到 \(\mathbb{R}^n\) 的形式，在密码学中有应用。
4.19
升维
题面
平面上四条直线，任两条不平行，任三条不共点。四个旅行者 \(A,B,C,D\) 分别匀速地走在这四条直线上（他们的速度可以不相同）。若 \(A\) 在行走过程中与 \(B,C,D\) 相遇，\(B\) 在行走过程后与 \(C,D\) 相遇（当然也遇见了 \(A\)），\(A,B,C\) 不同时相遇，\(A,B,D\) 不同时相遇，求证：\(C,D\) 在行走过程中相遇。
题解
引入时间 \(t\) 轴垂直于平面，每个人的位置可以唯一表示为一条直线 \(l(x,y,t)\)，由于 \(A,B\) 相遇，则 \(l_A\) 交与 \(l_B\) 确定了平面 \(F\)，由于 \(C\) 与 \(l_A\) 和 \(l_B\) 有互异的两个交点，故 \(l_C\subset F\)，同理 \(l_D\subset F\)，\(l_C\) 与 \(l_D\) 不平行必有交点。
停机问题
题面
是否存在一个程序 \(P\)，对于任意输入的程序 \(Q\) 和输入 \(w\)，能够判断 \(Q(w)\) 会在有限时间内结束或者死循环。
题解
不存在，假设有解，则给定 \(H(w)\) 描述为调用 \(P(H,w)\)，若 \(P(H,w)\) 判断为死循环，否则结束，那么 \(H(H)\) 就是反例，矛盾。
7.14
丢失的机票
题面
一架客机上有 \(100\) 个座位，\(100\) 个人排队依次登机。第一个乘客把机票搞丢了，但他仍被允许登机。由于他不知道他的座位在哪儿，他就随机选了一个座位坐下。以后每一个乘客登机时，如果他的座位是空着的，那么就在他的座位坐下；否则，他就随机选一个仍然空着的座位坐下。请问，最后一个人登机时发现唯一剩下的空位正好就是他的，其概率是多少？
题解
当第 \(i\in [2,99]\) 个人遇到自己的位置被第 \(1\) 个人占据后，那么可以理解成第 \(1\) 个人要坐第 \(i\) 个人的位置，而第 \(i\) 人依然是原位置，那么问题规约为最后只剩两个位置，\(1\) 号随机选自己，那么答案就是 \(\dfrac{1}{2}\)。
或者更细致的，我们设总共有 \(n\) 个人， \(p_k\) 为第 \(k\) 个人座位被占用的概率，那么：
\[ p_k=\dfrac{1}{n}+\sum_{i=2}^{k-1}p_i\dfrac{1}{n+1-i} \]
归纳得 \(p_k=\dfrac{1}{n+2-k}\)
\(0\) 和 \(9\)
题面
任意写下一个数 \(N\)，再在它下面写下它的 \(2\sim 9\) 倍。把这些数按位对齐，每一列里恰好有 \(9\) 个数字（前面几行中的首位为空时该位置视作0）。证明，每一列中至少有一个数字0或者数字9。
题解
假设存在某一列不存在，那么由鸽巢原理得，\(aN\) 和 \(bN\) 必定有一位相同，那么 \((a-b)N\) 该位一定要么是 \(9\) 要么是 \(0\)，矛盾。