一題環球城市競賽證明題

請問天助, [11]~[19] 如何被 [9]! 整除?

2010-02-22 18:00:00 補充：
( 出處: http://www.math.toronto.edu/oz/turgor/index.php ,
Solutions to Seniors A-Level Paper Fall 2009 by Jonathan Zung)

Define f(n) = 111....1 (n個1) and f(0) = 1 so that [0]! = 1.
Define
[n,k]=[n]!/[k]![n-k]! for n>=k>=0.

We use induction on n to prove that [n,k] is always a positive integer
for all n>=1.

For n = 0
[0,0]=[0]!/[0]![0]!= 1

Suppose the result holds for some n >0. Consider the next case.
[n + 1,k ] = [n + 1]!/[k]![n + 1 - k]!
= [n]! f(n + 1) / [k]![n + 1 - k]!
= [n]! f(n + 1 - k) * 10^k /[k]![n - k]!f(n + 1 - k)
+ [n]! f(k)/[k-1]![n + 1- k]!
=10^k*[n,k]+ [ n,k-1]

Since both terms in the last line are positive integers, the induction argument is complete. In particular, for any positive integers m and n, [m + n, m ]=[m + n]!/[m]![n]! is a positive integer, so that [m+n]! is divisible by [m]![n]!. (Jonathan Zung)

2010-02-25 15:22:58 補充：
[n + 1,k ] = [n + 1]!/[k]![n + 1 - k]!
= [n]! f(n + 1) / [k]![n + 1 - k]!
= [n]! f(n + 1 - k) * 10^k /[k]![n - k]!f(n + 1 - k)
+ [n]! f(k)/[k]![n + 1- k]!
=10^k*[n,k]+ [n]! /[k-1]![n + 1- k]!
=10^k*[n,k]+ [ n,k-1]

[n]! f(n + 1) / [k]![n + 1 - k]!
= [n]! f(n + 1 - k) * 10^k /[k]![n - k]!f(n + 1 - k)
+ [n]! f(k)/[k-1]![n + 1- k]!
=10^k*[n,k]+ [ n,k-1]
這部份好像有幾個問題
1.[k-1]!是哪裡來的?不是應該是[k]!?
2.[n]! f(k)/[k-1]![n + 1- k]!應該=f(k)*[n,k-1]!才對吧

[18]!除以[9]!=1000000001=d,餘0
[16]!除以[8]!餘0
[14]!除以[7]!餘0商10000001=a
[12]!除以[6]!=1000001=b餘0
[15]!除以[5]!=10000100001=c餘0
a*b為[4]!=1111倍數
c為[3]!=111倍數
d為[2]!=11倍數

2010-02-21 13:15:03 補充：
更正:
(18個1)除以(9個1)=1000000001=d,餘0
(16個1)除以(8個1)餘0
(14個1)除以(7個1)餘0商10000001=a
(12個1)除以(6個1)=1000001=b餘0
(15個1)除以(5個1)=10000100001=c餘0
a*b為(4個1)=11=11*101倍數
c為(3個1)=111倍數
d為把(2個1)=11倍數