|
問題541
Aを16桁の整数とする。Aから連続する桁かの数字をうまく取り出すと、それらの数字の積を平方数にできることを証明せよ。
解答
0を含むと積が0となるから除いてよい。
1から9までの数字はすべて2^a3^b5^c7^dのかたちに一意的に表せる。
（1,4,9 は数字1つでも平方数になるんですけどね ^^）
よって1桁からi桁までの積をAiとすると
Ai=2^ai3^bi5^ci7^diと表せる。
A,b,c,dをすべてmod2で表すと
a≡b≡c≡d≡0
のとき2^a3^b5^c7^dは平方数となる。
ところでa,b,c,dが0または1のとき(a,b,c,d)は2^4=16個しかない。
よって(1)あるAiについて(ai,bi,ci,di)≡(0,0,0,0)
または(2)あるi<jについて(ai,bi,ci,di)≡(aj,bj,cj,dj)
(1)のときAi=1桁からi桁までの積が平方数となる
(2) のときAj/Ai=(i+1)桁からj桁までの積が平方数となる。
後半がいまいち理解できなかったけど、、、つまり、、、
Ai が16種類しかないので、16 桁並べれば1個は mod 2 で0になるものがあるはずだってことですよね？^^v
・dobaさんのもの Orz〜(2007.5.31.)
★Aの各ケタの中に、０が１個でも出現する場合は、必ず題意を満たす。
★０が１個も出現しない場合
Aの左からmケタ目からnケタ目までの積をP(m,n)と書くものとする。
また、ある自然数nを素因数分解したとき、
ある素数pが偶数回（０回も含む）出現する場合にf(n,p)=0,
奇数回出現する場合にf(n,p)=1となるような
nとpの関数f(n,p)を考え、
f(n,2),f(n,3),f(n,5),f(n,7)を並べたものを
v(n)=(f(n,2),f(n,3),f(n,5),f(n,7))と定義する。
f(n,2),f(n,3),f(n,5),f(n,7)はいずれも0か1の値をとるので、
v(n)には16通りのパターンがある。
もし、v(P(1,n)) (n=1,2,…,16)が全て異なる場合、
v(n)は16通りしかないので、全てのパターンが出現し、
n(P(1,k))=(0,0,0,0)となるようなkが存在する。
そのとき、P(1,k)は明らかに平方数。
もし、v(P(1,n)) (n=1,2,…,16)の中のある２つが同じである場合、
v(P(1,j))=v(P(1,k)) (1≦j＜k≦16)となるような整数j,kが存在する。
この場合、
P(j+1,k)=P(1,k)/P(1,j)は
n(P(j+1,k))=(0,0,0,0)を満たし、
そのとき、P(j+1,k)は明らかに平方数。
いつもながら鮮やかです♪
画像：ほしのあき ちゃん ^^
|
コメント（0）
