# 數學之美

###### tags: `MyNTUST`

[toc]

課程介紹
===

- 隨時可以打斷、沒有笨問題
- 可以上一頁
- 可以重講
- 禁止攝影錄音
- 投影片下課後會上傳到 CEIBA
- 成績
- 三次大考各占 1/3
- 考試時間
- 4/9
- 5/14
- 6/18
- 會根據系別調整計分方式
- 聲明
- 不是教你秒殺各種謎題
- 可以站起來走動聽課

人物介紹
===

- 費曼

> 要有數學的概念才能夠欣賞大自然的美。

- 哈代

> 數學式 **必須要** 如詩如畫般之美、如色如詞般和諧。唯。有美的數學式能名留青史。

- 艾狄胥

> 如果數字不是美，那什麼才是美？

- Paul Erdos
- 念作 air-\`dishes
- 數學界論文數量紀錄保持人
- 喜歡到處找人討論，所以成為共同作者
- 出版 Proofs from THE BOOK
- 本課課本
- THE BOOK
- 傳說上帝手中有一本書記載了世界上所有完美的數學式，稱為 THE BOOK。
- 批評：證明有點簡略
- Erdos number
- 跟 Erdos 的距離
- 跟 Erdos 合寫過論文的人(A)的 Erdos number 是 1
- 跟 A 合寫過論文者 Erdos number 是 2
- 以此類推

開胃菜 -- 三道謎題
===

問題一 -- 咖啡牛奶咖啡
---

有 500cc 純黑咖啡及 500cc 台大牛奶 5cc 的湯匙。舀一匙咖啡到牛奶並攪拌均勻，再舀一匙 *咖啡牛奶* 到黑咖啡並攪拌均勻。

- 問：咖啡牛奶的咖啡比例 vs. 牛奶咖啡的牛奶比例
- 解：

$咖啡牛奶的咖啡比例 = \frac 5 {505} = \frac 1 {101} = 0.00990099...$

$牛奶咖啡的牛奶比例 = ((500 / 505) * 5) / 500 = 1 / 101 = 0.00990099...$

> 無論如何都會是一樣的(即使攪拌不均)，只要最終兩杯都是 500cc 少的比例就會一樣

$咖啡牛奶 = x咖啡 + (500-x)牛奶$
$牛奶咖啡 = x牛奶 + (500-x)咖啡$

> **物質不滅定律**

問題二 -- 洗牌*
---

- 問：把牌洗亂需要幾次？（亂：所有組合的出現機率一致($\frac 1 {n!}$))

- 解
- Persi Diaconis: 7 riffle shuffle
- $\frac 3 2 log_n$

> 如果是 top-in shuffle 呢?

- 自解
| 牌數 | n! | 洗亂次數 |
| ---- | --- | -------- |
| 2 | 2 | 1 |
| 3 | 6 | 2 |

1/3 機率不變

(1/n)^m = 1/(n!)
= 1 / n^m = 1 / n!
= n^m = n!
= log_n n^m = log_n n!
= m = log_n n!

- 老師解

aim: 一開始最底部那張牌上升一格
phase 1: 有 1/52 的機率把最上面放到最下面，進到 phase 2
phase 2: 2/52 = 1/26, 進到 phase 3
phase 3: 3/52
.
.
.
進到 phase n+1 平均需要 52/n 次

次數上限：n(1/1+1/2+...+1/n) + 1

問題三 -- 海怪謎題
---

- a finite tree
- root
- 身體
- internal node
- 頸
- leaf
- 頭

九頭蛇(Hydra)每砍下一顆頭，該位置就會長出新頭。如果砍掉的頭長在身上，不會再生新的頭；如果砍掉的頭長在頸上，會把該頸以上的整支都複製兩份。

- 問：是否任何海怪都存在一個砍頭順序可以把海怪砍死（意即是否存在一個砍不死的海怪）。

- 答：
- PBS Infinite Series
- 任何順序都能砍死海怪
- 詳解

設計一個血量計算方式，若血量為自然數，且每次砍頭必定損血，則只要初始血量為有限，則海怪必定被砍死。

血量算法: 每個節點都有一個血量。leaf 的血量是 0，non-leaf 的 node 的血量為: 4 的 (child的血量) 的次方的加總，(ie. $\sum 4^{c_i}$)。

Q: 為甚麼是 4?
A: 在 node 上砍頭則 node 血量 -1。因為 4 的 C 次方 **剛好** 可以證明刀刀損血。

Q: 如果每次複製的份數會隨著回合數增加，是否仍必然可以殺死海怪？
A: ~~以後會專門做一部影片跟大家說明~~

~~植樹~~質數 Prime
===

> 定義：
> - 自然數
> - $p \ge 2$
> - If $q \mid p$ for a $q \in \mathbb{N}$, then $q \in { 1, p }$

有趣的冷知識
---

- 質數日
- YYYYMMDD 末 n 位都是質數。
- e.g. 20190523
- 20190523
- 0190523
- 190523
- ...
- 23
- 3
- 可左截質數
- 不可以有0
- 可右截質數
- 同樣不能有0
- 又名**質質數(prime prime)**
- 為什麼是有限的？
- 好問題，基本上是暴力搜尋的結果。
- Hint: 若所有n位質數往右(or 往左)加 1~9 都不是質數，則證明有限。
- 也許考試會考ww

質數是無限的
---

- 課本上有六個版本證明
- 歐基里德 - 《幾何原本》版
- 歸謬法
- 若我想證明一個假說成立，先假設他不成立，如果證明其矛盾，則證明假說成立。
- 解
1. 假設質數是有限的
2. 則可以列舉出一個集合 {P1...Pk}
3. 故，任何 >= 2 的自然數都可以從集合中找出一個可以整除他的數 ($Pi|n$)
4. 設 n = 1 + 所有P乘起來
5. 則 n >= 2
6. 則 Pi|n
7. 則 Pi 可以整除 n 及 n-1
8. a 可以整除 p 及 q，則 a 可以整除 |p-q|
9. 則 Pi 可以整除 n-(n-1)=1
10. Pi|1 且 Pi >= 2 (**矛盾**)
- Pi 為甚麼可以整除任何數？
- 任何數都可以質因數分解，所以任何數都可以被質數整除。
- 小提醒：證明過程中，可能會產生一些過渡性的性質，似乎可以作為另一個定律。但要注意，這些性質基於錯誤，且推出矛盾。這些性質**經常**是錯誤的。

梅森質數
---

> 2^p -1

- 五年前找到 49 個，但不確定是不是第49小的
- 目前不確定是不是無限多個

質數定理
---

- 小於 n 的質數的數量
- $\frac{n}{\ln n}$
- 證明過程用到複數
- 數學中常有需要用高層次解低層次問題的情況
- n 越大，質數密度越低(但低得很慢)

歌德巴赫 (Christian Goldbach) 猜想
---

> 任何大於 2 的偶數可以被寫成兩個質數的和

- 教授懸賞歌德巴赫畫像喔喔喔
- 學期成績 +5 分喔喔喔
- 寄錯的（已經被驗證過的）扣分喔
- 要怎麼驗證真的是呢？
- 應該由家族畫像中找起
- 寫在給尤拉的信中
- 沒有被證明也沒有被否證

RSA 加密
===

- 基於**因數分解很困難**
- 所以如果可以快速因數分解，RSA就不再安全

如何破解
---

1. 因數分解 n (最直接的方法)
2. 也許有其他目前未知的方法，但有證據顯示可能沒有

哥德巴赫的質數無限論
===

- 構造法
- 製造出無窮多個質數

質數無限一行證法
===

- 要記住，在歸謬法過程中推出的定理是不可以用在其他地方的

疊書問題
===

集合
===

- 從有無窮多個元素的集合內取走一個元素，總數有沒有減少?
- 拿下一個來遞補
- 抽掉p點
- p前: 對到自己
- p(含)後: 對到自己 + 1

實數無窮
---

- r 的小數點後第 n 位和第 n 個實數不同

Power Set
---

- S*在R*裡面可以推出S*不在R*裡面，S*不在R*裡面可以推出S*在R*裡面
- Q 整數的冪集跟實數集合的大小關係?
- 一樣大
- 其實只要證明前<=後就可以了
- 對到 0~1 間的小數
- 如果 n 在集合裡，小數點後第 n 為為 5
- 可不可以把恰有一個元素的子集和對應到該元素，從而耗盡S中的元素
- 可以，但單一個案不能證明全部
- 所以不能證明 A !<= B