Last update: Oct 1, 2023
[TOC]
#1
这是一道来自学弟学妹组合数学课鸽巢原理部分的作业题。
Problem
“随意地给正 n 边形的 n 个顶点编上号 1,2,…,n, 求证：必有一个顶点及与之相邻的两顶点之和不小于 f(n)，并且 f(n) 是不可改进的。给出 f(n) 表达式再进行证明。”
Problem Abstraction
原题的表述很奇怪，我们把它抽象一下，同时加一点形式化的表述：
对于所有前 $n \ (n \ge 3)$ 个自然数的排列 $P_n$，求最小可能的 $\displaystyle \max_{i = 1}^n(P_{i - 1} + P_i + P_{i + 1})$，记为 $f(n)$。补充定义 $P_0 = P_n$，$P_{n + 1} = P_1$。
好懂多了。
Solution Probably Desired
利用鸽巢原理很容易求出 $f(n) \ge \left\lceil \dfrac{3n}2 + \dfrac32 \right\rceil$：
考虑 $\displaystyle \sum_{i = 1}^n(P_{i - 1} + P_i + P_{i + 1})$，排列里的每个值都会被计算三次，因此它就等于 $3\displaystyle \sum_{i = 1}^n P_i = \dfrac{3n(n + 1)}2$。显然 $f(n) \ge \dfrac{3n(n + 1)}{2n} = \dfrac{3(n + 1)}2$。
这个值可能不是整数，违背现实意义，所以套一层上取整得到 $f(n) \ge \left\lceil \dfrac{3n}2 + \dfrac32 \right\rceil$。
De Facto Solution
上面的解答只能粗略估计一个下界，但没办法证明这是下确界。实际上这也的确不是。根据 OEIS A066385，答案如下：
容易编程验证 $n$ 比较小时这个通项是正确的。$n > 15$ 后是猜想，目前没有人能给出过数学证明。
原题里那句“并且 $f(n)$ 是不可改进的”极其诡异，感觉是老师一拍大腿加上的，把这题变成了不可做题。
#2 - PE 306
Problem
原题链接 Project Euler Problem 306 - Paper-strip Game
Alice 和 Bob 在一组排列成长条型的 $n$ 个格子上玩游戏，两人交替进行操作。
每回合中一个玩家选择两个连续的空白格子涂黑，最先不能进行操作的玩家输。
Alice 先手。
$n = 1$ 时 Alice 没有合法操作，直接输掉。
$n = 2$ 时 Alice 只有一种合法操作，操作后 Bob 输。
$n = 3$ 时 Alice 有两种合法操作，但不论哪种操作过后 Bob 都会输。
$n = 4$ 时 Alice 有三种合法操作，他可以涂黑最中间的两个格子使 Bob 无法操作。
$n = 5$ 时如图 2.1，Alice 有四种合法操作（红色）；但无论他怎么操作，Bob（蓝色）都会赢。
因此，对于 $1 \le n \le 5$ 的情况，有 $3$ 种 $n$ 的取值使得 Alice 必胜。
类似地，对于 $1 \le n \le 50$ 的情况，有 $40$ 种 $n$ 的取值使得 Alice 必胜。
假设 Alice 和 Bob 都绝对聪明，永远会采取最优策略。
Bob 很想让 Alice 赢，但他不想放水。它想知道：对于 $1 \le n \le 1000000$，有多少种 $n$ 的取值使得 Alice 必胜？
Solution
这是一个找规律做法。
博弈论问题，直接考虑求出每个 $n$ 的 $\mathrm{sg}$ 函数。
枚举所有可能的操作（将大小为 $i \ (i \ge 2)$ 的问题分为大小为 $j$ 和 $i - j - 2$ 的两个问题），容易得到这样一个式子：
$n \in \{0, 1\}$ 时先手必败，$\mathrm{sg}(0) = \mathrm{sg}(1) = 0$。
打表得到 $1 \le n \le 204$ 时的 $\mathrm{sg}$ 函数值（每行 $34$ 个）：
1 | 0 1 1 2 0 3 1 1 0 3 3 2 2 4 0 5 2 2 3 3 0 1 1 3 0 2 1 1 0 4 5 2 7 4 |
容易发现除前两行特殊（共 $13$ 个 $0$）以外，以后的每一行都有恰好 $5$ 个 $0$。
之后幼儿园级别找规律，得到答案是 $852938$。