题目
Info
数学题面是英文，物理题面是中文。数学可以用中文或英文做答，物理用中文做答。
数学题是六道组合，感觉相对 OI 友好。
第一题
在一个数轴上，你站在 $0$ 点，并按照如下算法寻找 $x(x > 0)$ 点处的牛。
1 | curpos = 0; |
那么，你至多需要走（大约）多少单位长度以找到牛？ $3x, 5x, 7x, 9x$，还是以上都不正确。
第二题
给定 $10$ 个变量 $x_1, x_2, \dots, x_n$，满足 $x_i \ge 1$ 且 $x_i$ 两两不同。你要寻找一组 $\{x_i\}$ 的取值和一个参数 $a$，使得存在尽量多组 $\{b_i | b_i = -1~或~1\}$ 使得
最多能够存在多少组满足条件的 $\{b_i\}$？选项：$512, 252, 504, 684$。
第三题
给定无向图 $G = (V, E)$，我们称一个图是好的，如果：
- 每个点的度数均为 $d$
- 任何一个大小不超过 $|V|/2$ 的联通集合 $S$，其“邻居”，即不属于 $S$ 且可以通过 $S$ 中的点一步到达的点的个数 $N(S) \ge 5|S|/4$
求证：好的图中任意两点 $u, v$ 间的最短路径长度 $d(u, v) = O(\log |v|)$
第四题
给定两个相同的鸡蛋和一个 $100$ 层的高楼，你想要知道鸡蛋在多少层楼落下会恰好摔碎，给出最少所需的实验次数并证明。
第五题
$n$ 个人要进行一场游戏。游戏设计者准备了 $n$ 张卡片，正面分别写着 $n$ 个人的名字，背面写了 $1$ 到 $n$ 共 $n$ 个不同的数字。所有卡片都背面朝上放置在一个房间里。
当设计者准备完成后，$n$ 个人可以经过充分的讨论，并依次进入房间，一张一张地翻开共 $n/2$ 张卡片，并找到写有自己名字的卡片。当一个人操作结束后，他无法与其他人交流直到游戏结束。
只有所有 $n$ 个人全部找到了写有自己名字的卡片，他们才能获胜。请问：是否存在一种策略，使得无论设计者怎样安排名字和数字的对应，他们均拥有超过 $0.1$ 的胜率。
第六题
不记得了。
解答
第一题
设最后一次本当走 $k$，那么总共向前走的路程就是 $x + k - 1$，满足 $k / 4 \le x$，那么总共向前走了 $5x-1\approx 5x$，加上向后走的 $4x$，总共是 $9x$。
第二题
答案是 ${10\choose 5} = 252$，构造是容易的：只需让 $x_i = 1+\epsilon\times 2^{i}$ 并令 $a = 0$ 即可，因为 $b_i$ 任意五个取正均可使结果落在 $(0, 2)$ 内。
考虑无论对于任何 $x_i$ 和 $a$，设方案 $B$ 中取 $1$ 的指标集合为 $I(B)$，那么若 $I(B)\subseteq I(B’)$，$B, B’$ 不能同时在方案中存在。证明几乎是显然的。这样，根据 Sperner 定理就知道至多取出 ${10\choose 5}$ 个指标集合。
第三题
从两点出发双向 BFS，当两边集合不交时，至少有一者小于一半。加上邻居数量性质的保证，两边集合仅 $O(\log |B|)$ 就必然出现交点，从而可以构造一条路径。
第四题
经典题，结论是 $14$。事实上应该是最小的 $k$ 使得 $1 + 2 + \dots + k \ge n$，可以归纳证明，也可以直接组合论证。
第五题
经典题，Puzzle Toad 10。解法是随机打乱后沿着环寻找，概率约是 $1-\ln 2$。