数学趣题 6 则

· · 个人记录

在美丽的清清草原，今天也有很多羊羊对数学很感兴趣呢！快来看看他们在做些什么吧！

1. 沸羊羊连续扔一枚硬币，连续扔出三个正面则停止。假设硬币扔出正面反面的概率都为 50\%，求期望停止时间。

2. 喜羊羊和美羊羊玩游戏。在下面的多项式中，喜羊羊每次选择一个实数，而美羊羊则在剩下的方框中选一个填进喜羊羊选择的实数。这样进行三次之后，如果得到的多项式有三个不同的整数根，那么喜羊羊获胜；否则美羊羊获胜。请问谁有必胜策略呢？

x^3+\square x^2+\square x+\square

3. 慢羊羊召开羊村大会。羊羊们之间可能会有讨厌的情况，讨厌关系是相互的，一只羊最多讨厌另外 3 只羊。慢羊羊希望将全部的羊羊分成两组，使得每只羊羊在自己的组内至多只讨厌 1 只羊。这是一定可以办到的吗？

4. 懒羊羊用烟杆在草原上写下一个神秘的式子：

\sum_{S\subset\{1,2,\cdots,n\}}\left(\mathrm{Pr}\{f(\mathbf R)\oplus\bigoplus_{i\in S} \mathbf R_i=0\}-\mathrm{Pr}\{f(\mathbf R)\oplus\bigoplus_{i\in S} \mathbf R_i=1\}]\right)^2=1

请你按照下面的步骤来证明它吧！这里 f 是任意一个 \{0,1\}^n\to \{0,1\} 的函数，\oplus 是二进制意义下的异或运算，\mathbf R 是 \{0,1\}^n 上的均匀分布，\mathbf R_i 表示第 i 位。

(a) 对 \mathbf r\in\{0,1\}^n，S\subset \{1,\cdots,n\}，定义 \chi_S(\mathbf r)=\prod_{i\in S}(-1)^{\mathbf r_i}。证明：

(i) \chi_S(r)\times \chi_S(r')=\chi_S(r\oplus r')。

(ii) 当 \mathbf r\neq \mathbf 0 时，\sum_{S\subset\{1,\cdots,n\}}\chi_S(\mathbf r)=0。

(b) 证明

\mathrm{Pr}\{f(\mathbf r)\oplus\bigoplus_{i\in S} \mathbf r_i=0\}-\mathrm{Pr}\{f(\mathbf r)\oplus\bigoplus_{i\in S} \mathbf r_i=1\}=(-1)^{f(r)}\chi_S(\mathbf r)

(c) 证明原命题。

5. 沸羊羊在手心上写了两个不同的实数。你可以看其中一只手上的，然后猜哪边的数大。你能设计一种策略使得不论两个数是什么，你猜对的概率都严格大于 50\% 吗？

6. 羊村正在使用一些长方形的砖头搭墙。如果每块砖头都有至少一条边的长度是整数，且搭出的墙面是没有缝隙的长方形，求证：这个长方形也至少有一条边长是整数。