平成３０年１０月２８日

[流れ星]

　　　　第365回数学的な応募解答

　　　　＜解答募集期間：９月30日〜10月28日＞

［ユークリッドの互除法］

　

１以上の２つの整数ｍ、ｎ（ただしｎはｍより大きい）について次のような操作を行う。ｎをｍで割ったときの商を書いておいて、余りがあれば今度ｍをその余りで割って、余りのある限り繰り返す。

例えば、ｍ＝３１、ｎ＝９８のときはこうなる。

９８÷３１＝３、余りは５

３１÷５＝６、　余りは１

５÷１＝５、余りがない、操作終了

　このとき、出てきた商を順に書いてみると、３、６，５である。

そこで、３１と９８の相互関係は３，６、５であるという。また、相互関係に出てくる商の個数（３１と９８のときは３）を相互関係の長さという。

　例えば、８と１１の相互関係は１、２、１．２であるという。その長さは４である。

問題１　相互関係が１、２、１、１、３となる整数の組を１以上100以下の範囲ですべて求めなさい。

問題２　１以上100以下の範囲で相互関係が最も長くなるような整数の組を調べたところ、長さが９である組が最も長く、しかも1組しかありません。その1組を求めなさい。

「参考文献：ピーター先生と中学入試の算数に挑戦！」新潮社

「早起きのおじさん」 10/03 21時46分　受信 更新 10/28

●ユークリッドの互除法は、2数の最大公約数を求める方法です。

例えば、14580と2355の最大公約数は、次のように求められます。

まず、2数を並べて書きます。

大きい数を小さい数で割ります。（14580割る2355は、商6、余り450）

商6を14580の左側、余り450を14580の下に書きます。

そして、小さい数を余りで割ります。（2355割る450は、商5、余り105）

商5を2355の右側、余り105を2355の下に書きます。

次に、450と105を新たな2数として、上と同じことをします。

このようなことを繰り返していき、最後に余りが0となる場面があります。

このとき、すぐ前の余り15が、最初の2数の最大公約数となります。

ついでに、2355と14580の相互関係は、6,5,4,3,2となり、その長さは、5です。

●ユークリッドの互除法の仕組みを確認しておきます。

左右の2数の関係は、左にある商と余りを用いて、表すことができます。

左下がりの2数の関係は、右にある商と余りを用いて、表すことができます。

問題1

相互関係を計算する枠の左右に書いていきます。

黄色のところには、2数の最大公約数が入るので、1から5の場合を計算してみます。

上の仕組みを使い下から上に2数を求めます。

最大公約数が5のときは、大きい数が100より大きくなってしまいます。

よって、整数の組は、（18,25）、（36,50）、（54,75）、（72,100）の4つです。

問題2

100以下という制限があるので、なるべく小さくなるように考えます。

最大公約数が小さいこと、相互関係の数が小さいことを考えます。

最大公約数が1、相互関係が1の並びで最後のだけ2の場合を考えます。

相互関係の最後が1だと、下から2行目が1と1になってしまうからです。

右図の各数の関係を考えます。

商が最後以外1なので、i=h+g、h=g+f、g=f+e、f=e+d、e=d+c、d=c+b、c=b+a、b=a+1、のようになります。

順番に前2数の和が、次の数になっています。

これらは、初項1、第2項2のフィボナッチ数列です。

{1, 2, 3, 5, 8, 13, 21, 34, 55, 89}

計算しても、となり、（55,89）が求める組です。

●小さい2数になりそうな場合を考えます。

○相互関係の最後の数について

最大公約数が1、相互関係が1の並びで最後のだけ3の場合を考えます。

計算すると、となり、条件を満たしません。

○最大公約数が小さい場合

最大公約数が2、相互関係が1の並びで最後のだけ2の場合を考えます。

計算すると、となり、条件を満たしません。

○相互関係で1の並びの途中に2がある場合

・8番目の数が2のとき

aが増えた個数を数えると、

i=h+g、h=g+f、g=f+e、f=e+d、e=d+c、d=c+b、c=b+a、b=2a+1

　21　 　13 　8　　　5　　　3　　　2　　 　1　 　　1

のようになり、i＝89+2×21＝131

・7番目の数が2のとき、

ｂが増えた個数を数えると、

i=h+g、h=g+f、g=f+e、f=e+d、e=d+c、d=c+b、c=2b+a、b=a+1

　13 　8　　　5　　　3　　　2　　 　1　　　1

のようになり、i＝89+3×13＝128

・6番目の数が2のとき、

cが増えた個数を数えると、

i=h+g、h=g+f、g=f+e、f=e+d、e=d+c、d=2c+b、c=2b+a、b=a+1

　8　　　5　　　3　　　2　　 　1　　　1

のようになり、i＝89+5×8＝129

・5番目の数が2のとき、

dが増えた個数を数えると、

i=h+g、h=g+f、g=f+e、f=e+d、e=2d+c、d=2c+b、c=2b+a、b=a+1

　5　　　3　　　2　　 　1　　　1

のようになり、i＝89+8×5＝129

・4番目の数が2のとき、

eが増えた個数を数えると、

i=h+g、h=g+f、g=f+e、f=2e+d、e=d+c、d=2c+b、c=2b+a、b=a+1

　3　　　2　　 　1　　　1

のようになり、i＝89+13×3＝128

・3番目の数が2のとき、

fが増えた個数を数えると、

i=h+g、h=g+f、g=2f+e、f=2e+d、e=d+c、d=2c+b、c=2b+a、b=a+1

　2　　 　1　　　1

のようになり、i＝89+21×2＝131

・2番目の数が2のとき、

fが増えた個数を数えると、

i=h+g、h=2g+f、g=2f+e、f=2e+d、e=d+c、d=2c+b、c=2b+a、b=a+1

　1　　　1

のようになり、i＝89+34×1＝123

・1番目の数が2のとき、

fが増えた個数を数えると、

i=2h+g、h=2g+f、g=2f+e、f=2e+d、e=d+c、d=2c+b、c=2b+a、b=a+1

　1

のようになり、i＝89+55×1＝144

以上のようにどれも100を超えてしまいます。

増える個数は、初項1、第2項1のフィボナッチ数列になっています。

問題１　相互関係が１、２、１、１、３となる整数の組を１以上100以下の範囲ですべて求めなさい。

     a,b,c,d,e,fは自然数とし・・・�@

a÷b＝1余りc   a>b  a>c  

b÷c＝2余りd   b>c  b>d   

c÷d＝1余りe   c>d  c>e

d÷e＝1余りf   d>e  d>f

e÷f＝3余り0   e>f           a>b>c>d>e>f・・・�A

�@ �Aより

a=b+c

b=2c+d

c=d+e

d=e+f

e=3f

より

a=25f

b=18f

よって題意（a≦100）より

1≦f≦4

(a,b)=(25,18)、(50,36)、(75,54)、(100,72)・・・・回答

問題２　１以上100以下の範囲で相互関係が最も長くなるような整数の組を調べたところ、長さが９である組が最も長く、しかも1組しかありません。その1組を求めなさい。

　　　1以上100以下の自然数の組は、100*99/2＝4950組あります。これをすべて調べるのは難儀です。

そこで問題1と同じ要領で考えていきます。

　　　　記号が煩雑になるのでabcde・・・を、a₁,a₂,a₃・・・と書き換えます。また商をq₁ ,q₂ ,q₃・・・と書き換えます。

a_n-1で割り切れて終わる場合

a₁÷a₂＝q₁余りa₃

a₂÷a₃＝q₂余りa₄

a₃÷a₄＝q₃余りa₅

　　　　・

　　　　・

　　　　・

a_n-3÷a_n-2＝q_n-3余りa_n-1

a_n-2÷a_n-1＝q_n-2余りa_n=0

            q>0　、a₁> a₂> a₃> a₄> a₅>・・・>a_n・・・�@

長さが9と言う事は、n-2が9、n-1は10、nは11です。

即ち、

a₉÷a₁₀＝q₉余りa₁₁=0・・・�A

a₁とa_n-1との関係を書くと

a₁= q₁a₂+a₃

=q₁(q₂a₃+a₄)+a₃

= q₁(q₂(q₃a₄+a₅)+a₄)+ (q₃a₄+a₅)

= q₁(q₂(q₃(q₄ (q₅a₆+a₇)+a₆)+ (q₅a₆+a₇))+ (q₄(q₅a₆+a₇)+a₆))+ (q₃(q₄(q₅a₆+a₇)+a₆)+ (q₅a₆+a₇))

= q₁(q₂(q₃(q₄ (q₅(q₆a₇+a₈)+a₇)+ (q₆a₇+a₈))+ (q₅(q₆a₇+a₈)+a₇))+ (q₄(q₅(q₆a₇+a₈)+a₇)+ (q₆a₇+a₈)))

+ (q₃(q₄(q₅(q₆a₇+a₈)+a₇)+ (q₆a₇+a₈))+ (q₅(q₆a₇+a₈)+a₇))

= q₁(q₂(q₃(q₄ (q₅(q₆(q₇a₈+a₉)+a₈)+ (q₇a₈+a₉))+ (q₆(q₇a₈+a₉)+a₈))+ (q₅(q₆(q₇a₈+a₉)+a₈)+ (q₇a₈+a₉)))+ (q₄(q₅(q₆(q₇a₈+a₉)+a₈)+ (q₇a₈+a₉))+ (q₆(q₇a₈+a₉)+a₈)))

+ (q₃(q₄(q₅(q₆(q₇a₈+a₉)+a₈)+ (q₇a₈+a₉))+ (q₆(q₇a₈+a₉)+a₈))+ (q₅(q₆(q₇a₈+a₉)+a₈)+ (q₇a₈+a₉)))・・・・�B

ここまで書きましたが、�@�Aより

a₁₀>0

a₉>1

a₈>2

が言えますので�Bに

a₉=2、a₈=3、q₇=1（各々の最小値）を代入してみると

= q₁(q₂(q₃(q₄ (q₅(q₆(4)+3)+ (4))+ (q₆(4)+3))+ (q₅(q₆(4)+3)+ (4)))+ (q₄(q₅(q₆(4)+3)+ (4))+ (q₆(4)+3)))

+ (q₃(q₄(q₅(q₆(4)+3)+ (4))+ (q₆(4)+3))+ (q₅(q₆(4)+3)+ (4)))

さらにq₆に2を代入すると

= q₁(q₂(q₃(q₄ (q₅(15)+ (11))+ (q₅(11)+ (4)))+ (q₄(q₅(11)+ (4))+ (11)))

+ (q₃(q₄(q₅(11)+ (4))+ (11))+ (q₅(11)+ (4)))

これはq₁〜q₅まですべて1としても108となりoutです

よってq₁〜q₇＝1が言えます（∵式の形からq₆=1、q₁〜q₅を2としたときはa₁がさらに大きくなります）

したがって�Bは次のように変形できます

a₁= 21a₈+13a₉

ここから再度a₁とa₉との関係を書くと

a₁= 21(q₈a₉+a₁₀)+13a₉

　= 21(q₈(q₉a₁₀+a₁₁)+a₁₀)+13a₉

= 21(q₈q₉+1)a₁₀+13a₉（∵�Aよりa₁₁=0）・・・�C

a₁₀<a₉からa₁₀＝1、a₉＝2（各々の最小値）としたときq₉＝2

�Cに代入すると

a₁= 42q₈+47

q₈が1より大きなの値をとるときa₁は100より大きくなるので

q₈＝1

　　　以上から

　　　　a ₉＝2

　　　　a ₁₀＝1

q₁〜q₈＝1、q₉＝2

a₁＝89、a₂＝55

が一意に定まるので1組しかないことが言えます・・・・回答

調べてみるとフィボナッチ数列になるようです。（ラメの定理（小さい数の桁数の2倍以下の回数で求まる）もそれを利用しているようです）

今回は自力だけでどこまでやれるかやってみました。計算して並べるとフィボナッチ数列になっていました。

「スモークマン」 10/23 18時34分　受信 更新 10/28

問題365回

１以上の２つの整数ｍ、ｎ（ただしｎはｍより大きい）について次のような操作を行う。ｎをｍで割ったときの商を書いておいて、余りがあれば今度ｍをその余りで割って、余りのある限り繰り返す。

例えば、ｍ＝３１、ｎ＝９８のときはこうなる。

９８÷３１＝３、余りは５

３１÷５＝６、　余りは１

５÷１＝５、余りがない、操作終了

　このとき、出てきた商を順に書いてみると、３、６，５である。

そこで、３１と９８の相互関係は３，６、５であるという。また、相互関係に出てくる商の個数（３１と９８のときは３）を相互関係の長さという。

　例えば、８と１１の相互関係は１、２、１．２であるという。その長さは４である。

問題１　相互関係が１、２、１、１、３となる整数の組を１以上100以下の範囲ですべて求めなさい。

○/a=3

○/3a=1...a

○/4a=1...3a

○/7a=2...4a

○/18a=1...7a

最後の○=25a

so...(25,18),(50,36),(75,54),(100,72)

問題２　１以上100以下の範囲で相互関係が最も長くなるような整数の組を調べたところ、長さが９である組が最も長く、しかも1組しかありません。その1組を求めなさい。

割り切れずに続く...互いに素である...

1,1,2,3,5,8,13,21,34,55,89

89/55=1...34

55/34=1...21

34/21=1...13

21/13=1...8

13/8=1..5

8/5=1...3

5/3=1...2

3/2=1...1

1/1=1 の9回

so...

(89,55)