分類
數學

中國剩餘定理

這是個古老的數學問題, 當然也有對應的解法. 在解這個數學問題之前, 我們先來看簡單一點的題目, 就是相同餘數的數字.

舉例來說, 某數除以 7 餘 4, 除以 13 也餘 4, 則某餘最小的自然數為何?

計算方式還蠻單純的, 就是 7 和 13 的最小公倍數, 再加上 4 即得, 如下:

lcm(7,13) = 91, 由於兩數互質, 所以最小公倍數就是該兩數的乘積, 故答案則為 91 + 4 = 95

另一個變形的題目, 某數除以 7 餘 5, 除以 13 餘 11, 除以 15 餘 13, 則某數的最小自然數為何?

再看一下題目, 雖然和上面的同餘數不太一樣, 不過有個規律, 就是都差 2 就會整除, 也就是雖然餘數不一樣, 但同樣少了 2, 所以計算方式也很類似, 找出 7, 13, 15 的最小公倍數, 然後減 2就是答案了, 如下:

lcm(7, 13, 15) = 1365, 故答案為 1365 – 2 = 1363

以上兩種都是比較單純的餘數問題, 再來看看這個中國餘數定理的問題:

孫子算經中的: 有物不知其數,三三數之剩二,五五數之剩三,七七數之剩二。問物幾何?

換成數學白話, 某數除以 3餘 2, 除以 5餘 3, 除以 7餘 2, 某數為何?

這個既不是同樣的餘數, 也不是同樣的差某一值可整除, 要如何解呢? 這時會用到一些餘數的式子, 可以先參考這裡: http://www.mikekong.net/Maths/Problems/chinese_remainder02.html

所以只需要先找出 5, 7 的公倍數, 除以 3餘 1的; 再找出 3, 7的公倍數, 除以 5餘 1的; 再找出 3, 5的公倍數, 除以 7餘 1的, 如下:

找出 5, 7 的公倍數, 除以 3餘 1的: 5 x 7 x 2 = 70, 該數除以 3會餘 1
找出 3, 7的公倍數, 除以 5餘 1的: 3 x 7 = 21, 該數除以 5會餘 1
找出 3, 5的公倍數, 除以 7餘 1的: 3 x 5 = 15, 該數除以 7會餘 1

然後利用:
a ≡ b (mod m) 則 ac ≡ bc (mod m) 這個式子(注意反之不然), 得
70 ≡ 1 (mod 3) … (a)
21 ≡ 1 (mod 5) … (b)
15 ≡ 1 (mod 7) … (c)
因為要除以 3餘 2, 所以 (a) x 2:
70 x 2 ≡ 1 x 2 (mod 3) … (d)
因為要除以 5餘 3, 所以 (b) x 3:
21 x 3 ≡ 1 x 3 (mod 5) … (e)
因為要除以 7餘 2, 所以 (c) x 2:
15 x 2 ≡ 1 x 2 (mod 7) … (f)

再利用:
a ≡ b (mod m) 則 a + c ≡ (b + c) (mode m) 這個式子,
並綜合以上 (d), (e), (f) 得該數應為
x ≡ (70 x 2 + 21 x3 + 15 x 2)(mod 105)

所以最小的某數應為 23, (即 70×2 + 21×3 + 15×2 – 105×2 = 23)

相關閱讀:
http://zh.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E4%BD%99%E6%95%B0%E5%AE%9A%E7%90%86
http://www.mikekong.net/Maths/Problems/chinese_remainder02.html
http://www.geocities.ws/goodprimes/SCCongruence.html

分類
數學

有趣的機率-Monty Hall problem

這是個有趣的數學機率問題.

電視節目上, 有三個門, 其中只有一個門有汽車, 而另外兩個門後面沒有東西, 讓參賽者上台選擇. (原節目中的內容是空門後放山羊), 圖示如下:

一般的狀況下, 為了增加收視率, 提升刺激性, 主持人會參與, 把其中一個沒有東西的門打開, 讓參賽者再來選擇, 是否要更換門, 來選擇獲得汽車大獎的可能. 理論上是換而獲得的機會會增加.

這個問題表面上看起來的確不是這麼一回事, 主要是定義明確性的問題, 會導致想法發生誤解. 若是先把條件說明清楚的狀況下, 就是一個蠻單純的數學機率問題了.

這個問題叫做 蒙提霍爾問題 (Monty Hall problem). 可以參考 wikipedia 上的資料(link).

接下來來定義一下問題.

  1. 有三個門, 而參賽者不知後方的汽車在哪個門
  2. 主持人知道汽車在哪個門, 並會在參賽者選好門後, 總是開啟剩下兩個門中, 其中一個沒有汽車的門.
  3. 參賽者可以獨立選擇要換或是不換.

再來分析看看獲獎狀況的機率:

  1. 參賽者選空門1, 主持人選空門2, 參賽者換門後獲獎.
  2. 參賽者選空門2, 主持人選空門1, 參賽者換門後獲獎.
  3. 參賽者選汽車, 主持人選任一門, 參賽者換門後失敗.

從上述的狀況來看, 參賽者在總是換門的結果下, 只有一開始選中汽車的狀況下不會獲獎, 否則就會因為換了門而獲獎, 如此一來, 便能看出, 總是換門會有較高的獲獎機會 2/3 : 1/3, 也就是獲獎機會倍增的由來.

因為很容易發生直覺上誤判的問題, 所以這個問題, 也常被稱之為蒙提霍爾悖論, 十分有趣.

參考資料:
http://zh.wikipedia.org/zh-tw/%E6%A6%82%E7%8E%87%E8%AE%BA
http://zh.wikipedia.org/zh-tw/%E8%92%99%E6%8F%90%E9%9C%8D%E7%88%BE%E5%95%8F%E9%A1%8C

[2010/5/28 21:05]剛看到一個影音版的說明, 也順便提供給大家參考:
引用自: http://www.im.tv/vlog/personal/879704/6278986

分類
數學

數學證明題-平方和

還記得高中有學過證明累加的公式算法嗎? 利用數學歸納法來證明公式是否正確的一個方法, 為了再次熟悉以前的數學, 整理一下數學歸納法的方式.

先來看看 wikipedia 上的定義吧: http://zh.wikipedia.org/zh-tw/%E6%95%B0%E5%AD%A6%E5%BD%92%E7%BA%B3%E6%B3%95

利用數學歸納法, 可以證明數學問題的公式, 例如我們要證明平方和這個公式為 n(n+1)(2n+1)/6 於是就利用如下的步驟:

  1. 當 n = 1 時, 1^2 = 1, 1 * (1+1) * (2 * 1 + 1) / 6 = 1 成立
  2. 假設 n = m 時, 1^2 + 2^2 + 3^2 + … + m^2 = m(m+1)(2m+1)/6 成立
  3. 則 n = m+1 時, 應該就是 m(m+1)(2m+1)/6 + (m+1)^2 (也就是 2式 + (m+1)^2), 展開後得: (2m^3+9m^2+13m+6)/6
  4. 利用 n=m+1 的公式解得 (m+1)((m+1)+1)(2*(m+1)+1)/6 展開得: (m+1)(m+2)(2m+3)/6 = (2m^3+9m^2+13m+6)/6 和 3. 式結果相同
  5. 故得證.

不過用這種不是數學式的寫法看起來不是很舒服, 利用 google docs 的 “公式編輯器” 來寫應該更清楚, 如下:

證明平方和公式為:
1. 當 n = 1 時, 成立

2. 假設 n = m 時, 成立

3. 則當 n = m + 1 時, 4. 利用 n = m+1 的公式展開得:

5. 3和4式結果相同, 故得證.

相信這個證明很清楚地證明了平方和的公式及驗證, 也是數學歸納法的證明方式, 是不是讓久未碰高中數學的各位, 喚起了一些些記憶呢?