Quod Erat Demonstrandum

2010/12/14

數算

Filed under: Additional / Applied Mathematics,NSS — johnmayhk @ 6:21 下午

現在,高中學生都要學習「排列與組合」(permutation and combination)這個課題。聊舉兩個教科書的例:

e.g. 1

There are 12 Cantonese songs, 8 Mandarin songs and 5 English songs stored in the MP3 player of Katherine. If 6 songs are selected to play, how many playing sequences are there if at least 1 English song is selected.

以下是錯誤想法:

先在 5 首英文歌選 1 首(C^5_1 種方式),放在 play list 6 個位置的某個(C^6_1 種方式)。

再在餘下的 24 首歌,選 5 首放在 play list 的其餘位置(P^{24}_5 種方式)。

即共有 C^5_1 \times C^6_1 \times P^{24}_5 = 2907273600 種歌曲播放次序。

錯!

上述想法存在重覆算數:

::::::::::

先在 5 首英文歌選 1 首,比如 E_1

它可放在 play list 6 個位置的其中一個,比如第 1 個,即 E_1 放在第 1 個位置。

再在餘下的 24 首歌,選 5 首放在 play list 的其餘位置,

比如選上 E_2 放在第 2 個位置。

那麼,E_1E_2 分別佔據第 1 及第 2 個位置。

::::::::::

但我們也可能出現以下情況,

::::::::::

先在 5 首英文歌選 1 首,比如 E_2

它可放在 play list 6 個位置的其中一個,比如第 2 個,即 E_2 放在第 2 個位置。

再在餘下的 24 首歌,選 5 首放在 play list 的其餘位置,

比如選上 E_1 放在第 1 個位置。

那麼,E_1E_2 分別佔據第 1 及第 2 個位置。

::::::::::

看,這和剛才的情況一樣,但它卻被數算了兩次。

另一種錯誤想法是:

先在 5 首英文歌選 1 首(C^5_1 種方式),再在其他 24 首歌選 5 首(C^{24}_5 種方式),現把選出的 6 首歌排隊(6! 種方式),所以答案是

C^5_1 \times C^{24}_5 \times 6! 種播放次序。

錯!

同學,上述做法有何問題?試說明之。

並請不要只重申正確做法:P^{25}_6 - P^{20}_6 了事。

e.g. 2

There are 12 different plants in balcony, and 5 of them are cactuses. The plants are now arranged in a row such that any two cactuses cannot be placed next to each other, how many permutations are there?

以下是錯誤想法:

當 5 株仙人掌排在一起成為「一株」,情況好像是 12 - 4 = 8 株植物排隊,共 8! 種排法。

又 5 株排在一起的仙人掌,本身又可 5! 種排法,故 5 株仙人掌排在一起共 8!5! 種。

所以 5 株仙人掌不排在一起的排法,共 12! - 8!5! 種。

錯!

致命傷是:"any two cactuses cannot be placed next to each other" 並非「5 株仙人掌排在一起」的否定命題(negation)。

「5 株仙人掌不排在一起」可以有以下情況,比如「4 株仙人掌排在一起,餘下的 1 株被其他植物分隔開」,又或「3 株仙人掌排在一起,餘下的 2 株被其他植物分隔開」云云。但題目說:"any two cactuses cannot be placed next to each other",是「任何兩株仙人掌,都給其他植物分隔開」的意思。

建議答案:

先放其他 7 株植物(7! 種安排方法),植物兩旁留個空位(共 8 個空位),以放 5 株仙人掌(共 P^8_5 種排列方法),故正確答案是 7!P^8_5

5 則迴響 »

  1. e.g.2 的解法十分高明。
    這題問題應來自新里程。

    你認為新里程中五上,第五章,複習題5 #40c是不是超出hkdse的範圍?

    迴響 由 走得慢 — 2010/12/16 @ 7:23 下午 | 回覆

    • 你指以下一題吧:

      "There are 9 different books, how many ways to group the books into 3 piles such that there are 3 books in each pile?"

      以前教 applied math,我都會談這類問題(反而 blog 文中的 e.g.2 是 discrete math 的基本題目,除了當「趣味」題,沒有和學生正式談。)。

      這似乎也屬於在指引中:"problems on combination of distinct objects without repetition" 一類。

      且教科書是「已被批准」的。

      不過,學生「受得住」嗎?只好瞧著看了。

      迴響 由 johnmayhk — 2010/12/17 @ 9:30 上午 | 回覆

  2. 哇,甘難ge…

    我今年中四

    讀M1 的 Binomial expansion,只教了一點點 combination…

    迴響 由 andy wong — 2010/12/18 @ 11:24 下午 | 回覆

  3. 新高中數學必修課程之中,這課似乎最難掌握,老師同意嗎?

    迴響 由 Herrmann — 2010/12/24 @ 3:19 下午 | 回覆


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 位部落客按了讚: