2013年7月27日 星期六

訓練數學感 9 ─ Total 22

http://4rdp.blogspot.com/2013/07/total-22.html


X + Y + Z + ... = 22,   0 < X,Y,Z, ... 10

難度 ✩✩✩✩

這是我的小朋友不服氣我數學厲害,特別出題考我的暑假作業,並打算考倒全校數學高手,這題我花了很多天時間進行基礎研究,並查閱 OEIS,因粗心計算錯誤以為自己找到新數列,結果白忙一場,如果自認為是數學高手,就接受挑戰吧:

任意正整數排列組合,相加等於 22,並且單一整數最大值為 10,如果 10 + 10 + 2 是一種組合,那麼 10 + 2 + 10 是重覆的組合,請問有多少種排列組合不重覆?如果可以重覆有多少種?

這一題真的是很難,組合不重覆或許你可以慢慢排慢慢算,反正答案在一千以內,但是計算排列可以重覆,沒有利用數列,應該會算到天荒地老!

2013/8: 補充提示
2016/1: 試算表解法公告,含 "不重複"、"重複" 及董芳成老師解法

12 則留言:

  1. 有一條香腸,有22節,中間有21個連接點,
    每個連接點,可切,可不切,
    全部組合:有2^21次方,
    把題目轉換成21位數的2進位數字,或是21位數字串
    =========================
    題目:最大塊香腸~限制長度10節香腸,可以組合重覆時,

    先~~負面思考:
    (NG-case1):先切一塊11節香腸時,剩下11節有2^10的組合
    (NG-case2):先切一塊12節香腸時,剩下10節有2^9的組合
    (NG-case3):先切一塊13節香腸時,剩下9節有2^8的組合
    .....
    .....
    (NG-case12):先切一塊22節香腸時,剩下0節有2^0的組合
    所以NG組合共有2^10+2^9+2^8+2^7+...+2^0=(2^11)-1

    再回到正面思考:
    則(OK組合)=(全部組合:2^21)-(NG組合:2^11-1)
    ==========================================
    但是組合不重覆的狀況,就還沒想到怎麼計算了

    回覆刪除
    回覆
    1. 自己吐槽自己一下
      (NG-case09):先切一塊19節香腸時,剩下3節,有2^2=4的組合
      (NG-case10):先切一塊20節香腸時,剩下2節,有2^1=2的組合
      (NG-case11):先切一塊21節香腸時,剩下1節,有2^0=1的組合
      (NG-case12):先切一塊22節箱腸時,剩下0節,有2^0=1的組合
      所以(NG組合)=(2^10)+(2^9)+(2^8)+...+(2^0)+(2^0)=(2^11)-1+1=(2^11)
      (OK組合)=(全部組合:2^21)-(NG組合:2^11)
      .........
      嗯,還是有怪怪的地方
      .....抱歉,我再有空再想想

      刪除
    2. 您好,

      能用切香腸來比喻這題 總合二十二 數學題,真是傳神貼切,怪怪的地方在最長為十段連結,而非十一段連結。

      我是利用試算表幫忙加總計算,沒關係有的是時間慢慢思考,祝你成功求解。

      刪除
    3. 再補充線索,不可重複排列可參考 OEIS A008284,可重複排列的 A048004。

      刪除
  2. 這個問題有人已經給出通解,見
    http://blog.chinaunix.net/uid-26548237-id-3503956.html
    我放在compileonline上,結果顯示為807

    回覆刪除
  3. Linke 謝謝你,807 是"不重複"的正解,沒想到有網友早就解決這個問題。
    這題的"不重複"通解與數列 A008284 相關,詳見 http://oeis.org/A008284
    很佩服你的耐性,逐一克服各式難題,有這樣個性的人,會有成功的一天。
    喜歡與你網路交誼,日後有機會去香港或你來台北,和你相聚認識認識。

    關於重複組合的解答,大家繼續努力。等有人解答之後,再公佈我的試算表解答。

    回覆刪除
    回覆
    1. 哈哈,Bridan您過譽啦~
      台北我讀書的時候去過一次,那裏濃厚的學習氣氛我十分喜歡.
      如果能夠再去的話一定找你~
      你要是來香港我也應該好好招待你呀~
      這都要歸功於你的博文很有趣,我把其中的幾篇還講給過小朋友們聼呢~
      希望你的博客越寫越好~

      刪除
    2. Linke 隨時歡迎您來,有你們這些讀者的加油,我會更加努力。

      目前初步計畫每週兩文,其中一篇有關訓練數學感,先寫到明年底湊一百篇。

      刪除
  4. 對於可重覆的方法數,我的想法是:
    最左邊的數可能是1,也可能是2,…,也可能是10。
    所以若令加起來的數是k時的分法共有N(k)種方法 (可重覆,即10, 10, 2 與 10, 2, 10看作不同分法)
    則n(k)=n(k-1)+ n(k-2)+ n(k-3)+ n(k-4)+ n(k-5)+ n(k-6)+ n(k-7)+ n(k-8)+ n(k-9)+ n(k-10)
    故所求=n(22)
    =n(21)+ n(20)+ n(19)+ n(18)+ n(17)+ n(16)+ n(15)+ n(14)+ n(13)+ n(12)
    =2(n(20)+ n(19)+ n(18)+ n(17)+ n(16)+ n(15)+ n(14)+ n(13)+ n(12))+n(11)
    =4(n(19)+ n(18)+ n(17)+ n(16)+ n(15)+ n(14)+ n(13)+ n(12))+3n(11)+2n(10)
    =8(n(18)+ n(17)+ n(16)+ n(15)+ n(14)+ n(13)+ n(12))+7n(11)+6n(10)+4n(9)
    =16(n(17)+ n(16)+ n(15)+ n(14)+ n(13)+ n(12))+15n(11)+14n(10)+12n(9)+8n(8)
    =32(n(16)+ n(15)+ n(14)+ n(13)+ n(12))+31n(11)+30n(10)+28n(9)+24n(8)+16n(7)
    =64(n(15)+ n(14)+ n(13)+ n(12))+63n(11)+62n(10)+60n(9)+64n(8)+48n(7)+32n(6)
    =128(n(14)+ n(13)+ n(12))+127n(11)+126n(10)+124n(9)+120n(8)+112n(7)+96n(6)+64n(5)
    =256(n(13)+ n(12))+255n(11)+254n(10)+252n(9)+248n(8)+240n(7)+224n(6)+192n(5)+128n(4)
    =512n(12)+511n(11)+ 510n(10)+508n(9)+ 504n(8)+ 496n(7)+ 480n(6)+ 448n(5)+ 384n(4)+256n(3)
    =1023n(11)+ 1022n(10)+ 1020n(9)+ 1016n(8)+ 1008n(7)+ 992n(6)+960n(5)+ 896n(4)+ 768n(3)+ 512n(2)
    = 2045n(10)+ 2043n(9)+ 2039n(8)+ 2031n(7)+ 2015n(6)+1983n(5)+ 1919n(4)+ 1791n(3)+ 1535n(2)+1023n(1)
    =4088n(9)+ 4084n(8)+ 4076n(7)+ 4060n(6)+4028n(5)+ 3964n(4)+ 3836n(3)+ 3580n(2)+3068n(1)
    =8172n(8)+ 8164n(7)+ 8148n(6)+8116n(5)+ 8052n(4)+ 7924n(3)+ 7668n(2)+7156n(1)
    =16336n(7)+ 16320n(6)+16288n(5)+ 16224n(4)+ 16096n(3)+ 15840n(2)+15328n(1)
    =32656n(6)+32624n(5)+ 32560n(4)+ 32432n(3)+ 32176n(2)+31664n(1)
    =65280n(5)+ 65216n(4)+ 65088n(3)+ 64832n(2)+64320n(1)
    =130496n(4)+ 130368n(3)+130112n(2)+129600n(1)
    =260864n(3)+260608n(2)+260096n(1)
    =521472n(2)+520960n(1)
    =1042432n(1)
    =1042432

    所以共有1042432 方法。

    回覆刪除
    回覆
    1. 這題放了近兩年半,終於有人提出"重複"的解法,不過正解要計算到 n(0),2083841
      雖然少算一個步驟,方老師還是很厲害,從看到題目到寫出解法不到一天的時間,我還沒有這樣的功力

      刪除
    2. 更正一下 (沒錯!要算到n(0)):

      X + Y + Z + ... = 22, 0 < X,Y,Z, ... ≦ 10
      -------
      對於可重覆的方法數,我的想法是:
      最左邊的數可能是1,也可能是2,…,也可能是10。
      所以若令加起來的數是k時的分法共有n(k)種方法 (可重覆,即10, 10, 2 與 10, 2, 10看作不同分法)
      則n(k)=n(k-1)+ n(k-2)+ n(k-3)+ n(k-4)+ n(k-5)+ n(k-6)+ n(k-7)+ n(k-8)+ n(k-9)+ n(k-10)

      [ 但n(0)=1 例如 n(2) 的最左邊的數可能是1或2 所以 n(2)=n(1)+n(0)=1+1=2
      也可以直接 n(2)=n(1)+n(0) =n(0)+n(0)= =2n(0)=2 ]

      故所求=n(22)
      =n(21)+ n(20)+ n(19)+ n(18)+ n(17)+ n(16)+ n(15)+ n(14)+ n(13)+ n(12)
      =2(n(20)+ n(19)+ n(18)+ n(17)+ n(16)+ n(15)+ n(14)+ n(13)+ n(12))+n(11)
      =4(n(19)+ n(18)+ n(17)+ n(16)+ n(15)+ n(14)+ n(13)+ n(12))+3n(11)+2n(10)
      =8(n(18)+ n(17)+ n(16)+ n(15)+ n(14)+ n(13)+ n(12))+7n(11)+6n(10)+4n(9)
      =16(n(17)+ n(16)+ n(15)+ n(14)+ n(13)+ n(12))+15n(11)+14n(10)+12n(9)+8n(8)
      =32(n(16)+ n(15)+ n(14)+ n(13)+ n(12))+31n(11)+30n(10)+28n(9)+24n(8)+16n(7)
      =64(n(15)+ n(14)+ n(13)+ n(12))+63n(11)+62n(10)+60n(9)+56n(8)+48n(7)+32n(6)
      =128(n(14)+ n(13)+ n(12))+127n(11)+126n(10)+124n(9)+120n(8)+112n(7)+96n(6)+64n(5)
      =256(n(13)+ n(12))+255n(11)+254n(10)+252n(9)+248n(8)+240n(7)+224n(6)+192n(5)+128n(4)
      =512n(12)+511n(11)+ 510n(10)+508n(9)+ 504n(8)+ 496n(7)+ 480n(6)+ 448n(5)+ 384n(4)+256n(3)
      =1023n(11)+ 1022n(10)+ 1020n(9)+ 1016n(8)+ 1008n(7)+ 992n(6)+960n(5)+ 896n(4)+ 768n(3)+ 512n(2)
      = 2045n(10)+ 2043n(9)+ 2039n(8)+ 2031n(7)+ 2015n(6)+1983n(5)+ 1919n(4)+ 1791n(3)+ 1535n(2)+1023n(1)
      =4088n(9)+ 4084n(8)+ 4076n(7)+ 4060n(6)+4028n(5)+ 3964n(4)+ 3836n(3)+ 3580n(2)+3068n(1)+2045n(0)
      =8172n(8)+ 8164n(7)+ 8148n(6)+8116n(5)+ 8052n(4)+ 7924n(3)+ 7668n(2)+7156n(1)+6133n(0)
      =16336n(7)+ 16320n(6)+16288n(5)+ 16224n(4)+ 16096n(3)+ 15840n(2)+15328n(1) +14305n(0)
      =32656n(6)+32624n(5)+ 32560n(4)+ 32432n(3)+ 32176n(2)+31664n(1) +30641n(0)
      =65280n(5)+ 65216n(4)+ 65088n(3)+ 64832n(2)+64320n(1) +63297n(0)
      =130496n(4)+ 130368n(3)+130112n(2)+129600n(1) +128577n(0)
      =260864n(3)+260608n(2)+260096n(1) +259073n(0)
      =521472n(2)+520960n(1) +519937n(0)
      =1042432n(1) +1041409n(0)=2083841

      (謝謝Bridan的指正!)

      刪除
    3. 謝謝方老師予以指導,說真的,我沒想到用這種解法,只會苦力的用試算表總計,不然當時就可以很快破解小朋友的考題。

      刪除