具体数学 Chapter I

· · 个人记录

Announce

以防浏览器爆炸，现将不同章节的题目移至其他页面。

导航：

Chapter I:本页

Chapter II:点我跳转

Chatper III:点我跳转

Update

2023.6.16：将错误的第 4 题证明修改为感性证明（太菜了）

2023.6.17：勉强把 Chapter I 热身题做完了，我好菜。（又做了两道题）

2023.6.29：写了几道 Chapter II 的热身题。（还有存货）

2023.6.30：将 Chapter II 的热身题补完了。

Chatper I

热身题

  1. 记 Col_i 为第 i 匹马的颜色。显然，当 n=2 时，按照题目中的逻辑，Col_1=Col_1,Col_2=Col_2 ，并不能推出 Col_1=Col2 ，得证。

  2. 通过手玩 n=1,2,3 的情况可以得到最少操作数为 T_n=3^n-1

  3. 证：因为盘无法在 A , B 杆之间直接移动，使得第 n 个盘必须走过3个盘子。而在这期间第 n-1 个盘子又会在三个盘子之间游走，以此类推，必会有三种情况分别是 n 个盘子在三个盘子上按正确方式摆放。

  4. 不存在，证：考虑 n 较小的情况，当 n=3 的时候，可以发现每一种开始情况的最少操作数都不超过 7=2^3-1 次，同理，结束情况也是，而既然对于 n=3 的情况操作数不大于 2^n-1 次，n 更大的情况也可以由归纳法得到操作数上界则应为 2^n-1 ，得证。

  5. 不能，因为由 n 个圆组成的维恩图必须包含由 n-1 个圆组成的维恩图，也就是说由 n 个圆组成的维恩图由有 n-1 个圆组成的维恩图再加一个圆组成。容易发现，无论无论如何组合，如果想要有一块只有第 4 个圆的区域，那么第 4 个圆一定会覆盖住另 2 个圆所覆盖的区域，使得表示的区域数与答案不符。

  6. 容易发现，如果要分割出一个有界的区域，那么至少需要3条直线（组成一个三角形）。自然，当 n<3 时，个数 S_n=0 ，而当 n\ge3 时，每一条直线都最多能够和之前的每一条直线相交，可得第 n 条直线最多能够和前面 n-1 条线构成 n-2 个有界空间与 2 个无界空间。也就是说总有界空间数为

S_n=\sum ^{n-2} _{i=1} i=\frac{(n-1)(n-2)}{2}

（式子中的 n-1 和 n-2 就是 S_1=S_2=0 的由来！）

  1. 容易发现，归纳法总结出来的式子范围是 n\in[2,+\infty)

有 1 吗，有 1 吗 没有包括 n=1 的情况，得证。

作业题

  1. 根据提示，我们将 Q_n 手推到 n=4 的情况，发现

    Q_2=\frac{\beta+1}{\alpha} Q_3=\frac{\alpha+\beta+1}{\alpha\beta} Q_4=\frac{\alpha+1}{\beta}

    然后 n=5 的时候……

    Q_5=\alpha

    (~又回到最初的起点~)

    接下来就好办了，既然是周期函数，那么直接可以得出以下结论：

    \alpha & (x=5k) \\ \beta & (x=5k+1) \\ \frac{\beta+1}{\alpha} & (x=5k+2) &(k \in \mathbb Z^+ )\\ \frac{\alpha+\beta+1}{\alpha\beta} & (x=5k+3) \\ \frac{\alpha+1}{\beta} & (x=5k+4) \end{cases}

  2. a. 根据题目提示，我们令 x_n=\frac{(x_1+\cdots+x_{n-1})}{n-1} ，代入得

    \frac{x_1 \cdots x_{n-1}(x_1+ \cdots +x_{n-1})}{n-1} \le (\frac{x_1+\cdots+x_{n-1}}{n}+\frac{x_1+\cdots+x_{n-1}}{n(n-1)})^n

    将左边的分母和分子上的 x_1+\cdots+x_{n-1} 移到右边并合并同类项可得

    x_1\cdots x_{n-1}\le(\frac{x_1+\cdots+x_{n-1}}{n-1})^{n-1}

    b. 这个非常简单，已知要求：

    x_1\cdots x_n x_{n+1}\cdots x_{2n} \le (\frac{x_1+\cdots+x_{n}+x_{n+1}+\cdots+x_{2n}}{2n})^{2n}

    将左右分别分为两组，再对这两组分别使用证出的不等式

    x_1\cdots x_n x_{n+1} \cdots x_{2n} \le (\frac{x_1+\cdots+x_n}{n}\cdot\frac{x_{n+1}+\cdots+x_{2n}}{n})^n

    右边根据分开的两组继续使用不等式

    \begin{aligned} (\frac{x_1+\cdots+x_n}{n}\cdot\frac{x_{n+1}+\cdots+x_{2n}}{n})^n &\le \Big [\big (\frac{x_1+ \cdots +x_n+x_{n+1}+\cdots+x_{2n}}{2n} \big )^n \Big ] ^n\\ &=(\frac{x_1+\cdots+x_{n}+x_{n+1} + \cdots + x_{2n}}{2n})^{2n} \end{aligned}

    那么最终便是

    x_1\cdots x_{2n} \le (\frac{x_1+\cdots+x_{2n}}{2n})^{2n}