2019 茶园二次招生题目(数学)

题目

Info

数学题面是英文,物理题面是中文。数学可以用中文或英文做答,物理用中文做答。

数学题是六道组合,感觉相对 OI 友好。

第一题

在一个数轴上,你站在 $0$ 点,并按照如下算法寻找 $x(x > 0)$ 点处的牛。

1
2
3
4
5
6
7
curpos = 0;
curdir = LEFT;
step = 1;
while (没有找到牛) {
沿着 curdir 方向,走 step 单位距离,如果找到牛就停止;
如果没有找到牛,回到原点并将 curdir 设为反方向,step = step * 2;
}

那么,你至多需要走(大约)多少单位长度以找到牛? $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$。

本文标题:2019 茶园二次招生题目(数学)

文章作者:ljt12138

原始链接:http://ljt12138.github.io/2019/08/07/iiis-selection/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。