九個 1~9 的數，使其和為 45、積為 362880 的方案有幾種？如何證明？

01-07

從1~9的9個整數中任取9個數（可重複取），且它們的和為1+2+3+4...+9，它們的積為1x2x3x...x9。問這樣的9個數組合有幾種？

我的脖子

和為45，積為9！=2^7*3^4*5*7，每個數都是1到9

顯然，5和7各出現且只出現1次。

也就是說，想辦法在1,2,3,4,6,8,9里取7個數，和為33，積為2^7*3^4。

首先假設沒有6。

如果3^4是以9*9的方式出現，那麼剩下5個數的和為15，顯然不可能有3個1（2個一位數乘不出2的7次方），那麼一定是1個1，於是2,4,8當中取4個數和為14。

把這幾個偶數都除以2，那麼等價於在1,2,4中取4個數和為7，積為8，那麼裡面一定有且只有一個1，再在2,4當中取3個數，和為6，你說怎麼取？

然後再把2乘回去。

那麼結果就是，1+2+4+4+4+5+7+9+9=45，1*2*4*4*4*5*7*9*9=362880。

如果3^4是以3/3/9的方式出現，那麼剩下4個數和為18

同樣的方法除以2，等價於在1,2,4中取4個數，和為9，積為8。

顯然只有一個1，三個偶數和為8積為8怎麼看怎麼無解。

如果是以3/3/3/3的方式出現，那麼剩下3個數和為21。

壞了，因為奇偶性，顯然得有一個1，剩下兩個一位數加不出20。無解。

假設有一個6。

剩下6個數，乘積為2^6*3^3，和為27。

如果3^3是以3和9的方式出現的，那麼4個數和為15，積為64。

類似討論可得，只有一個解，這就是平凡的123456789啦。

如果3^3是3/3/3的方式出來的，那麼3個數和為18，積為64。

顯然都是偶數，同樣全都除以2，那麼3個數和為9，積為8，還是怎麼看怎麼無解。

假設有2個6。

剩下5個數，乘積為2^5*3^2，和為21。

假設那個3^2就是9。

剩下4個數，乘積為32，和為12。

那麼問題來了，它們當中有沒有1呢？

假設有1，那麼一定有2個1，但是留下和為10的兩個整數，乘積一般不太會是32。

如果沒有1，那就把它們四個偶數全都除以2，那麼四個數的乘積為2，和為6，似乎也並不能有解。

假設那個3^2是兩個3。

剩下3個數，乘積為32，和為15。

好了，一定有個1，剩下兩個2的冪加不出14。無解。

假設有3個6……還不死心嗎？

剩下4個數，乘積為48，和為15。

其中必有一個3。那麼剩下3個數，乘積為16，和為12。

顯然不可能有2個1，那麼一定都是偶數，同樣除以2，它們的積為2，和為6，無解。

假設有4個6！？

剩下3個數，積為8，和為9。哦，之前見過了，無解。

總結：除了你的123456789之外，只有一組解，124445799

後面的事情就是你要的排列組合了

我想到了一個只用進行一次分類討論的，基於 @薛定諤的喵改進的做法

首先如他提到，5和7必須各出現一次。其他的數，令2，3，4，6，8，9出現的次數分別為a,b,c,d,e,f, 則1出現的次數為g=7-(a+b+...+f)

我們有2^a 3^b ... 9^f=2*3*4*6*8*9=2^7 3^4

比較素因子得

a+2c+d+3e=7 (1)

b+d+2f=4 (2)

由於所有數的和為1+2+...+9=45，我們有g+2a+3b+4c+5+6d+7+8e+9f=45 (3)

注意原問題等價於求不定方程組(1)(2)(3)的所有非負整數解。

由(1)得

a=7-2c-d-3e &>= 0 (1")

由(2)得

b=4-d-2f &>= 0 (2")

代入(3)消去a,b變數，並化簡得

c+2d+4e+4f=11 (3")

注意到d+2f&<=4 (由2"可得)，代入(3") 可得一個輔助不等式 c+4e=11-2(d+2f)&>=3 (4)

注意c+2d被4除餘3，所以c是奇數

分類討論開始：

情況1： c=1

那麼由c+2d被4除餘3，d是奇數，所以d&>=1. 由(4), 4e&>=2, 所以e&>=1.

由(1"), 7-2c-d-3e=5-d-3e &>= 0 可以得到d,e必須恰好為1 （注意奇數d如果不是1的話至少為3，d+3e就太大了）

代入(3")得1+2+4+4f=11, 所以f=1. 代入(1")(2")得a=b=1, 所以得到的恰是原有的123456789.

情況2：c=3

由c+2d被4除餘3，d是偶數。由(1"), 7-2*3-d-3e&>=0, d+3e &<= 1, 必須有d=e=0

代入(3")得3+4f=11, f=2

代回(1")(2")得a=1, b=0

所以得到的9個數是一個2，三個4，兩個9，再加上必然有得一個5，一個7，最後還剩一個用1補全。數組為124445799

暴力一下

#include &

void f(int* a, int sum, int product, int n) { if (n == 9) { if (sum == 45 product == 362880) { for (int i = 0; i &< 9; i++) printf("%d ", a[i]); printf(" "); } } else for (a[n] = (n == 0) ? 1 : a[n - 1]; a[n] &<= 9; a[n]++) f(a, sum + a[n], product * a[n], n + 1); } int main() { int a[9]; f(a, 0, 1, 0); }

輸出

1 2 3 4 5 6 7 8 9 1 2 4 4 4 5 7 9 9

from itertools import combinations_with_replacement print(filter(lambda x: sum(x) == sum(range(1,10)) and reduce(lambda a, b: a * b, x) == reduce(lambda a, b: a * b, range(1,10)), combinations_with_replacement(range(1,10),9)))

上面是Python版

[(1, 2, 3, 4, 5, 6, 7, 8, 9), (1, 2, 4, 4, 4, 5, 7, 9, 9)]

下面是Scala版

val array = 1 to 9 print(array.flatMap(_ =&> array).combinations(9).filter{list =&> list.sum == array.sum list.reduceLeft(_ * _) == array.reduceLeft(_ *_)}.toList)

List(Vector(1, 2, 3, 4, 5, 6, 7, 8, 9), Vector(1, 2, 4, 4, 4, 5, 7, 9, 9))

9個數必須包含5和7,否則數的乘積不會被5和7整除。

9個數中除掉5和7，剩下的數和為33，,積可以看做 $2^{7} imes 3^{4}$ 。3和2互質，因此9個數的乘積必須能夠拆解出7個2和4個3。

設9個數中2,3,4,6,8,9分別有 $a,c,d,e,f,g$ 個。

$2=2 imes 1, 3=3 imes 1, 4=2 imes 2, 6=2 imes 3, 8=2 imes 2 imes 2 imes 2, 9=3 imes 3 imes 3$ ,

也就是說在在9個數的乘積中，2可以提供1個2,3可以提供1個3,4可以提供兩個2,6可以提供1個2和1個3...

所以，

$a+2d+e+3f=7$

$c+e+2g=4$

滿足條件的情況下，解出存在以下情況

------略顯複雜，如感不適，請跳至結論-------

1. $c=0,e=0,g=2$

2. $c=0,e=2,g=1$

3. $c=0,e=4,g=0$

4. $c=1,e=1,g=1$

5. $c=1,e=3,g=0$

6. $c=2,e=0,g=2$

7. $c=2,e=2,g=0$

8. $c=4,e=0,g=0$

9. $c=3,e=1,g=0$

---------------繼續暴力破解中(⊙v⊙)----------------

第9種情況中，能夠確定的就是573336，待確定的還有3個數。這3個數只能是2,4,8中任選3個。同時選的3個數必須能夠提供6個2（參看上述）。所以可選的是組合是573336842，573336444。和均不為45，排除。

第8種情況中，能夠確定的就是573333，待確定的還有3個數。因為最終和為45（奇數），這3個數必須包含1。剩下兩個數只能是2,4,8中選2個。同時選的2個數必須能夠提供7個2，不可能，排除。

第7種情況中，能夠確定的就是1573366，待確定的還有2個數。兩個數只能是2,4,8中選2個。同時選的2個數必須能夠提供5個2，這樣只能是157336684。和為43，排除。

第6種情況中，能夠確定的就是1573399，待確定的還有2個數。兩個數只能是2,4,8中選2個。同時選的2個數必須能夠提供7個2，不可能，排除。

第5種情況中，能夠確定的就是573666，待確定的還有3個數。兩個數只能是2,4,8中選3個。同時選的2個數必須能夠提供4個2，這樣只能是573366422。和為38，排除。
第4種情況中，能夠確定的就是157369，待確定的還有3個數。兩個數只能是2,4,8中選3個。同時選的3個數必須能夠提供6個2，這樣只能是(1)157369842，和為45，符合(2)157369444，和為43，排除。
第3種情況中，能夠確定的就是1576666，待確定的還有2個數。兩個數只能是2,4,8中選2個。同時選的2個數必須能夠提供3個2，這樣只能是157666624。和為43，排除。
第2種情況中，能夠確定的就是57669，待確定的還有4個數。兩個數只能是2,4,8中選4個。同時選的4個數必須能夠提供5個2，這樣只能是576694222。和為43，排除。
第1種情況中，能夠確定的就是15799，待確定的還有4個數。兩個數只能是2,4,8中選4個。同時選的4個數必須能夠提供7個2，這樣只能是157994442。和為45，符合。

可以發現，只有兩種組合123456789,124445799

(〝▼皿▼)

定義狀態：dp[i][j][k]為和為i，積為j，取了k個數的方案數

轉移方程：dp[i+t][j*t][k+1]+=dp[i][j][k]，1&<=t&<=9

dp[45][362880][9]即為所要求答案

複雜度好像有點高

-------------優化的分割線-----------

注意到362880中大多數為非法狀態

而362880

=1*2*3*4*5*6*7*8*9

=2^7*3^4*5*7

所以可以把狀態更改為:dp[i][j][k][l][m][n]

表示和為i，取了j個數，積中含k個2，l個3，m個5，n個7的方案數

於是dp[45][9][7][4][1][1]即為所要求答案

複雜度一下子就下來了呢(??ω??)?

我來提供一個@Milo Yip回答的非遞歸版本

#include & #include &

int main(int argc, char*argv[]) { int arr[9] = { 1,1,1,1,1,1,1,1,1 }; int sum = 0, product = 1; for (;arr[0] &<= 9;) { ++arr[8]; sum = 0, product = 1; for (int i = 8;i &>= 0;--i) { if (arr[i] &> 9 i &> 0) { ++arr[i - 1]; for (int j = i;j &< 9;++j) arr[j] = arr[i - 1]; } sum += arr[i]; product *= arr[i]; } if (sum == 45 product == 362880) { for (int i = 0;i &< 9;++i) fprintf(stdout, "%2d", arr[i]); fputc(" ", stdout); } } system("pause"); return 0; }

首先362880=2^7*3^4*5*7，因為2*5=10，2*7=14，已經不是個位數了，所以5和7取且只取一次。

所以問題就變成了求七個數字，積為10368，和為33。

不考慮和，只考慮積，可以求出10368里最多4個9，4個8，5個6，6個4，8個3，但是因為8&>7，所以3不考慮。

9^x=10368 x向下取整=4

8^x=10368 x向下取整=4

6^x=10368 x向下取整=5

4^x=10368 x向下取整=6

3^x=10368 x向下取整=8&>7

假設7個數裡面有4個9，10368?9?9?9?9=1.58，不是一個整數，所以7個數里不能取4個9；

假設3個9，2個9......

可以得出，只有2個9，2個8，1個8，4個6，3個6，2個6，1個6，3個4，2個4，1個4的時候，商是整數。

2個9的時候，商為128=2^7。滿足條件時，剩下的五個數的和為33-2*9=15。因為這五個數是7個2的乘積，所以它們的和為2*7=14。14與15相差1，任何數乘1都是它本身，所以7個2可以分為4個數，再取一個1。因為2^2=2*2，2^3不等於2*3，所以7個2隻能被分為2*2，2*2，2*2，2，也就是4，4，4，2。這就是一種情況，九個數分別取124445799。

1個9的時候，商為1152=2^7*3^2

33-9=24 2*7+3*2=20 20不等於24或25 所以這種情況是不可以的。

上面算出的情況都算一遍後，會發現只有取2個9的時候是符合條件的。

那麼當沒有9，沒有8，沒有6，沒有4，沒有3，沒有2的時候呢？

9=3*3

8=2*2*2

6=2*3

4=2*2

3=9^0.5

2=4^0.5=8^1/3

所以當沒有9的時候，必有2個3，沒有8的時候，必有3個2，沒有6的時候，必有1個2和1個3，沒有4的時候，必有2個2，沒有9的時候，必有1個9，沒有2的時候，必有1個4或1個8。

同理可證得，這些情況都是不符合的。

所以就只有兩種情況，一取123456789，二取124445799。

我用第一種方法解得之後，掃了一眼其他答案，受啟發用方程式來解。

設有x1個1，x2個2...x9個9。

把X5，X7=0

從七個數的數量和為7得x1+x2+x3+x4+x6+x8+x9=7 ①

從七個數的和為33得

1+2x2+3x3+4x4+6x6+8x8+9x9=33 ②

從10368=2^7*3^4，並且4=2*2，6=2*3，8=2*2*2，9=3*3得

x2+2x4+x6+3x8=7 ③

x3+x6+2x9=4 ④

①②③④式解線性方程組，再用0&<=x&<=7列不等式縮小x的範圍，可以得到x6是0-4，x8是0-2，x9是0-2。然後窮舉得出結論。

似乎各個方法都是要窮舉，有沒有哪個方法可以直接算出呢？

把362880拆一下就是2^7*3^4*5*7。

5跟7隻能出現一次這個我瞟了一眼好像各位都提到了。

有幾個1無所謂，反正不算數。

讓2、3、4、6、8、9出現的次數等於x_1 ... x_6。

可以列出兩個方程：

x_1 + 2*x_3 + x_4 + 3*x_5 = 7 (1)

x_2 + x_4 + 2*x_6 = 4 (2)

分別代表質因子有7個2和4個3。

然後就是九個數相加等於45。其中1的個數等於7 - (x_1 + ... + x_6)。那麼可以列這麼個方程：

7 - (x_1 + ... + x_6) + 2*x_1 + 3*x_2 + 4*x_3 + 5 + 6*x_4 + 7 + 8*x_5 + 9*x_6 = 45

太亂了，整理一下：

x_1 + 2*x_2 + 3*x_3 + 5*x_4 + 7*x_5 + 8*x_6 = 26 (3)

就是這樣了。(1)(2)(3)是個很好解的線性方程組。