KAMINA PUBLICATIONS／懸賞18解答

■　懸賞 ・ １８桁の自然数Ａがあります。Ａの上９桁と下９桁を入れ換えて１８桁の自然数Ｂを作ったところ、ＢはＡの倍数になりました。
ＡとＢの最上位桁は何でしょうか。
ただし、Ａ≠Ｂとします。
・ 『入れ換え』の解説を少々。Ａ＝１１２２３３４４５５６６７７８８９９のとき、Ｂ＝５６６７７８８９９１１２２３３４４５です。 この例では残念ながらＢはＡの倍数にはなっていません。
■　解答 ・ Ａの最上位桁は１、Ｂの最上位桁は８。
・ 解答者は、北村太路氏、岡田麻知弘氏、若林氏、もず氏の４名（解答到着順）。全員正解でした。 ちょっと難しかったようで解答が少なかったので色々かさ上げしました。
・ 厳正なる抽選の結果、「東京おとなクラブ」懸賞当選者は若林氏となりました。送付先をお知らせください。
■　解説 ・ Ａの上９桁をＣ、下９桁をＤとします。
また、ＢはＡのｍ倍だとします。


Ａ＝１０９×Ｃ＋Ｄ
Ｂ＝１０９×Ｄ＋Ｃ
Ｂ＝ｍＡ


したがって、


（１０９−ｍ）×Ｄ＝（ｍ×１０９−１）×Ｃ


となります。
１０９−ｍとｍ×１０９−１の最大公約数をＧとすると、 Ｃは（１０９−ｍ）／Ｇの倍数、 Ｄは（ｍ×１０９−１）／Ｇの倍数になります。 それで、ｍは２以上（Ａ≠Ｂ）、９以下（１０以上だとＢの桁数が１８を越えてしまう）なので、 この範囲のｍについて１０９−ｍとｍ×１０９−１を素因数分解してＧを求めてみたのが下表です。


ｍ １０９−ｍ ｍ×１０９−１ Ｇ Ｃの最小値＝
（１０９−ｍ）／Ｇ		 Ｄの最小値＝
（ｍ×１０９−１）／Ｇ
２ ２×６９１×７２３５８９ ３１×６４５１６１２９ １ ９９９９９９９９８ １９９９９９９９９９
３ ７１×２２５１×６２５７ １６９３７×１７７１２７ １ ９９９９９９９９７ ２９９９９９９９９９
４ ２×２×３×８３３３３３３３ ３×１５７×８４９２５６９ ３ ３３３３３３３３２ １３３３３３３３３３
５ ５×８９×１４４７×１５５３ １７×１４０３３×２０９５９ １ ９９９９９９９９５ ４９９９９９９９９９
６ ２×７×７１４２８５７１ ７×１４８３×５７７９７９ ７ １４２８５７１４２ ８５７１４２８５７
７ ３×１７×１９６０７８４３ ３×１０１６３×２２９５９１ ３ ３３３３３３３３１ ２３３３３３３３３３
８ ２×２×２×４９９×２５０５０１ １９９９×４００２００１ １ ９９９９９９９９２ ７９９９９９９９９９
９ ６７×１４９２５３７３ １５１×５２３×１１３９６３ １ ９９９９９９９９１ ８９９９９９９９９９


この表から、


Ｃ＝１４２８５７１４２
Ｄ＝８５７１４２８５７
Ａ＝１４２８５７１４２８５７１４２８５７
Ｂ＝８５７１４２８５７１４２８５７１４２


がわかります。
１０９−ｍとｍ×１０９−１の素因数分解はちょっと大変かもしれません。
ユークリッドの互除法を用いると最大公約数は割りと簡単に求められます。
とりあえず、（ｍ×１０９−１）−ｍ×（１０９−ｍ）＝ｍ２−１を素因数分解する手もあります。
■　北村太路氏 
解法）
Ａの上９桁をx、下９桁をyとします。

問題文より、n(1,000,000,000x+y)=1,000,000,000y+x
移項して、(1,000,000,000n-1)x=(1,000,000,000-n)y・・・@

まず、ｎについて考えます。
Ａ（１８桁）をｎ倍しても１８桁（Ｂ）のままなので、ｎ＜１０。
またＡ≠Ｂなので、ｎ＞１。
ｎは２〜９までの整数です。

次に@の式について考えます。
1,000,000,000n-1をv、1,000,000,000-nをwとします。
vとwが互いに素だと仮定すると、@の式が成立するにはyがvの倍数ではないといけませんが、
yは９桁、ｎが２〜９までの整数なのでvは１０桁なので、そのようなyとvはとれませんので
仮定が間違っていたことになります。

vとwの最大公約数をuとします。
vとwは互いに素ではないのでu＞１です。
?の式を変形して、
u(v/u)x=u(w/u)y

両辺をu(v/u)で割ると
  (w/u)y
x=------
   v/u

uが最大公約数なので、w/uとv/uは互いに素。
そしてxが整数ですので、yはv/uで割り切れることになります。

ここから力ワザで、nが２〜９までの間のvとwの最大公約数uを求めてみます。
「なんとか（名前を失念）のふるい」という方法で求めてみました。

「なんとかのふるい」の方法、２つの整数がある。
大きい方から小さい法を引く、差があればまた大きい方から小さい方を引く。
同じ値になったら、その値が最大公約数。

例）  234  54
     ---------
      180  54
     ---------
      126  54
     ---------
       72  54
     ---------
       18  54
     ---------
       18  36
     ---------
       18  18

１８が最大公約数。

で、おのおの計算。
n=2、v=1,999,999,999、w=999,999,998、vとwの最大公約数u=1。 
n=3、v=2,999,999,999、w=999,999,997、vとwの最大公約数u=1。 
n=4、v=3,999,999,999、w=999,999,996、vとwの最大公約数u=3。 
n=5、v=4,999,999,999、w=999,999,995、vとwの最大公約数u=1。 
n=6、v=5,999,999,999、w=999,999,994、vとwの最大公約数u=7。 
n=7、v=6,999,999,999、w=999,999,993、vとwの最大公約数u=3。 
n=8、v=7,999,999,999、w=999,999,992、vとwの最大公約数u=1。 
n=9、v=8,999,999,999、w=999,999,991、vとwの最大公約数u=1。 

u>1でなくてはいけないので、n＝４，６，７のいずれか。
ｎ＝４、７の時は、
n=4、v=3,999,999,999、u=3、v/u=1,333,333,333
n=7、v=6,999,999,999、u=3、v/u=2,333,333,333
で、v/uで割り切れる９桁のyはないから不適。

ｎ＝６の時
n=6、v=5,999,999,999、u=7、v/u=857,142,857
v/uで割り切れる９桁の数は、857,142,857そのものしかありえないので、
y=857,142,857

  (w/u)y  999,999,994/7*857,142,857
x=------=---------------------------=142,857,142
   v/u           857,142,857

よって、Ａ＝142,857,142,857,142,857
        Ｂ＝857,142,857,142,857,142

ということで最上位桁は１と８。

感想）
見慣れた数字（１４２８５７）でがっかり。７分の１、７分の６、というやつですね。
しかし、問題、答えに１８が出て、なおかつ唯一解なことに気づいた人間が偉い、とも言える。
途中力ワザでなく、なんとかしたかった。
エレガントな解法が披露されるのが楽しみです。
東京もウルトラＱも興味がないので、そういうのが好きな人に当たることを望みます。
「なんとか（名前を失念）のふるい」というのは「エラトステネスのふるい」のことでしょうか。これは最大公約数を求める方法ではなくて素数を拾い出す方法ですね。
■　岡田麻知弘氏
御無沙汰しております。
Ａ＝１
Ｂ＝８　・・・　他にもあるのか否か...:-J
（Ｂ＝６Ａ）
大学の同級生。山口で高校の先生をしている。年賀状の返事として寄せられたものですが、正解なので載せました。ごめん＞岡田
■　若林氏
年賀パズル、今回は難しいですね。Bの最上位桁が4以上で あることくらいしか見えていません。単純に最上位桁（と10桁目だけ見ても） 39通り残りますね。まあ、答えは(1,8)だと当てずっぽうで行って 当たったとしても存在証明はともかくそれ以外ないことの証明が難しそうです。
別件メールの余談として寄せられたものですが、正解なので載せました。ごめんなさい＞若林さん
■　もず氏 
A = 142857142857142857
B = 857142857142857142
A*6 = B
が答えです。

A = X*10^9 + Y
B = Y*10^9 + X
A*n = B 
(10^8 <= X,Y < 10^9。nは2から9までの整数。)
とおく。

B = A*n に代入して変形すると
Y*10^9 + X = (X*10^9 + Y)*n
Y*(10^9 - n) = X*(n*10^9 - 1)
             = X*( n*(10^9 - n) + n^2 - 1 )
移項してまとめると
(Y - n*X)*(10^9 - n) = X*(n^2 - 1)           (*)

これより、Y > n*X。
Y < 10^9 なのでX < 10^9 / n がわかる。
10^9 - n と n^2 - 1 の最大公約数をdとおくと、
(*)式より、(10^9 - n)/d はXの約数でなければならない。
特に、X >= (10^9 - n)/d 。
もし、10^9 / n >= (10^9 - n)/d が成立していると、求めるXは存在しない。
すなわち、(10^9 - n)*n < 10^9 *d が必要。
特に、n <= d が必要なことがわかる。
表を作る。


 n   10^9 - n  n^2 -1  d
--------------------------
 2   999999998    3    1
 3   999999997    8    1
 4   999999996   15    3
 5   999999995   24    1
 6   999999994   35    7
 7   999999993   48    3
 8   999999992   63    1
 9   999999991   80    1


この表より、n >= d が成立しているのは n=6 のときだけ。
このとき、(10^9 - n)/d = 999999994/7 = 142857142 がXの約数。
X >= 10^8 から X = 142857142 となるしかなく、
これを(*)式に代入して計算すると Y = 857142857 となる。
たしかに、
142857142857142857 * 6 = 857142857142857142
となっている。
もずさんは、締切ぎりぎりで解答してくださいました。ありがとうございました。
戻る