0%

具体数学 学习记录

​ 开个坑,准备把《具体数学》这本书好好学一下。

​ 所以这个帖子被我置顶了,时刻警示着我是个带菜鸡。


2.26:

$\Large\text{1. Recurrent Problems}$

$\large\text{1.1 The Tower of Hanoi}$

​ 有关答案递推式的一些理解:怎么确定答案递推式是 $T_n = 2 T_{n-1} + 1$ 而不是 $\leq$ ?

​ 首先 $\leq$ 显然可证,就是先把前 $n-1$ 个盘子移到另一个立柱上,再把第 $n$ 个盘子移到最后一个上,最后把 $n-1$ 个盘子摞上去。

​ 那么怎么证 $\geq$ 呢?也很感性,考虑我们迟早会挪动最后一个盘子,如果我们可能挪动他,那就一定说明剩下的 $n-1$ 个已经在一撮里面了,否则不可能挪动。同理,挪动完最后一个盘子之后还要摞上去 $n-1$ 个,所以$T_n \geq 2 T_{n-1} + 1$.

​ 综合一下就能得到等于的关系了。两边待定系数一下,就可以发现这个东西是某种意义上的等比数列。

​ 有一个有意思的推广,或者说是脑洞:如果推广到 $n$ 盘,$m$ 柱怎么做?

​ 注意到,我们一定可以将过程分为如下几个部分:随便挪 $i$ 个到某个柱子上,再把剩下的 $n - i$ 个挪到最后一个柱子上,最后再挪回来那 $i$ 个。

​ 所以就直接 $dp$ 一下。

$\large\text{1.2 Lines in the Plane}$

​ 这题貌似还真没咋见过。。。

​ 首先是令 $L_n = n$ 条直线的答案,看起来这玩意没有一眼能看出来的递推式…

​ 但是书告诉我们,显然有一个明显的上界,即

​ 为啥呢?

​ 考虑每次我们新加一条直线,如果会多 $k$ 个区域,那意味着分裂了已知平面中的 $k$ 个区域。转化成另一个等价条件:这条直线和 $k-1$ 条直线有交。

​ 但是显然,这个 $k-1 \leq n-1$。所以就有了上面那个式子。

​ 那我们进一步考虑一下,显然我们可以构造出 $=$ 的上界:只需要保证每次的直线都不与剩下的所有直线平行即可。

​ 所以递推式就有了,粗略计算一下也能发现有通项$L_n = \frac{n(n + 1)}{2} + 1$.

​ 这里存在一个封闭形式的探讨:即对于一个式子是否是封闭形式,只需要看他是否是用“人人熟知”的运算所表示出来的。如果是,则是封闭形式(例如$2^n - 1$),若不是(比如是个递归式子),那就不是封闭形式。

​ 也就是说,我并不需要依赖比我小的子问题去回答这个问题,这才是“封闭形式”的真实意义。

​ 另外书中还引申出了一个用折线分平面的问题。经过思考后发现,这个折线可以被当做 $2$ 条直线,只不过每次 cut 会少两个区域而已。那么$R_n = L_{2n} - 2n$.

​ Z 形线同理:每次 3 条直线,少 4 个区域。


2.27

$\large\text{1.3 The Joseph Problem}$

​ 经典的约瑟夫问题的进一步思考,之前听 EntropyIncreaser 在校内讲过,这里写一下具体的探究过程(以 2 个人为间隔为例):

​ 考虑基于朴素递归的 $J(n)$ 定义,即每次变为更小规模。

​ $J(2n) = 2J(n) - 1$

​ $J(2n + 1) = 2J(n) + 1$

​ 这个式子显然可以直接递归 $\Theta(\log n)$ 计算,但是还有更为简便的做法,也就是“封闭形式”。

​ 首先经过简单的观察,可以发现 $n$ 和 $J(n)$ 有一定的规律:1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 17, 1… 也就是说,每次增长是一个 2 的幂。

​ 然后经过归纳,我们可以证得 $J(2^m + l) = 2l + 1, 0 \leq l < 2^m$ 。

​ 看起来这个式子也很 final 了,但是还可以从二进制表示出发,进一步探究。

​ 令 $n = (b_m b_{m-1} b_{m-2} … b_{0})_2$ ,则 $l = (0, b_{m-1}, b_{m-2}, … b_{0})_2$,$2l + 1 = (b_{m-1}, b_{m-2}, … b_0, 1)_2$ ,由 $J(n) = 2l + 1$ 可得:$J(n)$ 就是将 $n$ 二进制循环移位一位后的结果。

​ 经过观察发现,这个函数 $J(n)$ 如果不断进行迭代,最后一定会停在一个 $J(n) = n$ 的不动点,也就是 $n$ 位于某一个 $2$ 的幂次方 $-1$ 。那么这个幂次是多少呢?显然是一开始 $n$ 的二进制位中 $1$ 的个数。

​ 看样子探究完了,不过书中还给予了我们一些有意思的思考内容:

​ 考虑我们在一开始列出 $J(n)$ 的时候给出了一个猜测,即对于 $n$ 是偶数的情况均有$J(n) = n / 2$. 那么根据我们列出的 $ J(n) $ 的算式,我们不禁会想:什么情况下这个满足?

​ 那么重申一下:满足当且仅当 $n$ 循环移位后和 $n$ 删掉最后一个0所得的数是一样的。

​ 通过一个简单的对应可以发现,这东西一定形如 $10101010…10$ ,这似乎解答了我的疑惑。

​ 今天就更到这里吧,后面的还没看.jpg


2.28

​ 今天读的比较少。后面的待定系数法今天脑子有点晕,就暂时不看,先把warmup做了。

​ $\tt{1.}$ 一看就是假的传递性。

​ $\tt{2.}$ 有点牛逼这个题。发现这个东西你不能用经典结论去搞,原因是他从1柱挪n个到2和到3是不一样的。所以,我们令定义 $T_n = $ 挪 $n$ 个盘子从 1 柱到 3 柱的方案数。

​ 那么有递推式 $T_n = T_{n-1} + 1 + T_{n-1} + 1 + T_{n-1}$.

​ 这是啥意思呢?先把 n-1 个从 1 到 3,再把第 n 个从 1 到 2,再把 n-1 个从 3 到 1,再把第 n 个从 2 到 3,最后把那 $n - 1$ 个挪回来。

​ 用当时证明汉诺塔结论时同样的方法,可以显然证明步数最少是这个,原因是你至少要挪动两次 n。

​ $\tt{3.}$ 继续来毒瘤归纳。

​ 算得上面的 $T_n = 3^n - 1$。所以呢,总共可能的局面只有 $3^n$ 种(即每个盘子选柱子),但是你最优需要 $3^n - 1$ 次移动。在这移动中呢,显然不会出现相同的局面,因为那样会让你有更优的步数。所以,你移动中也恰好 meet 了 $3^n$ 种不同的局面。

​ 所以,你肯定是每个都碰到了一次。

​ $\tt{4.}$ 考虑依然用归纳法证明这一结论。

​ 当 $n = 1$ 时,显然。

​ 当 $n - 1$ 成立时,如果 $n$ 在最后一个,那只需要把最后一个柱子上的所有盘子都移走,再放上去,再移回来。这个步骤最多 $2^{n-1} - 1 + 1 + 2 ^ {n - 1} - 1$ 次操作(由归纳假设)。如果不在,则最多只需要 $2 ^ {n-1} - 1$ 次操作。故若 $n-1$ 成立,$n$ 也成立。

​ $\tt{5. }$ 不可能。

​ 即,我们如果可能去表示,那么一个必要条件是 4 个圆能把平面分成 16 个区域。

​ 但是呢,还是用分平面的那一套结论。即,每次如果多分出来了 $x$ 个区域,那么一定恰好和目前存在的圆有 $x$ 个交点。所以,$4$ 个圆最多分成 14 个区域,所以不行。


2.29

​ $\tt{6.}$ 显然每次增加一条线段必然会增加两个无界区域,于是答案就是 $L_n - 2n$.

​ $\tt{7.}$