一个九位数由1-9数字组成并前N 位被N整除

皓月当空

请将123456789九个数字以特定的顺序排列，组成一个9位数ABCDEFGHI（每个数字只能使用一次），使得：
1.第一位数字组成的整数可以被1整除
2.第一、二位数字组成的整数可以被2整除
3.第一、二、三位数字组成的整数可以被3整除
4.第一、二、三、四位数字组成的整数可以被4整除
......
9.第一、二、三...九位数字组成的整数可以被9整除


分析：
通常想法是遍历9！=362280种排列。
其实第5位E一定是5，这样可缩减到8!=40320种排列
进一步分析，偶数位一定是偶数（BDFH={2，4，6，8}），奇数位一定是奇数（ACGI={1，3，7，9}），因而只需分析P(4,4)*P(4,4)=576种排列。
继续分析，4能整除 10*C+D，故D=2  或 6, 加之8能整除 10*G+H，故D,H={2，6}，所以B，F={4，8}，故需分析P(4,4)*P(2,2)*P(2,2)=48种排列
接着分析，3 能整除 100* D+ 10 * 5+ F，所以DEF={258 ，654}，ABC，GHI能被3整除
如果DEF=258，则，ABC={147，741}，GHI={369，963}，但1472589，7412589均不能被7整除，不符合条件，故DEF=654，
B=8，H=2.此时只有P(4,4)=24种排列
又7能整除A8C654G，故7整除（A+4C+G）,而G={3，7}，如果G=3，ABC为{189，789，981，987}均不满足条件，故G=7，此时ABC={183，189，381，981}中只有381符合条件，故ABCDEFGHI=381654729

sch1122

总结得不错，谢谢共享。

jymm222

我反应不过来 ，"3 能整除 100* D+ 10 * 5+ F"，怎么看出来的 ，哪位给讲解讲解

jymm222

还有一点反应不过来，“而G={3，7}”，怎么看出来的 ，哪位给讲解讲解

jymm222

原帖由 jymm222 于 2008-12-16 11:22 发表
我反应不过来 ，"3 能整除 100* D+ 10 * 5+ F"，怎么看出来的 ，哪位给讲解讲解

我终于想到了，原来是因为ABC能被3整除，所以要使ABCDEF能被3整除，DEF能被3整除就可以了。

jymm222

原帖由 jymm222 于 2008-12-16 12:58 发表
还有一点反应不过来，“而G={3，7}”，怎么看出来的 ，哪位给讲解讲解

我终于懂了,原来H=2,要使GH能被8整除,得G={3，7}，我真慢呀