---
# System prepended metadata

title: 數學之美
tags: [MyNTUST]

---

# 數學之美

###### 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