Quod Erat Demonstrandum

2009/08/31

拼出 $100

老題:利用面值 $10,$20 及 $50 紙幣若干張,要拼出 $100,問有多少組合方式?

可以拿 2 張 $50 紙幣,這是一種組合;
可以拿 3 張 $10,1 張 $20 及 1 張 $50,這是另一種組合;
……

那麼,共有多少種可能的組合?

這篇為承接昨天的發帖而寫的例。是舊技巧,高手見諒。

對 $10 紙幣,我們考慮冪級數

1 + x^{10} + x^{20} + x^{30} + \dots

我們觀察 x 的指數,便可對應 $10 紙幣的數目,即

x^{20} 代表 2 張 $10 紙幣;
x^{30} 代表 3 張 $10 紙幣;
……

類似地,

對 $20 及 $50 紙幣,我們分別考慮冪級數

1 + x^{20} + x^{40} + x^{60} + \dots
1 + x^{50} + x^{100} + x^{150} + \dots

把上面提及的三個級數相乘,得

(1 + x^{10} + x^{20} + x^{30} + \dots)(1 + x^{20} + x^{40} + \dots)(1 + x^{50} + x^{100}\dots) – – – – – – (*)

同學,想像(是,想像而已)把上式拆開(或曰「爆開」expand),每項皆由三個括弧,分別抽出一項相乘而得。比如,

第一個括弧抽出 x^{30}
第二個括弧抽出 x^{20}
第三個括弧抽出 x^{50}

相乘之,得

x^{30} \times x^{20} \times x^{50} = x^{30 + 20 + 50} = x^{100} – – – – – – (**)

看看當中的意義:

第一個括弧抽出 x^{30},相當於拿出 3 張 $10 紙幣;
第二個括弧抽出 x^{20},相當於拿出 1 張 $20 紙幣;
第三個括弧抽出 x^{50},相當於拿出 1 張 $50 紙幣;

總面值是 3*$10 + 1*$20 + 1*$50 = $100;而 100,正是 (**) 中 x 的指數。

這樣,(**) 代表著一種拼出 $100 的組合方式(即 3 張 $10,1 張 $20 及 1 張 $50)。

而 (**) 不過是 (*) 拆開後的某一項。

即 (*) 拆出一項 x^{100},代表著一種拼出 $100 的組合方式。

那麼,若 (*) 可以拆出 nx^{100},即代表著 n 種拼出 $100 的組合方式。

但若 (*) 可以拆出 nx^{100},把它們加起來,得 nx^{100}

也就是說,(*) 拆開後,x^{100} 的係數就是 n,亦即是說

「有多少種拼出 $100 的組合方式,就等於 x^{100} 的係數」。

但如何求 (*) 中 x^{100} 的係數?昨天也談過。

(1 + x^{10} + x^{20} + x^{30} + \dots)(1 + x^{20} + x^{40} + \dots)(1 + x^{50} + x^{100}\dots) – – – – – – (*)

可變為

\frac{1}{(1 - x^{10})(1 - x^{20})(1 - x^{50})}

之後就是拆部份分式,但直接考慮上式的部份分式,太艱鉅,我們考慮簡單一點的情況:

\frac{1}{(1 - y)(1 - y^2)}

不難得到

\frac{1}{(1 - y)(1 - y^2)} \equiv \frac{1}{4(1 - y)} + \frac{1}{2(1 - y)^2} + \frac{1}{4(1 + y)}

運用 sum of G.S.,得知

\frac{1}{4(1 - y)} \equiv \frac{1}{4}(1 + y + y^2 + y^3 + \dots)
\frac{1}{2(1 - y)^2} \equiv \frac{1}{2}(1 + 2y + 3y^2 + 4y^3 + \dots)
\frac{1}{4(1 + y)} \equiv \frac{1}{4}(1 - y + y^2 - y^3 + \dots)

於是

\frac{1}{(1 - y)(1 - y^2)} \equiv 1 + y + 2y^2 + 2y^3 + 3y^4 + 3y^5 + \dots

那麼,

\frac{1}{(1 - x^{10})(1 - x^{20})} \equiv 1 + x^{10} + 2x^{20} + 2x^{30} + 3x^{40} + 3x^{50} + \dots

故此,(*) 變成

\frac{1}{(1 - x^{10})(1 - x^{20})(1 - x^{50})}
\equiv (1 + x^{10} + 2x^{20} + 2x^{30} + 3x^{40} + 3x^{50} + \dots)(1 + x^{50} + x^{100} + \dots)

不難尋求上式中,x^{100} 的係數,即

1 \times 1 + 3 \times 1 + 6 \times 1 = 10

即是說有 10 種拼出 $100 的組合方式。

驗證一下:

$10

$20

$50

0

0

2

1

2

1

3

1

1

5

0

1

0

5

0

2

4

0

4

3

0

6

2

0

8

1

0

10

0

0

數一數,共 10 個組合方式。

同學你或在取笑這個方法:「就咁數」仲快。不錯,這個特例是,但上述的方法是值得留意的:因為它是有系統的方法。

3 則迴響 »

  1. 當我們使用sum of G.S的sum to infinity: 1 + x + x^2 + … = 1/(1 – x)
    我們要確保 |x|<1吧,但是這個條件在這例中有甚麼含意/代表甚麼?

    迴響 由 Justin — 2009/08/31 @ 9:09 下午 | 回覆

    • 正如昨天的 blog 文提及,這方法的重點在於「形式」(比較係數),而不是分析上的問題(即 x 是什麼確保級數收斂),x 這個東西不過是一個「形式」工具,它的數值如何,不太重要。所以,不妨假設:在整個討論中 x 的數值在一個「確保文中提及的所有級數都是(絕對)收斂」的範圍內。

      迴響 由 johnmayhk — 2009/08/31 @ 9:24 下午 | 回覆

  2. 這些數學題, 很適合小朋友去玩

    《我通我識》節目主持
    http://lslu.wordpress.com/

    迴響 由 lslu — 2009/09/03 @ 10:11 上午 | 回覆


RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在WordPress.com寫網誌.

%d 位部落客按了讚: