|
問題2682・・・ひよこさんのサイト http://myhome.cururu.jp/gersdorffite/blog/article/71002133994 より Orz〜
（１） P_(100) を求めよ。
（２） ω(P_n)≦3 を満たすnは無限に存在するか。
* ω(n)はnのもつ異なる素因数の個数です。
たとえば、 ω(8)=1、 ω(30)=3、 ω(12)=2 となります。
例として、P_6を求めてみます。
a+b+c=6 を満たす正整数a,b,cの組は以下のように10通りあります。
(a, b, c) = (1, 1, 4), (1, 2, 3), (1, 3, 2), (1, 4, 1), (2, 1, 3),
(2, 2, 2), (2, 3, 1), (3, 1, 2), (3, 2, 1), (4, 1, 1)
この10個を要素にもつのが集合A_6であるわけです。
なので、
P_6 = (1・1・4)＋（1・2・3）＋(1・3・2)＋（1・4・1）＋（2・1・3）
＋(2・2・2)＋（2・3・1）＋(3・1・2)＋（3・2・1）＋（4・1・1） = 56
（おまけ問題）
x = (x_1, x_2, x_3, ・・・ , x_99, x_100) とする。
x_1＋x_2＋x_3＋・・・＋x_100 = 10000 を満たす、
正整数x_1, x_2, x_3, ・・・ , x_99, x_100 の組全体の集合をHとするとき、
Σ_[x∈H] (x_1)(x_2)(x_3)・・・(x_100） を求めよ。
そこまで大きくない値になるはず。 500桁以下です。
解答
上記サイトより Orz〜
・否定する者さんのもの Orz〜
2項係数(n, r)に対して、次の2つの等式が成立することに注意する。
(r+1)・(n+1, r+1) = (n+1)・(n, r)
Σ_[k=r to n] (k, r) = (n+1, r+1)
（１）の解答
x=(a. b)とおき、
B_n = ｛x∈N＾2 ； a+b = n｝として、
Q_n=Σ_[x∈B_n] ab を先に求めることにする。
これは次のように計算できる。
Q_n = Σ_[k=1 to n-1] k・(n-k) = Σ_[k=1 to n-1] (k, 1)・((n+1)-(k+1))
= (n+1)Σ_[k=1 to n-1] (k, 1)‐Σ_[k=1 to n-1] (k+1)・(k, 1)
= (n+1)・(n, 2)‐2Σ_[k=1 to n-1] (k+1, 2)
= 3(n+1, 3)‐2Σ_[t=2 to n] (t, 2)
= 3(n+1, 3)‐2(n+1, 3)
= (n+1, 3)
P_n を求める。
Q_nを使いたいので以下のように考える。
P_n は a+b+c=n を満たす(a, b, c)に対して、Σabcの値を意味するのである。
a+b+c=nについて、cの動く範囲を考えると、明らかに 1≦c≦n-2である。
cをこの範囲で固定することで、Q_nの結果が使えるのである。
c=n-2, n-3, n-4, ・・・, 3, 2, 1 のときをそれぞれ考えて、
P_n = (n-2)・Q(2)＋(n-3)・Q(3)＋(n-4)・Q(4)＋・・・＋2・Q(n-2)＋1・Q(n-1)
= Σ_[k=2 to n-1] (n-k)・Q(k) = Σ_[k=2 to n-1] (n-k)・(k+1, 3)
= Σ_[k=2 to n-1] ((n+2)-(k+2))・(k+1, 3)
= (n+2)Σ_[k=2 to n-1] (k+1, 3)‐Σ_[k=2 to n-1] (k+2)(k+1, 3)
= (n+2)Σ_[t=3 to n] (t, 3)‐4Σ_[k=2 to n-1] (k+2, 4)
= (n+2)(n+1, 4)‐4Σ_[t=4 to n+1] (t, 4)
= 5・(n+2, 5)‐4(n+2, 5)
= (n+2, 5)
P_n = (n+2, 5) に n=100を代入すると、
P_100 = (102, 5) = 83291670 を得る。
この方法は明らかに一般化できる。
なぜなら、似たような式変形に対して、
(r+1)・(n+1, r+1) = (n+1)・(n, r)
Σ_[k=r to n] (k, r) = (n+1, r+1) をただ繰り返し使っているだけであるから。
面倒な計算は一切行っていない。
おまけ問題の結果は、
(n+99, 199) に対して、 n=10000を代入して得られた。
62870341973631462227866308134933797250054320153722
57774502472027613931615704524973508760441555985368
39080777715723555955605925688560252109237253858219
91231802132331602947051921753520852570809290345180
84331528832041936526494992999760990725192554445944
90281574256650147658195157317099010441960745866512
19761763679824262669639396493507880091716287900930
30758797833855949866496415031833861973580849280388
463169871775902239301418000
４２７桁・・・
(2)の解答。
まず、次の簡単な補題を示す。
それを用いれば問題は容易に解けるとおもう。
（補題）
n.kをn≧k≧0なる整数とし、任意に素数pを取れば、
v=v_p(C(n,k))とおいたとき、p^v≦n が成立する。
（証明）
任意に整数n.k（n≧k≧0）を与える。
任意に素数pを取り、v=v_p(C(n,k))とおく。
各正整数jに対して、f(j)=[n/p^j]-[k/p^j]-[(n-k)/p^j]とおく。
vは、Legendreの等式より、次のように表示される。
v=Σ_[j=1,+∞]f(j) ・・・й
各正整数jに対して、f(j)は0か1のいずれかの値しか取りえないので、
n/p^j≧1 を満たす最大の整数をj=m とすれば、
Σ_[j=1,+∞]f(j)=Σ_[j=1,m]f(j)≦1*m がいえる。
このことと、йより、v≦m がいえる。
よって、p^v≦p^m≦n （p^m≦nの成立はmの取り方から明らか）
これで証明が完了したといえる。
以下、本題の解答。
ω(P_n)≦3 を満たす整数n≧3を任意に取る。
m=n+2≧5 とおく。
相異なる素数p,q,rと、非負整数a,b,cを用いて、
P_n=(m,5)=p^a*q^b*r^c と表示できるが、
補題より、p^a*q^b*r^c≦m*m*m=m^3
よって、(m,5)≦m^3 の成立がいえるが、
これがm≧16で成立していないことは簡単な計算によりわかる。
なので、m≦15 であることがいえる。
一方、ω((h,5))≦3 を満たす整数h(5≦h≦15)が
h=5,6,7,8,9,10,12,13 の計8個で全てであるというのは
直接計算により確かめることができる。
以上より、ω(P_n)≦3 を満たす整数n≧3は
n=3,4,5,6,7,8,10,11 で全てであるといえる。
う〜ん...熟読玩味〜〜〜^^;
|
コメント（2）
