作者fragmentwing (片翼碎梦)
看板Math
标题[离散] 数学归纳法、强数学归纳法的n=1
时间Tue Oct 27 10:41:08 2020
感觉愈写反而愈抓不太到数学归纳法对於第一步骤和最後一步骤的要求
像是邮票题目 证明除1、3、4、7外，皆可用3、5元邮票组合成
＜解法＞
n=3 ：3=3
n=5 ：5=5
n=8 ：8=3+5
n=9 ：9=3+3+3
n=10：10=5+5
设n<k成立，consider n=k
n-3小於k成立 加回去变k
n-5小於k成立 加回去变k
关於最後这一项，不知道到底该证明几个n-x的状况才够
也不知道第一项到底是不是证明到n=10就足够
然後另外一个搞不懂的状况是，马颜色同一种的延伸题目，如下：
关於盖金字塔
一粒沙盖不起来
k粒沙盖不起来
k+1粒沙盖不起来
所以人类盖不出金字塔
改成这样就不知道怎麽抓逻辑漏洞了
对数学归纳法一直都不是有办法很信任
假设我看到一个数列都是2，我要怎麽才能知道前方不会有个1？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.71.214.119 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1603766473.A.2F3.html
※ 编辑: fragmentwing (111.71.214.119 台湾), 10/27/2020 10:44:41
1F：→ hwanger : 数学归纳法是关於无限的定理 对他不信任是正常的 10/27 11:00
2F：推 Ciolos : 盖金字塔的问题是，你要先定义清楚什麽叫做金字塔， 10/27 11:00
3F：→ Ciolos : 五粒沙叠成类似四面体的形状可以是金字塔吗？没有明 10/27 11:00
4F：→ Ciolos : 确金字塔的定义，你要怎麽证明k+1粒沙盖不成？ 10/27 11:00
5F：→ hwanger : 但使用数学归纳法时你永远要确保两件事 第一件事是 10/27 11:01
6F：→ hwanger : 起点是存在的 第二件事是链锁是一定会发生的 10/27 11:02
7F：→ hwanger : 关於盖金字塔 你并没有保证链锁一定会发生 也就是 10/27 11:02
8F：→ Ciolos : 另外你看到数列都是2，不知道前项，所以你没有起始 10/27 11:03
9F：→ Ciolos : 条件（或者起始条件只能从2开始），另外你也没办法 10/27 11:03
10F：→ Ciolos : 证明2的下一项一定是2，所以数学归纳法本来就没办法 10/27 11:03
11F：→ Ciolos : 用在这个问题上。 10/27 11:03
12F：→ hwanger : 你没有正当的理由说明P(k)发生时 P(k+1)是无法发生 10/27 11:03
说到这个 其实马的题目也能这样证吧 但不知道为什麽 看大家的解法都是用无法重叠去破解
13F：→ hwanger : 或一定发生的 10/27 11:04
※ 编辑: fragmentwing (111.71.214.119 台湾), 10/27/2020 11:05:28
14F：→ hwanger : 看到一个数列前头都是2 你没有任何理由保证链锁一定 10/27 11:06
15F：→ hwanger : 会发生 自然就不知道下一个是什麽 10/27 11:07
16F：→ hwanger : 马的题目是什麽?? 10/27 11:08
任n匹马具相同颜色
n=1成立
设n＝k成立
考虑n=k+1
然後就会讲到overlap、重叠之类的
17F：→ hwanger : 另外邮票题目是可以3x+5y=n n>=8 一定有正整数解去 10/27 11:11
18F：→ hwanger : 看的 用数论的方法就能解释 虽然文中数学归纳法是正 10/27 11:12
19F：→ hwanger : 确的 但如果你不放心 你可以用其他方法证 10/27 11:13
可是关於最後一步骤 如果今天题目写1，2，3，4以外皆可由5元邮票组成 那最後一步骤时写一个k-5可组成k就成了?
※ 编辑: fragmentwing (111.71.214.119 台湾), 10/27/2020 11:14:34
20F：→ hwanger : 喔喔 我知道马的问题了 马的问题是在你没有确保链锁 10/27 11:15
※ 编辑: fragmentwing (111.71.214.119 台湾), 10/27/2020 11:16:21
21F：→ hwanger : 一定发生 也就是P(k) implies P(k+1)这件事对所有的 10/27 11:16
22F：→ hwanger : k都会成立 因为论述中不能适用在k=1的情况 10/27 11:17
23F：→ hwanger : 我不太懂overlap是指什麽 马的问题缺失是在P(1)推不 10/27 11:19
「因为在证两匹马时，前半後半个1，没有overlap」只有在n大於等於3时有overlap之情形，所以无法用p(1)来证得p(2)
24F：→ hwanger : 到P(2) 10/27 11:19
25F：→ hwanger : "可是关於最後一步骤...">>>可是你没有确保起点存在 10/27 11:20
26F：→ hwanger : 呀 数学归纳法中"起点存在"和"链锁一定发生"是同样 10/27 11:21
所以我才会想起点的状况要列到什麽程度才够
※ 编辑: fragmentwing (111.71.214.119 台湾), 10/27/2020 11:21:56
27F：→ hwanger : 重要的 有些书写证明会省略这个或那个 是因为有时他 10/27 11:22
※ 编辑: fragmentwing (111.71.214.119 台湾), 10/27/2020 11:23:15
28F：→ hwanger : 是显然的 不是因为他不用check 10/27 11:23
29F：→ hwanger : 例到最小的k-3或k-5会存在就好了 10/27 11:25
30F：→ hwanger : 如果真的无法理解 那就列8,9,10 然後分别考虑3k, 10/27 11:28
31F：→ hwanger : 3k+1,3k+2的情况就好了 不用特别去想k-3或k-5 10/27 11:29
32F：→ hwanger : 也就是一次证三个数学归纳法 10/27 11:30
33F：→ hwanger : Ok 我可能懂你的问题在哪了 你列的东西并没有保证 10/27 11:33
34F：→ hwanger : k>=11时 k-5一定会发生 但其实k-5这条是多余的 考虑 10/27 11:34
35F：推 TimcApple : 你以为骨牌排好就会连倒 结果没有 10/27 11:36
36F：→ hwanger : k-3就好了 而比较严谨的证明就如上所述 你要分别在 10/27 11:36
37F：推 Ciolos : 马的问题那个错误证明是「假设n匹马颜色相同，那1,2 10/27 11:36
38F：→ Ciolos : ,...,n号马颜色相同，又2,3,...,n+1号马颜色相同， 10/27 11:36
39F：→ Ciolos : 所以1,2,...,n+1号马颜色都相同，问题是你只能假设 10/27 11:36
40F：→ Ciolos : 某n匹马颜色(A色）一样，另一群n匹马颜色（B色）一 10/27 11:36
41F：→ Ciolos : 样，但这n匹和那n匹不一定会有重复的马」 10/27 11:36
关於这叙述我最不能理解的是怎麽跑到2,3,...,n+1号马颜色相同上去的
42F：→ TimcApple : 这不是物理的错 是排骨牌的人手残ow o 10/27 11:36
43F：→ hwanger : 除3余1 除3余2 除3余0的cases上各自作数学归纳法 10/27 11:37
我了解书上为何要省略了，太占空间啦
44F：→ hwanger : ??? 马的问题 "P(n) implies P(n+1)"n大於1时是对的 10/27 11:41
※ 编辑: fragmentwing (111.71.214.119 台湾), 10/27/2020 11:41:47
※ 编辑: fragmentwing (111.71.214.119 台湾), 10/27/2020 11:43:26
45F：→ hwanger : 他的论证也没问题 可是数学归纳法是要求"P(n) 10/27 11:42
46F：→ hwanger : implies P(n+1) for all n" 数学有很多定理 条件差 10/27 11:43
47F：→ hwanger : 一点点 结论就会错了 10/27 11:43
48F：→ hwanger : 用T大的比喻就是 你骨牌在台湾排好了 但你起点却在 10/27 11:48
49F：→ hwanger : 美国 10/27 11:48
50F：→ hwanger : "关於这叙述我最不能理解...">>>因为P(n)的叙述是对 10/27 11:50
51F：→ hwanger : 於任意n只马 其颜色都相同 10/27 11:51
52F：→ hwanger : 那你现在假设P(n)是对的 所以1,2,...,n是"任意n只马 10/27 11:52
53F：→ hwanger : 2,3,...,n+1也是任意n只马 所以1和2同颜色 2和n+1也 10/27 11:53
54F：→ hwanger : 同颜色 你会觉得奇怪 是因为你一开始就知道P(n)不可 10/27 11:54
55F：→ hwanger : 能是对的 但在implication中 前项恒错 叙述恒真 10/27 11:56
56F：→ hwanger : 深究一下金字塔问题 其谬误在於你假设前k粒因为建不 10/27 12:01
57F：→ hwanger : 起金字塔 所以就不重要了 再加一粒不重要的 所以还 10/27 12:01
58F：→ hwanger : 是不重要 但假设你今天走路 你一步跨不出一百公尺 10/27 12:03
59F：→ hwanger : 你接下来每步都跨不出一百公尺 所以你走不到一百公 10/27 12:04
60F：→ hwanger : 尺? 10/27 12:04
61F：→ Ciolos : 因为他把某n匹马颜色相同偷换概念成任n匹马颜色相同 10/27 12:10
62F：→ Ciolos : ，你不能理解是因为那是错的 10/27 12:10
63F：→ hwanger : 马的题目本来就是要证任意n匹马 颜色都相同 数学中 10/27 12:14
64F：→ hwanger : 的题目 本来就是没有特别讲存在 就是for all 10/27 12:14
65F：→ hwanger : 他没有把概念偷换掉 证明会错也不是因为什麽概念被 10/27 12:16
66F：→ hwanger : 偷换的关系 纯粹就是因为P(1)无法用他想用的论证推 10/27 12:17
67F：→ hwanger : 到P(2) 10/27 12:17
68F：→ hwanger : "if n>1, P(n) infers P(n+1)"原本要作的论证是形式 10/27 12:18
69F：→ hwanger : 上对的 但其意义是违反直觉的 10/27 12:19
70F：推 TimcApple : 马的题目 数归的证明在 n > 1 的时候都会对 10/27 13:07
71F：→ TimcApple : 如果题目改成「若任两匹马颜色一样 10/27 13:08
72F：→ TimcApple : 则所有马颜色一样」这样用数归证就不会错 10/27 13:08
73F：→ TimcApple : 毕竟起点是 2 不是 1 了 10/27 13:08
74F：→ TimcApple : 也没有什麽违反直觉的地方 10/27 13:08
75F：→ TimcApple : 原本的问题 完全就只错在 P(1) 到 P(2) 10/27 13:10
76F：→ TimcApple : 然而一步错步步错 证出了鬼扯的结果而已 10/27 13:10
77F：→ hwanger : 违反直觉的地方是指为什麽要假设P(n)(意即前提已经 10/27 13:21
78F：→ hwanger : 错了 为何要再证P(n)→P(n+1) 而不是说"n>1 P(n)→ 10/27 13:23
79F：→ hwanger : P(n+1)"这件事是对的违反直觉的 至於把起点改为2 也 10/27 13:25
80F：→ hwanger : 是不能用数学归纳法 因为没有保证起点是对的 10/27 13:26
81F：→ hwanger : 我误会了 "若任两匹马颜色一样 则所有马颜色一样"已 10/27 14:34
82F：→ hwanger : 经和原本马问题无关了 实际上也不需要用数学归纳法 10/27 14:35
83F：→ hwanger : 去证明 10/27 14:35
84F：推 LPH66 : 并没有无关喔, 後一问题是原问题改变 base case 10/27 16:50
85F：→ LPH66 : 後一问题能用原论证证明表示原论证本来就无误 10/27 16:51
86F：→ LPH66 : 问题完全只在 P(1)→P(2) 无法用原论证证明 10/27 16:51
87F：→ LPH66 : 但就因为这一个无法证明使得结论变为荒谬 10/27 16:52
88F：→ hwanger : 原本问题是"对於任意n匹马 这n匹马颜色都相同" 10/27 17:34
89F：→ hwanger : 形式是" for all x1,x2,...xn, Q(x1,x2,...,xn)" 10/27 17:34
90F：→ hwanger : 改过的问题是"对於任意n匹马 若任意两两颜色相同 则 10/27 17:34
91F：→ hwanger : 这n匹马颜色相同" 10/27 17:34
92F：→ hwanger : 形式是 "for all x1,x2,...,xn, if for all i,j A(x 10/27 17:34
93F：→ hwanger : i,xj), then Q(x1,x2,....,xn)" 10/27 17:34
94F：→ hwanger : 第2个问题只要固定其中一匹马 大家都跟这匹马相比即 10/27 17:34
95F：→ hwanger : 可 10/27 17:34
96F：→ hwanger : 就算硬要用数学归纳法证 两者的induction hypothesi 10/27 17:34
97F：→ hwanger : s也不同 10/27 17:34
98F：→ hwanger : 第一个P(n):对於任意n匹马 这n匹马颜色都相同 10/27 17:34
99F：→ hwanger : P(n)推P(n+1):若"任意n匹马 这n匹马颜色都相同" 则 10/27 17:34
100F：→ hwanger : "任意n+1匹马 这n+1匹马颜色都相同" 10/27 17:34
101F：→ hwanger : 第二个P(n):对於任意n匹马 若任意两两颜色相同 则这 10/27 17:34
102F：→ hwanger : n匹马颜色相同 10/27 17:34
103F：→ hwanger : P(n)推P(n+1):若"对於任意n匹马 若任意两两颜色相同 10/27 17:34
104F：→ hwanger : 则这n匹马颜色相同" 则 "对於任意n+1匹马 若任意 10/27 17:34
105F：→ hwanger : 两两颜色相同 则这n+1匹马颜色相同" 10/27 17:34
106F：→ hwanger : 用到的假设和要证的东西已经不同了 你说用类似的想 10/27 17:34
107F：→ hwanger : 法证ok 但直接用原论证一定是不行的 10/27 17:34
108F：→ hwanger : 最简单的看法就是 从n+1匹马选出n匹马後 在第一个 10/27 17:34
109F：→ hwanger : 情况 这n匹马就是同颜色的 但在第二个情况 你必须 10/27 17:34
110F：→ hwanger : 先check任意两两相同颜色 才能下结论这n匹马同颜色 10/27 17:34
111F：→ hwanger : 两者推到选出来的n匹马同颜色的方式不同 10/27 17:34
112F：→ hwanger : 荒谬的是"对於任意n匹马 这n匹马颜色必然相同" 10/27 17:39
113F：→ hwanger : "对於任意n匹马 若两两颜色相同 则这n匹马颜色必然 10/27 17:39
114F：→ hwanger : 相同"则完全没问题 10/27 17:39
115F：→ hwanger : 两个问题形式已经不同 说是相关勉强可以 但并不是 10/27 17:45
116F：→ hwanger : 谁基於谁 我认为无关 就是他们形式上已经无关 前者 10/27 17:45
117F：→ hwanger : 有问题的证明 也没办法直接给後者用(实际上也不需要 10/27 17:45
118F：→ hwanger : ) 10/27 17:45