15. 设 $n$ 是正整数, $f(S)$ 表示一个有限实数集中至少有 $2$ 元素的等差子集的个数.

证明对任意 $n$ 元实数集 $S$, 有 $f(S)\le\dfrac{n^2}4+f(\{1,2,\cdots,n\})$.

16. 给定整数 $k>1$. 设 $S=\{(x_1,x_2,\cdots,x_{k+1})\in\Z^{k+1}:1\le x_1<x_2<\cdots<x_{k+1}\le k^2+1\}$.

若 $\sigma$ 是 $1,2,\cdots,k^2+1$ 的置换, 则称 $(x_1,x_2,\cdots,x_{k+1})\in S$ 是 $\sigma$-好的, 当且仅当 $\sigma(x_1)<\sigma(x_2)<\cdots<\sigma(x_{k+1})$ 或 $\sigma(x_1)>\sigma(x_2)>\cdots>\sigma(x_{k+1})$.

证明: 对任意 $X=(x_1,x_2,\cdots,x_{k+1})\in S$, 使得以下两个命题等价:

(1) 存在一个置换 $\sigma$ 使得 $X$ 是 $S$ 中唯一一个 $\sigma$-好的元素;

(2) $\min\limits_{i=1}^k\lfloor\dfrac{x_i}i\rfloor+\min\limits_{i=2}^{k+1}\lfloor\dfrac{k^2+2-x_i}{k+2-i}\rfloor\ge k+1$.

17. 黑板上有有限多个两两不同的正整数.

每次操作, 若黑板上有两个数 $n,n+1$, 可擦去它们并写下一个新的数 $n-2$;

或者若黑板上有两个数 $n,n+4$, 可擦去它们并写下一个新的数 $n-1$.

操作后允许出现负整数和重复的数.

确定黑板上可能出现的最小整数.

18. 设 $ABC$ 是边长为 $1$ 的等边三角形, 初始时每个顶点处各有一只青蛙.

之后青蛙们可按如下规则跳跃: 每次跳跃选择两只青蛙 $X,Y$, 可将 $X$ 处的青蛙跳跃到 $XY$ 延长线上一点 $Z$, 要求满足 $XZ$ 的长度是 $XY$ 长度的偶数倍.

设 $M,N$ 分别是射线 $AB$ 与射线 $AC$ 上的点, 满足 $AM = AN = l$, 其中 $l$ 是正整数.

青蛙们经过若干次跳跃后, 都位于三角形 $AMN$ 中 (可在三角形的内部或边界上), 此后青蛙们不再跳跃. (青蛙们不必时刻位于三角形 $AMN$ 中, 只需跳跃终止时都在三角形 $AMN$ 中即可)

设终止跳跃时三只青蛙所在的点构成的集合为 $P$, 求集合 $P$ 的可能值的数目.

19. 设正整数 $k,s$ 满足 $s < (2k+1)^2$.

初始时 $n \times n$ 方格表中恰一个小方格染为绿色.

之后每次可如下操作: 选取一个绿色小方格 $c$, 并在以 $c$ 为中心的 $(2k+1) \times (2k+1)$ 方格表中选 $s$ 个未染色的小方格染成绿色 (已经染绿的方格不能再次被染绿).

称 $s$ 是 $k$-稀疏的, 如果存在正常数 $C$ 使得对任何正整数 $n$, 不论如何按上述方式操作, 绿色方格的总数均不超过 $Cn$.

对给定的正整数 $k$, 求最小的 $k$-稀疏正整数 $s$.

20. 设 $n$ 为正整数. 一个 $n \times n$ 方格表的每个格子中各有一盏灯.

初始时, 除最左列的灯可能亮着以外, 其余灯全灭. 每次操作可选择一盏不在最上行的灯, 同时切换它及所有与它所在格子有公共边的相邻格子中的灯的状态.

在全部 $2^n$ 种初始状态中, 有多少种可以经过有限次操作, 变成其关于连接左下角格子与右上角格子的对角线的镜像？

21. 设 $k, N$ 是给定的整数, 满足 $k > 1, N > 2k + 1$. 一共 $N$ 个人沿着圆桌均匀的坐下, 每个人或者是骑士 (永远说真话) 或者是说谎者 (永远说假话).

每个人观察逆时针方向离自己最近的 $k$ 个人与顺时针方向离自己最近的 $k$ 个人. 每个人都说: "我看到我左侧 $k$ 个人中骑士的数目等于我右侧 $k$ 个人中骑士的数目".

对怎样的 $k$ 与 $N$, 可通过上述信息确定所有 $N$ 个人都是骑士?