大卡車

一題填數字的問題(排列組合)

Recommended Posts

將1-10十個整數填入下列空格

┌-┬-┬-┬-┬-┐

├-┼-┼-┼-┼-┤

└-┴-┴-┴-┴-┘

並規定每一行下面的數字不能比上面大

   每一列左邊的數字不能比右邊大

求有幾種填數字的方法?

PS:我是用土法煉鋼解出來 但我想知道是否可以用遞迴式表示到第N列

還有問到老師說可以用走4X4格子的加法原理方式但不能過對角線 但我不知道原因 可否請大家幫忙解答 謝謝!!!

Share this post


Link to post
Share on other sites

先回答老師對您的解說

數學上 常常在兩個問題(或兩個觀念)之間 找尋一一對應的關係 

使得 想要解決其中一個問題時 等於是解決另一個與之對應的問題 

排列組合在這方面的表現更是明顯

以這題來說 題目有兩個規定 我們先看第一個:每一列左邊的數字不能比右邊大

在只考慮這一條規定之下 我們可以發現填格子的方法恰與一個由1和2所構成的數列(長度為10)產生一一對應

對應的方法是 將 1 ~ 10 在格子的列數 依序記錄下來 (底下那列記為1 上方列記為2)

譬如說 567810

    12349 這樣的的填法 對應到 1111222212

因為 1~4 在第一列 5~8在第二列 所以數列的前四項是1 第5到第8項是2

9在第一列 所以數列的第9項是1 10在第二列 所以數列的第10項是2

反過來 如果任意給一個數列(注意:必須五個1和五個2) 我們也可以找到一個對應的填格子的方法

譬如說 1211211222 則對應到 258910

                 13467

所以 光考量每一列左邊的數字不能比右邊大時 

我們可以將填格子的問題 看成是 由五個1和五個2組成的數列的問題

接下來 要考慮題目的另一規定:每一行下面的數字不能比上面大

如果數列的開頭是 11222 則對應到 345

                 12  則 5 的下方必然只能填 6, 7, 8, 9, 10 但都比5大

違背了題目的規定  所以 一個數列對應到的填格子方法要滿足題目規定的話

必須具備以下的性質:

從左數到右 不論數到什麼地方 1的總數必須大於等於2的總數

像是剛才的 11222 數到第五項的時候 1的總數是2 但2的總數是3 這是造成違規的主因

總結:填格子問題可以看成是由五個1和五個2組成的數列的問題 而且該數列必須滿足

從左數到右 不論數到什麼地方 1的總數必須大於等於2的總數

而上述的數列問題 可以用走4X4格子 配合上角落註記法 來計數

數列如果出現1 相當於往右邊走一格(從4X4格子的左下角出發) 出現2 則往上走一格

五個1反應了往右共走五格 五個2反應了往上共走五格

但 考慮到 1的總數必須大於等於2的總數 所以 走格子的時候不可以走到左上方的部分

也就是老師說的 不能(超)過對角線

今天時間不夠 有些地方沒有解說的很詳細 如果有疑問 可先提出 阿牛下次再補充說明

Edited by 曾阿牛

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.