约瑟夫问题 The Josephus Problem

归纳

`第一归纳法`

对于有n节的梯子，我们想要从第一节爬到第n节，可以使用如下的方法：

可以爬到第一节
如果可以爬到第k节，那么我们可以爬到第k+1节

现在我们先假设以上两句都成立，这样可以使用递归的方式来爬到第n节楼梯:

首先可以爬到第1节楼梯，然后令k=1，由第二句可知我们可以爬到第2节，再令k=2，则可以爬到第3节。以此类推就可以爬到第n节了.

`强归纳法`

用感性的语言来描述其实就是,强归纳法的强在于他的假设条件确实很强,同样拿上面第一归纳法的爬来举例,我们的假设如果是可以爬到任意有限数量的一段楼梯,即$m_0\to m$这些节楼梯,可以推出可以爬到$m+1$节楼梯那么从$m_0$楼梯开始的任意节都是可以爬到的.多么强大的归纳法啊,上来就假设任意有限长度的楼梯都是可以爬到的,只要推到出来下一节是可以爬到的就可以完成归纳,其实简单的来看如果假设仅一节楼梯是可以爬到的,那么不就退化到来第一归纳法的形式了嘛?这样看来强归纳法的强确实很强. 那么怎么从第一归纳法推导出强归纳法来呢?

Exercise 2.2.5. Prove Proposition 2.2.14.¹

Proposition 2.2.14 (Strong principle of induction). Let $m_0$ be a natural number, and let $P(m)$ be a property pertaining to an arbitrary natural number $m$. Suppose that for each $m \geq m_0$, we have the following implication: if $P\left(m^{\prime}\right)$ is true for all natural numbers $m_0 \leq m^{\prime}<m$, then $P(m)$ is also true. (In particular, this means that $P\left(m_0\right)$ is true, since in this case the hypothesis is vacuous.) Then we can conlude that $P(m)$ is true for all natural numbers $m \geq m_0$.

Solution: Let $Q(n):=(P(m)\text{. is true,}\forall{m_0}\leq{m<n}),Q(n)$ is true if $n<m_0$ The conclusion is equivalent to $Q(n)$ is true, $\forall n \geq m_0$. Case $m_0: Q(m_0)$ is true since $m_0 \leq m<m_0$ is impossible. If case $n$ is true, i.e. $Q(n)$ is true, then $Q(n++)=(P(k)\text{ is true, }\forall m_0 \leq k<n++)$ Since $Q(n)$ is true, we see $P(k)$ is true, $\forall m_0 \leq k<n$, thus $P(n)$ is true and so $Q(n++)$ is true.

两人拿签

考虑一个取火柴的游戏²，其中两名选手轮流从两堆火柴中的一对取出任意数目整数的火柴，取走最后一根火柴的人获胜。求证：当每堆开始有n根火柴的时候，后手一定会赢。

假设游戏开始时有每堆有$N$根火柴,那么可以假设只要每堆有${N-1}\implies{1}$根火柴都时后手赢,那么无论先手拿了几根,后手都可以拿根先手同样的根数使得情况变成每堆有${N-1}\implies{1}$的情况,即满足强归纳法,得证.

在网页上输入数学公式真是一件很啥比的行为.