具体数学 Chapter III

· · 个人记录

Chapter III

妈的顶和底的符号打得我累死了

热身题

  1. 容易得到 m=\lfloor \log_2 n \rfloor,l=n-2^{\lfloor \log_2 n \rfloor} .

  2. a. \lfloor x+0.5 \rfloor

    b. \lceil x-0.5 \rceil

  3. 由 m\alpha = \lfloor m\alpha \rfloor + \{ m\alpha \} 得：

    \begin{aligned} \lfloor \lfloor m\alpha \rfloor n / \alpha \rfloor &= \lfloor mn - \{ m\alpha \} n / \alpha \rfloor\\ &= mn + \lfloor - \{ m\alpha \} n / \alpha \rfloor \end{aligned}

    因为 \alpha > n ，所以后面那一坨里面是处于 (-1,0) 之间的.

    所以最后就得到

    \lfloor \lfloor m\alpha \rfloor n / \alpha \rfloor = mn - 1

  4. 瞎猜一波，是让人瞎猜的问题 （答案就是这个，没骗你）

\begin{aligned} \lfloor nx \rfloor = nx - \{ nx \}\\ n \lfloor x \rfloor = nx -n \{ x \} \end{aligned}

得

\{ nx \} = n \{ x \}

因为 \{ x \} \in [0,1) ，所以 n \{ x \} 也应该在这个范围内

因此 0 \le \{ x \} < \frac 1 n .

反推过来也一样，可以使用反证法。

当 \{ x \} \ge \frac 1 n 时，\lfloor nx \rfloor \ge n \lfloor x \rfloor +1 \not = n \lfloor x \rfloor

故 0 \le \{ x \} < \frac 1 n 为 \lfloor n x \rfloor = n \lfloor x \rfloor 的充要条件.

  1. 简单类比书前面所提到的式子可以得到
\lfloor f(x) \rfloor = \lfloor f(\lceil x \rceil)\rfloor

（注意这里的 f 是减函数，所以里面是顶）

  1. 易得
X_n = X_{n \bmod m} + \lfloor n / m \rfloor

当 n > m 时

  1. 首先将 \lfloor \frac n m \rfloor m 个物体铺满盒子，然后会剩下 n \bmod m 个盒子. 这些盒子无论怎么分，总会使至少一个盒子大于 \lfloor \frac nm \rfloor 个，即 \ge \lceil \frac nm \rceil

    而如果将其他还保留了 \lfloor \frac nm \rfloor 个物体的盒子中拿出物体给别的盒子，那么就会 < \lfloor \frac nm \rfloor ，不拿出就是等于.

  2. 将 \frac 1 q 移过去得到

\begin{aligned} \frac m n - \frac 1 q &= \frac{qm-m}{qn}\\ &= \frac{m \lceil \frac n m \rceil -m}{n \lceil \frac n m \rceil}\\ &= \frac{m \lfloor \frac n m \rfloor}{n \lceil \frac n m \rceil} \end{aligned}

现在要证明最后那个式子不等于 \frac 1 q . 因为 \frac m n 是最简分数，所以 \frac n m 不为整数

\begin{aligned} \frac{m \lfloor \frac n m \rfloor}{n \lceil \frac n m \rceil} &< \frac{m \cdot \frac n m }{n \lceil \frac n m \rceil}\\ &= \frac 1 {\lceil \frac n m \rceil} \end{aligned}

所以每个 \frac 1 q 都是不一样的.