Homework 1

Problem 1

(a) 二者都是 , 故

(b)

(c)

取对，两边分别为

而

(d)

直接考虑

不难发现

即知

Problem 2

single-digit number 至多为 ，则他们的和至多为 ，题意即证

这由

易知

Problem 3

记作 ，显然

另一方面，由于 时

故

综上，证毕

Problem 4

如果 ，则 显然

如若不然，则由等比数列求和公式，

若 ，则

若 ，则

Problem 5

本来想类似遍历点然后从点找邻居 DFS 的形式，但后面发现有点复杂化了而且邻居不唯一导致理论上不严密

考虑类似 Bounded Search Tree 的算法

由于 每迭代一次都减少，故迭代深度为 ，而 branch factor 为 ，故保证了总搜索节点数为 ，而每个节点的工作量为 ，满足题目要求

Problem 6 (Optional)

Question 1

K2 显然满足（因为 ）

下面关注 K1: 考虑对 进行改造：我们知道第 6 步时的图是否有大小不大于 的点覆盖和 是否有大小不大于 的点覆盖是等价的，那么我们对 再做一次 步的过程，即 ，随后去掉 中度数不小于 的点，每次减小 ，再去除 isolate point ，得到 ，此时的 是否有 的点覆盖与最初的 等价

1. 这个过程中，isolate point 什么时候被去掉不影响结果，因为 isolate point 一旦生成就永远不会在 for 循环中去掉，只可能在单独 remove 时被去掉
2. 如果我们反复进行如上的过程，过程能够持续的条件是 for 循环中剩下的点的最大度数不止不大于 ，还不大于 ，因此如果我们将去除点的标准直接定为 ，就相当于不断迭代这个过程
3. 中的 过程在什么时候进行也是不重要的，因为其本质上只是一个对没有满足要求点覆盖的情况进行剪枝的过程，只要在最后进行一次就可以了，甚至不管做不做都不影响等价性。

综上， 的 就是把 的 反复迭代的过程，因而保持了等价性，即 K1

Question 2

如下