---
description: forum, 2020F, math203, discrete math, jephian, nsysu, 離散數學一, 林晉宏
tags: learning-together
---

# 離散數學（一）討論區 2020FMath203

## 使用說明

{%hackmd zPpOuVCmTK6AGJ1JS11Dfg %}

**[:arrow_right: 更多說明看這邊 :arrow_left:](/features-tw?both)**
數學式、表情符號......

## 討論區

:arrow_down: 新討論串從這邊開始 :arrow_down: （留言留在討論串最下面）

:::info
此區停止更新（也關閉修改權限），可以改在[網路大學](https://cu.nsysu.edu.tw/)上問問題／回答問題。
:::

### Big Oh and Little Oh
>複習時看到一個yt寫Little Oh 的證明，是需要先證明Big Oh的$f(n)<=c*g(n)$再證極限為0，而且我看到很多部影片中Little Oh定義都是寫$f(n)<=c*g(n)$，但是好像沒有看到筆記或課本有寫Little Oh需要先滿足Big Oh？希望不是我錯過了什麼:joy:
>[name=iwantA+][time=future][color=MediumSlateBlue]

> 的確 $f=o(g)$ 是比 $f=O(g)$ 強的條件
> 也就是 $f=o(g) \implies f=O(g)$
> 課本是說 $f=o(g)$ 的意思是 $\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)} = 0$
> 這句話等價於
> 對於任何 $c$，當 $n$ 夠大的時候都滿足 $0\leq f(n)/g(n) < c$。
> 希望有回答到你的問題～
> [name=Jephian Lin] [time=Thu, Oct 15] [color=teal]

### K(n,m)需要幾個蟲洞呢?
> 今天上課討論 $K_{3,3}$ 在杯上的問題，而其連線不交叉原因是上面有一個蟲洞，那如果要 $m$ 點連 $n$ 點不交岔會最少需要幾個蟲洞?
>[name=wei cheng] [time=Tue, Sep 11] [color=yourcolor]

> 設蟲洞有 $k$ 個，且 $m,n\in\mathbb{N}$，
> if $n=1$ 或 $2$ 或 $m=1$ 或 $2$ ，then $k=0$；
> if $n>2$ 且 $m>2$ ,then $k=(m-2)(n-2)$
> [name=Lifang Lu]
[time=Fri, Sep 11]
[color=LightSkyBlue]

> 如果能加上一些說明就太好了!
> [name=wei cheng] [time=Tue, Sep 11] [color=yourcolor]

> 第一個if應該很好理解。
> 而第二個if，除了m1、m2可以完全連接n個點，其餘的m點只能連接n最外面兩個點。
> BTW 大家時間是不是都亂打？
> [name=Lifang Lu]
[time=Fri, Sep 11]
[color=LightSkyBlue]

> 看來難的部份是說明**最少**須要這麼多個蟲洞！
> 方便起見，我們就說 $g(G)$ 是把圖 $G$ 畫出來不交叉最少所須的蟲洞個數。
> Lifang 已經說明了 $g(K_{m,n})\leq (m-2)(n-2)$。
> wei cheng 發現 $g(K_{3,n})\leq \lceil \frac{n-2}{2}\rceil$，畫法跟 Lifang 的想法差不多，先將 $K_{2,n}$ 畫在平面，然後再多加一個點。這時候發現一個蟲洞可以幫這個點連到內部的兩個點，所以可以省下一半的蟲洞。
> 但答案似乎是 $g(K_{3,n}) = \lceil\frac{n-2}{4}\rceil$。有辦法畫出來嗎？
> 可以把答案拍下來，再用上方的 <i class="fa fa-picture-o"></i> 上傳照片。
> [name=Jephian Lin] [time=Mon, Sep 14] [color=teal]

> 不會，坐等答案。
> [name=Mathisfun]
[time=Thu, Sep 17]
[color=magenta]

>我試驗了一下,狀況超出我想像QQ\
>中間的圖我畫錯了,$m_1$,$m_m$不用連\
>最後一個圖我試驗了K(3,6)，但我還是需要兩個wormhole，而不是老師的1個wormhole。
>
>
>\
>[name=Robinson Chiang][time=Wed, Oct 7][color=aqua]

:::success
wei cheng, AL point +0.5. :tada:
Lifang Lu, AL point +0.5. :tada:
Robinson Chiang, AL point +0.5. :tada:
:::

> 科科，那就再努力一下看看囉？還是你要挑戰 $K_{4,4}$？一樣一個洞。
> [name=Jephian Lin] [time=Sat, Oct 10] [color=teal]

### 第一次上課算的那個數字是什麼？
> 第一次上課的時候老師叫我們[算一個 0~6 的數字](https://hackmd.io/@jephianlin/2020FMath203-notes#%E6%9A%96%E8%BA%AB%E4%B8%80%E4%B8%8B)是幹麻的？如果只是要拿來分組應該不用那麼複雜吧？
> [name=I love math] [time=Fri, Aug 7] [color=magenta]

> 感覺就是讓課程有趣一點安餒
> [name=yourname] [time=maybe Wed,Sep 9] [color=MediumSlateBlue]

> 有讓課程有趣一點就好，不過不只這樣喔。（樓上記得寫時間和選顏色～）
> [name=Jephian Lin] [time=Thu, Sep 10] [color=teal]

### 重複物件時環狀排列的公式
>課本有提到重覆物件的環狀排列,請問它的公式是甚麼?以及它是如何推導的
>[name=YEH JUEWE WEN]

:::info
thread closed.
moved to [archive](https://hackmd.io/JZVj9q36RqeVuoYRcrmfLQ#%E9%87%8D%E8%A4%87%E7%89%A9%E4%BB%B6%E6%99%82%E7%92%B0%E7%8B%80%E6%8E%92%E5%88%97%E7%9A%84%E5%85%AC%E5%BC%8F).
:::

### 上課講的那串數字到底是什麼？
> $1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6, \ldots$
> [name=Jephian Lin] [time=Tue, Sep 22] [color=teal]

:::info
thread closed.
moved to [archive](https://hackmd.io/JZVj9q36RqeVuoYRcrmfLQ#%E4%B8%8A%E8%AA%B2%E8%AC%9B%E7%9A%84%E9%82%A3%E4%B8%B2%E6%95%B8%E5%AD%97%E5%88%B0%E5%BA%95%E6%98%AF%E4%BB%80%E9%BA%BC%EF%BC%9F).
:::

### 鋪地磚
> 考慮排成一排的 $n$ 個正方格，如果手上有兩種地磚，一種是 $1\times 1$、一種是 $1\times 2$，令 $a_n$ 為用這兩種地磚鋪滿整排的方法數（e.g., $a_1=1$, $a_2=2$），求 $a_n$？
> [name=Jephian Lin] [time=Wed, Sep 16] [color=teal]

:::info
thread closed.
moved to [archive](https://hackmd.io/JZVj9q36RqeVuoYRcrmfLQ#%E9%8B%AA%E5%9C%B0%E7%A3%9A).
:::

### 近視會傳染 :scream:
> 誤用數學歸納法會得到奇怪的結論。請拋開一切日常的直覺，細細品味以下的證明，並思考問題出在哪？
> **敘述 $S_n$**：若 $n$ 個人之中有一人近視，則全部 $n$ 個人都會近視。
> **basic step**： 當 $n=1$ 時，敘述 $S_1$ 是正確的，的確如果 1 人之中有一人近視，則全部（只有 1 個人）都會近視。
> **indutive step**：
> 假設 $S_n$ 成立。
> 考慮一群 $n+1$ 個人組成的集合 $A = \{p_1,\ldots,p_{n+1}\}$，並假設其中有一人近視。不失一般性，令近視的人叫 $p_1$。
> 令 $B = \{p_1,\ldots,p_{n}\}$ 及 $C = \{p_2,\ldots,p_{n+1}\}$ 為兩群人數為 $n$ 的集合。
> 因為 $B$ 有 $n$ 個人且 $p_1$ 近視，根據歸納法假設，$B$ 中的所有人都會近視；如此一來，我們知道 $p_2$ 也有近視。
> 這時 $C$ 有 $n$ 個人且 $p_2$ 近視，根據歸納法假設，$C$ 中的所有人都會近視；如此一來，$A$ 中的所有人都近視。
> 我們得到 $S_n$ 成立 $\implies$ $S_{n+1}$ 成立。
> 根據數學歸納法，近視會傳染。（請小心你周圍有近視的同學...）
> [name=Jephian Lin] [time=Fri, Oct 2] [color=teal]

:::info
thread closed.
moved to [archive](https://hackmd.io/JZVj9q36RqeVuoYRcrmfLQ?view#%E8%BF%91%E8%A6%96%E6%9C%83%E5%82%B3%E6%9F%93-).
:::

### 教師節快樂！:mortar_board:
> :rolling_on_the_floor_laughing::rolling_on_the_floor_laughing::rolling_on_the_floor_laughing:
> 表情符號顯示不出來QQ
> [name=mathisfun]
[time=Sat, Mon 28]
[color=magenta]

:::info
thread closed.
moved to [archive](https://hackmd.io/JZVj9q36RqeVuoYRcrmfLQ#%E6%95%99%E5%B8%AB%E7%AF%80%E5%BF%AB%E6%A8%82%EF%BC%81).
:::

### $S(n)\leq n\log_2n$ 的完整證明
> 如果 $S(2) = 1$, $S(4) = 6$, $S(2n) = 2n + 2S(n)$。
> 證明 $S(n)\leq n\log_2n$ 對於所有 $n=2^k, k\geq 1$。
> [name=Jephian Lin] [time=Sat, Sep 26] [color=teal]

:::info
thread closed.
moved to [archive](https://hackmd.io/JZVj9q36RqeVuoYRcrmfLQ#Snleq-nlog_2n-%E7%9A%84%E5%AE%8C%E6%95%B4%E8%AD%89%E6%98%8E).
:::

### `sumrecursive`
> 參考課本的[程式](https://rellek.net/book/s_induction_statements.html#sage-4)。
> 計算 $\sum_{n=1}^{50} (-1)^n - 2^n + 10$ 的值，並附上你的程式碼。
> [name=Jephian Lin] [time=Thu, Sep 24] [color=teal]

def sumrecursive(n):
    if n == 1:
        return 2;
    else:
        return sumrecursive(n-1) + (n*n - 2*n + 3)
sumrecursive(3)

:::info
thread closed.
moved to [archive](https://hackmd.io/JZVj9q36RqeVuoYRcrmfLQ#sumrecursive).
:::

### 隔一格、隔兩格？
> 考慮一排 $n$ 個座位，要選 $k$ 個位置放坐墊。
> 如果一個座位可以放多個座墊，那放法有 $H^n_k$ 種。（坐墊和坐墊之間沒距離）
> 如果一個座位只能放一個坐墊，那放法有 $C^n_k$ 種。（坐墊和坐墊之間距離至少為 $1$）
> 如果坐墊和坐墊之間距離至少為 $2$（就是一定要隔一格），那放法有幾種？
> 如果坐墊和坐墊之間距離至少為 $3$（就是一定要隔兩格），那放法有幾種？
> [name=Jephian Lin] [time=Sun, Sep 20] [color=teal]

:::info
thread closed.
moved to [archive](https://hackmd.io/JZVj9q36RqeVuoYRcrmfLQ#%E9%80%99%E5%80%8B%E7%AD%89%E5%BC%8F%E6%80%8E%E9%BA%BC%E8%AD%89%E6%98%8E%EF%BC%9F).
:::

### 這個等式怎麼證明？
> 如果 $a+b = n$，則
> $$\binom{n}{k} = \binom{a}{0}\binom{b}{k} + \binom{a}{1}\binom{b}{k-1} + \cdots +\binom{a}{k}\binom{b}{0}.$$
> [name=Jephian Lin] [time=Wed, Sep 16] [color=teal]

:::info
thread closed.
moved to [archive](https://hackmd.io/JZVj9q36RqeVuoYRcrmfLQ#%E9%80%99%E5%80%8B%E7%AD%89%E5%BC%8F%E6%80%8E%E9%BA%BC%E8%AD%89%E6%98%8E%EF%BC%9F).
:::

### 這個數列會不會停下來？
> 課本題到一個數列叫作 Collatz sequence，它的做法是這樣：
> 1. 選一個正整數 $n$
> 2. 如果 $n$ 是奇數，則 $n \leftarrow 3n+1$
> 3. 如果 $n$ 是偶數，則 $n \leftarrow n/2$
> 4. 一直重覆步驟 2 和 3 直到 $n$ 變為 $1$ 為止。
> [color=teal]

> 比如說 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1。我試了很多數都會停下來，它真的都會停下來嗎？
> [name=Jephian Lin] [time=Tue, Sep 8] [color=teal]

:::info
thread closed.
moved to [archive](https://hackmd.io/JZVj9q36RqeVuoYRcrmfLQ#%E9%80%99%E5%80%8B%E6%95%B8%E5%88%97%E6%9C%83%E4%B8%8D%E6%9C%83%E5%81%9C%E4%B8%8B%E4%BE%86%EF%BC%9F).
:::

### 我要怎麼新增討論串？
> 好多功課我都不會，想和大家討論，請問要怎麼把問題貼上來呢？
> [name=I love math] [time=Fri, Aug 7] [color=magenta]

> 請參考[新增討論串或留言](#%E6%96%B0%E5%A2%9E%E8%A8%8E%E8%AB%96%E4%B8%B2%E6%88%96%E7%95%99%E8%A8%80)中的說明。
> [name=Jephian Lin] [time=Sat, Aug 8] [color=teal]

---

## 聊天測試區

> 歡迎～我把你的留言移到下面來。
> [name=Jephian Lin] [time=Sat, Aug 8] [color=teal]

> 哈囉，我只是上來打個招呼
> [name=blackpink][time=Wed, Sep 9][color=black]

### 怎樣才能加入系:volleyball:？
> 怎樣才能加入系排？
> [name=I love math] [time=Fri, Aug 7] [color=magenta]

---

## 英文單字區
- preliminary: 基本的、先備知識
- pattern: 模式
- algorithm: 演算法
- category: 類別
- metro: 捷運
- concrete: 具體的
- precise: 精準的
- postulate: 公理
- Euclid: 歐幾里得