题目
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$。