Challenge!

問題128　長方形から正方形へ
Weekend Mathematics／問題／問題128

１２８．長方形から正方形へ

縦の長さも横の長さも整数であるような、正方形でない長方形の形をした紙がある。この紙に対して、次の ような操作を繰り返す。

（操作）
その長方形にふくまれる最大の正方形を切り落とす。
操作後の紙が長方形であれば、操作を続け、操作後の紙が正方形であれば、そこで操作を終わる。 操作が終わるまでの回数を、元の長方形の「耐数」、最後に残った正方形の１辺の長さを、元の 長方形の「基本サイズ」ということにする。
例えば、２×５の長方形は、図のように操作が繰り返されるので、耐数３、基本サイズ１となる。

長方形から正方形へ

(1) １４４×２３３の長方形の耐数、基本サイズを求めよ。
(2) 短い方の辺の長さが整数、長い方の辺の長さが７２０である長方形で、耐数が６であるようなものはいくつあるか。
(3) 短い方の辺の長さが整数、長い方の辺の長さが８００である長方形で、基本サイズが２であるようなものはいくつあるか。
(4) (３２１－１)×(３１８－１)の長方形の基本サイズを求めよ。

問題の出典

広中杯ハイレベル中学数学に挑戦
算数オリンピック委員会監修
講談社ブルーバックス
2005年ファイナル問題

答えと解説

解答・その1

（ペンネ－ム：スモークマン）

(1) 233-144=89
144-89=55
89-55=34
55-34=21
34-21=13
21-13=8
13-8=5
8-5=3
5-3=2
3-2=1
2-1=1
よって、耐数＝11、基本サイズ＝1

解答・その2

（ペンネ－ム：テレスとアリス）

(1)
操作1　切り落とす正方形の一辺＝144　→　残りの長方形の縦と横の長さ＝144×89
操作2　切り落とす正方形の一辺＝89　→　残りの長方形の縦と横の長さ＝55×89
操作3　切り落とす正方形の一辺＝55　→　残りの長方形の縦と横の長さ＝55×34
操作4　切り落とす正方形の一辺＝34　→　残りの長方形の縦と横の長さ＝21×34
操作5　切り落とす正方形の一辺＝21　→　残りの長方形の縦と横の長さ＝21×13
操作6　切り落とす正方形の一辺＝13　→　残りの長方形の縦と横の長さ＝8×13
操作7　切り落とす正方形の一辺＝8　→　残りの長方形の縦と横の長さ＝8×5
操作8　切り落とす正方形の一辺＝5　→　残りの長方形の縦と横の長さ＝3×5
操作9　切り落とす正方形の一辺＝3　→　残りの長方形の縦と横の長さ＝3×2
操作10　切り落とす正方形の一辺＝2　→　残りの長方形の縦と横の長さ＝1×2
操作11　切り落とす正方形の一辺＝1　→　残りの長方形の縦と横の長さ＝1×1

よって、耐数＝11、基本サイズ＝1。

解答・その3

（ペンネ－ム：こまったコ）

(1) 長い方の辺の長さから短い方の辺の長さが何回取れるかを数えればよい。
　233÷144=1 余り　89
　144÷89=1 余り　55
　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
　2÷1=2　...このうち片方が最後に残る正方形。

1+1+1+1+1+1+1+1+1+1+2-1=11
よって耐数11、基本サイズ1。

(4)
３21-1= 10460353202
３18-1= 387420488
10460353202÷387420488=27 余り 26
387420488÷26=14900788
基本サイズは26。

解答・その4

（ペンネ－ム：レイ）

なかなかうまく解く方法を思いつかなかったので無理やり コンピューターに計算をさせました。 プログラムはエクセルのマクロです。アルゴリズムは ユークリッドの互除法に似た方法を使っております。

(1)基本サイズ １、耐数 １１

(2) 回答　8個
以下詳細
192、200、280、315、405、440、520、528

(3) 160個

(4)基本サイズ ２６、ちなみに耐数は 14900814

参考までに、以下プログラムの詳細です。

Sub BoxCal()
    Dim xx As Currency
    Dim yy  As Currency
    Dim taisu As Long
    Dim Tcounter As Integer
    Dim IsThisTSix As Integer

    taisu = 0
    IsThisTSix = 1
    Tcounter = 1
    xx = 720
    yy = 0
    
    While IsThisTSix < 720
        yy = IsThisTSix
    
        While xx > 0 And yy > 0
            If xx = yy Then
                GoTo NEXTNUMBER:
            Else
                If xx > yy Then
                    xx = xx - yy
                    taisu = taisu + 1
                Else
                    If yy > xx Then
                        yy = yy - xx
                        taisu = taisu + 1
                    End If
                End If
            End If
        Wend
        
NEXTNUMBER:
        If taisu = 6 Then
            Range("B" & Tcounter).Value = IsThisTSix
            Tcounter = Tcounter + 1
        End If
            
            IsThisTSix = IsThisTSix + 1
            taisu = 0
            xx = 720
    Wend
        
    Excel.Workbooks("BOX.xls").Worksheets("Sheet1").Select
    With Selection
    Range("A1").Value = Tcounter - 1
    End With
    
End Sub

Sub Kakunin()
    Dim xx As Currency
    Dim yy  As Currency
    Dim taisu As Long
    xx = (3 ^ 21 - 1)
    yy = (3 ^ 18 - 1)
    taisu = 0
    While xx > 0 And yy > 0
            If xx = yy Then
                GoTo NEXTNUMBER:
            Else
                If xx > yy Then
                    xx = xx - yy
                    taisu = taisu + 1
                Else
                    If yy > xx Then
                        yy = yy - xx
                        taisu = taisu + 1
                    End If
                End If
            End If
    Wend
NEXTNUMBER:
    Excel.Workbooks("BOX.xls").Worksheets("Sheet1").Select
    With Selection
    Range("A1").Value = taisu
    Range("A2").Value = xx
    Range("A3").Value = yy
    End With
End Sub


Sub Happyaku()
    Dim xx As Currency
    Dim yy  As Currency
    Dim taisu As Long
    Dim counter As Integer
    Dim IsTheGCDTwo As Integer
    IsTheGCDTwo = 2
    counter = 1
    While IsTheGCDTwo < 800
        yy = IsTheGCDTwo
        xx = 800
        While xx > 0 And yy > 0
                If xx = yy Then
                    GoTo NEXTNUMBER:
                Else
                    If xx > yy Then
                        xx = xx - yy
                        taisu = taisu + 1
                    Else
                        If yy > xx Then
                            yy = yy - xx
                            taisu = taisu + 1
                        End If
                    End If
                End If
        Wend
NEXTNUMBER:
        If yy = 2 Then
            Excel.Workbooks("BOX.xls").Worksheets("Sheet1").Select
                With Selection
                    Range("B" & counter).Value = IsTheGCDTwo
                End With
            counter = counter + 1
        End If
       
        IsTheGCDTwo = IsTheGCDTwo + 1
    Wend
    Excel.Workbooks("BOX.xls").Worksheets("Sheet1").Select
    With Selection
    Range("A1").Value = counter - 1
    End With
End Sub

解答・その5

（ペンネ－ム：転位反応）

(1)　長方形の長い方の辺の長さを短い方の辺の長さで割って、切り出せる正方形の個数をカウントする。
　　［長方形の長い方の辺の長さ］＝［正方形の個数］×［短い方の辺の長さ］＋［余った辺の長さ］
の計算式で整理すると以下の通り。

計算式切り出した正方形の個数の累計
233＝1×144＋891
144＝1×89＋552
89＝1×55＋343
55＝1×34＋214
34＝1×21＋135
21＝1×13＋86
13＝1×8＋57
8＝1×5＋38
5＝1×3＋29
3＝1×2＋110
2＝2×112

よって、この長方形の耐数は１１、基本サイズは１
この方法は、ユークリッドの互除法により最大公約数を求めることに等しい。

(2)　長方形の耐数が６であることは、７個の正方形から構成されていることを意味し、
そのうち最小の正方形の辺の長さは、長方形の縦と横の辺の長さの最大公約数に等しい。
ここで、720=24×32×5なので、最大公約数の候補は以下の通り。
1,2,3,4,5,6,8,9,12,15,16,18,20,24,30,36,40,45,48,60,72,80,90,120,144,180,240,360

さて、基本サイズａの正方形２個から出発して、常により大きな正方形ができるように全部で７個の 正方形を組合せると下記の長方形を作成できる。この長方形は面積最大で長い方の辺の長さも最大である。 横の辺の長さは２１ａなので、２１ａ＝７２０としてａ≒３４。よって、３６以上の最大公約数を考えれば良い。 さらに、80,120,240,360は40の倍数、90,180は45の倍数、144は72の倍数なので、結局のところ、 36,40,45,48,60,72の倍数を短い方の辺の長さとして、耐数を検証すればよい。

長方形から正方形へ
例えば、 720=3×200＋120
200=1×120＋80
120=1×80＋40
80=2×40
耐数は3+1+1+2-1=6

検証結果は、下記の通り８通り
36の倍数：該当無し
40の倍数：200,280,440,520
45の倍数：315,405
48の倍数：192,528
60の倍数：該当無し
72の倍数：該当無し

(3)　基本サイズが2ということは、最大公約数が2ということである。
800=25×52なので、
2の倍数から4及び10の倍数を除けば長方形の短い方の辺の長さが求められる
2～100で20通りあるので、2～798までは160通り

長方形から正方形へ

(4)　321-1=33（318-1）+33-1
318-1=(315+312+39+36+33+1)（33-1）
最大公約数は33-1、よって基本サイズは33-1=26

解答・その6

（ペンネ－ム：nao）

(1)
　　２３３÷１４４＝１・・・８９
　　１４４÷８９＝１・・・５５
　　８９÷５５＝１・・・３４
　　５５÷３４＝１・・・２１
　　３４÷２１＝１・・・１３
　　２１÷１３＝１・・・８
　　１３÷８＝１・・・５
　　８÷５＝１・・・３
　　５÷３＝１・・・２
　　３÷２＝１・・・１
　　２÷１＝２・・・０

答え　耐数１１　基本サイズ１

(2)
耐数が６ということは、正方形７つに切り分けられればよい。
一番小さい正方形のサイズを（１）として、（１）×２、（２）×３、（７）×２に 切り分けると長い方の辺の長さが（１６）になって７２０が割り切れる。
この場合 （７２０、３１５）の長方形ができ、基本サイズは４５になる。
同様にして、（１） ×２、（２）×３、（７）×１、（９）×１に切り分けても長い方の辺は（１６）に なり、やはり基本サイズ４５で、（７２０、４０５）の長方形ができる。
同様にして、調べた結果をまとめると、

基本サイズ４０のばあい
（７２０、２８０）：（１）×３、（３）×１、（４）×１、（７）×２
（７２０、４４０）：（１）×３、（３）×１、（４）×１、（７）×１、（９）×１
（７２０、２００）：（１）×２、（２）×１、（３）×１、（５）×３
（７２０、５２０）：（１）×２、（２）×１、（３）×１、（５）×２、（１３）×１

基本サイズ４５のばあい
（７２０、３１５）：（１）×２、（２）×３、（７）×２
（７２０、４０５）：（１）×２、（２）×３、（７）×１、（９）×１

基本サイズ４８のばあい
（７２０、１９２）：（１）×３、（３）×１、（４）×３
（７２０、５２８）：（１）×３、（３）×１、（４）×２、（１１）×１

これ以外にないということを検証するために、すべての可能性を挙げてみました。

（１）×７のばあい　長い方の辺（７）短い方の辺（１）
（１）×６、（６）×１のばあい　（７）と（６）
（１）×５、（５）×２のばあい　（１１）と（５）
（１）×５、（５）×１、（６）×１のばあい　（１１）と（６）
（１）×４、（４）×３のばあい　（１３）と（４）
（１）×４、（４）×２、（９）×１のばあい　（１３）と（９）
（１）×４、（４）×１、（５）×２のばあい　（１４）と（５）
（１）×４、（４）×１、（５）×１、（９）×１のばあい　（１４）と（９）
（１）×３、（３）×４のばあい　（１３）と（３）
（１）×３、（３）×３、（１０）×１のばあい　（１３）と（１０）
（１）×３、（３）×２、（７）×２のばあい　（１７）と（７）
（１）×３、（３）×２、（７）×１、（１０）×１のばあい　（１７）と（１０）
（１）×３、（３）×１、（４）×３のばあい　（１５）と（４）
（１）×３、（３）×１、（４）×２、（Ⅰ１）×１のばあい　（１５）と（１１）
（１）×３、（３）×１、（４）×１、（７）×２のばあい　（１８）と（７）
（１）×３、（３）×１、（４）×１、（７）×１、（Ⅰ１）×１のばあい　（１８）と（１１）
（１）×２、（２）×５のばあい　（１１）と（２）
（１）×２、（２）×４、（９）×１のばあい　（１１）と（９）
（１）×２、（２）×３、（７）×２のばあい　（１６）と（７）
（１）×２、（２）×３、（７）×１、（９）×１のばあい　（１６）と（９）
（１）×２、（２）×２、（５）×３のばあい　（１７）と（５）
（１）×２、（２）×２、（５）×２、（Ⅰ２）×１のばあい　（１７）と（１２）
（１）×２、（２）×２、（５）×１、（７）×２のばあい　（１９）と（７）
（１）×２、（２）×２、（５）×１、（７）×１、（Ⅰ２）×１のばあい　（１９）と（１２）
（１）×２、（２）×１、（３）×４のばあい　（１４）と（３）
（１）×２、（２）×１、（３）×３、（Ⅰ１）×１のばあい　（１４）と（１１）
（１）×２、（２）×１、（３）×２、（８）×２のばあい　（１９）と（８）
（１）×２、（２）×１、（３）×２、（８）×１、（Ⅰ１）×１のばあい　（１９）と（１１）
（１）×２、（２）×１、（３）×１、（５）×３のばあい　（１８）と（５）
（１）×２、（２）×１、（３）×１、（５）×２、（Ⅰ３）×１のばあい　（１８）と（１３）
（１）×２、（２）×１、（３）×１、（５）×１、（８）×２のばあい　（２１）と（８）
（１）×２、（２）×１、（３）×１、（５）×１、（８）×１、（Ⅰ３）×１のばあい　（２１）と（１３）

全部で３２の場合がありました。これで長い方の辺が７２０を割り切る数になってい るのは８つのばあいしかないといえたと思います。

(3)
（１）（２）の問題で分かるように、この問題はユークリッドの互除法による最大公 約数のみつけかたを図形であらわしたものである。 それで、長い方の辺の長さが８００である長方形で基本サイズが２になるということ は、８００と最大公約数が２になるものということである。

　　　８００÷２＝４００

４００と素になる数はたとえば１。 ８００と１×２＝２は基本サイズが２になる。また、そのつぎは３。 ８００と３×２＝６も最大公約数または基本サイズは２になる。 ４００の素因数は２と５なので、

　　　４００÷２＝２００　４００÷５＝８０　４００÷１０＝４０

で、２００＋８０ー４０＝２４０個が２または５で割り切れる数。 残りの４００―２４０＝１６０は４００と共通の因数を持たない。

答え１６０個

(4)
因数分解でなにかうまい方法があるかと考えたが、小学校レベルの私の力ではとても 及ばず、実際に割算を実行すればいいのだとおもいつきやってみたら、何とかできた ような気がする。

　　　(３２１－１)÷(３１８－１)＝３３・・・３３ー１
　　　(３１８－１)÷（３３ー１）＝３１５＋３１２＋３９＋３６＋３３＋１・・・０

たった２回で割り切れた。

耐数はできた正方形の数引く１なので３３＋３１５＋３１２＋３９＋３６ ＋３３＋１ー１＝３１５＋３１２＋３９＋３６＋３３×２ また基本サイズは最後に割り切った数なので３３ー１＝２６

解答・その7

（ペンネ－ム：kohji）

(操作Ａ)
A*B(A>B)の長方形について、
　　　A=C*B+D…(ア) A,B∈Ｎ C={C|A>B*Cとなる最大の自然数}
となるようにC,Dを定める。

(操作Ａ)は、
「(ア)はA*Bの長方形からB*Bの正方形をC個切り落とすとB*D(B≧D)の長方形が残る。」
ということを意味する。

つまり題意の(操作)は、(操作Ａ)で切り取られて残った長方形において更に(操作Ａ)を、切り取られて 残る長方形が正方形になるまで繰り返すことである。
また、A*Bの長方形の基本サイズは(ア)の式の形とユークリッド互除法よりA*Bの最大公約数となる。そ して耐数は {(ア)の式のCの和} で与えられる。

(1)
(操作Ａ)を繰り返すと、
　　　233=1*144+89
　　　144=1*89+55
　　　89=1*55+34
　　　55=1*34+21
　　　34=1*21+13
　　　21=1*13+8
　　　13=1*8+5
　　　8=1*5+3
　　　5=1*3+2
　　　3=1*2+1
　　　2=1*1+1

よって、基本サイズ 1、耐数 1*11=11

(2)
題意の(操作)において(操作Ａ)を繰り返す回数をmとする。
またn回目の(操作Ａ)の整数Cの値をCnとする。

(i)m=1のとき
C1=6なので、
720=6B+B ⇔ B=720/7 これは整数ではないので不適。

(ii)m=2のとき
(C1,C2)=(1,5),(2,4),(3,3),(4,2),(5,1)
720=C1*B+D
B=C2*D+D　⇔　D=720/(C1*C2+C1+1)
Bが整数のときDも整数となるが、
D=720/7,720/11,720/13,720/11 (同順) となるので不適。

(iii)m=3のとき
(C1,C2,C3)=(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)
720=C1*B+D
B=C2*D+E
D=C3*E+E　⇔　E=720/(C1*C2*C3+C1*C2+C1+1+C3)
∴E=720/11,720/13,720/13,720/11,360/7,720/17,45,48,720/17,360/7 (同順)
となり、Bが整数であることはEが整数であることの必要十分条件であることも考えて、Eが整数にな るものは2通りなので、Bは2通りある。

(iv)m=4のとき
(C1,C2,C3,C4)=(1,1,1,3),(1,1,2,2),(1,1,3,1),(1,2,1,2),(1,2,2,1),(1,3,1,1),(2,1,1,2),(2,1, 2,1),(2,2,1,1),(3,1,1,1)
720=C1*B+D
B=C2*D+E
D=C3*E+F
E=C4*F+F　⇔　F=720/(C1*C2*C3*C4+C1*C2*C3+C1*C2+C1+1+C3+C1*C4+C3*C4)
∴F=360/7,720/17,45,48,720/17,360/7,40,720/19,720/19,45 (同順)
となり、Bが整数であることはFが整数であることの必要十分条件であることも考えて、Fが整数にな るものは4通りなので、Bは4通りある。

(v)m=5のとき
(C1,C2,C3,C4,C5)=(1,1,1,1,2),(1,1,1,2,1),(1,1,2,1,1),(1,2,1,1,1),(2,1,1,1,1)
720=C1*B+D
B=C2*D+E
D=C3*E+F
E=C4*F+G
F=C5*G+G　⇔　G=720/(C1*C2*C3*C4*C5+C1*C2*C3*C4+C1*C2*C3+C1*C2+C1+1 +C1*C2*C5+C1*C4*C5+C3*C4*C5+C1*C4+C3*C4+C3+C5)
∴F=40,720/19,720/19,40,240/7 (同順)
となり、Bが整数であることはGが整数であることの必要十分条件であることも考えて、Gが整数にな るものは2通りなので、Bは2通りある。

(vi)m=6のとき
(C1,C2,C3,C4,C5,C6)=(1,1,1,1,1,1) なので、
720=B+D
B=1*D+E
D=1*E+F
E=1*F+G
F=1*G+H
G=1*H+H　⇔　H=720/21=240/7
Bが整数のときHも整数となるので不適。
(i)～(vi)より、求めるものは 2+4+2=8通り

(3)
8800以下の自然数で、800との最大公約数が2であるものの数を求めればよい。
800-(奇数∨4の倍数∨5の倍数)
　=800-{(奇数)+(4の倍数)+(5の倍数)-(奇数∧5の倍数)-(4の倍数∧5の倍数)}
　=800-{[800/2]+[800/4]+[800/5]-[800/5]/2-[800/20]}
　=800-(400+200+160-80-40)
　=160

(4)
321-1 と 318-1 の最大公約数を求めればよい。
　　　321-1=318(33-1)+318-1
　　　318-1=315(33-1)+315-1
　　　315-1=312(33-1)+312-1
　　　312-1=39(33-1)+39-1
　　　39-1=36(33-1)+36-1
　　　36-1=33(33-1)+33-1
以上の式とユークリッド互除法より基本サイズは 33-1=26

解答・その8

（ペンネ－ム：三角定規）

（１）
（２３３，１４４）→（１４４，８９）→（８９，５５）→（５５，３４）→（３４，２１）→（２１，１３）→（１３，８）→
　→（８，５）→（５，３）→（３，２）→（２，１）→（１，１）
となるから，耐数 １１，基本サイズ １ …［答］

（２）
どのように式を立てればいいのかわからなかったため，エクセルで虱潰しをしてみました。その結果，
　　（７２０，５２８）<基本サイズ４８>，（７２０，５２０）<４０>，（７２０，４４０）<４０>，（７２０，４０５）<４５>
　　（７２０，３１５）<４５>，（７２０，２８０）<４０>，（７２０，２００）<４０>，（７２０，１９２）<４８>　の　８個 … ［答］

（３）
基本サイズが ２ ということは，８００ と N の最大公約数が ２ ということで，
８００＝２5×５2　だから，題意を満たす N の条件は，
　　　(1)　素因数 ２ を１個だけ持つ。
　　　(2)　素因数 ５ を持たない。
この２つの条件を満たす整数は，
１～４００ までの奇数（２００個）から ５ の倍数を除いたもの（１６０個）を ２ 倍した偶数 で，その個数は，１６０ 個…［答］

（４）
　　　ｘ18－１＝（ｘ3－１）（ｘ15＋ｘ12＋ｘ9＋ｘ6＋ｘ3＋１）
　　　ｘ21－１＝（ｘ3－１）（x18＋ｘ15＋ｘ12＋ｘ9＋ｘ6＋ｘ3＋１）
ｘ15＋ｘ12＋ｘ9＋ｘ6＋ｘ3＋１　と　x18＋ｘ15＋ｘ12＋ｘ9＋ｘ6＋ｘ3＋１　は互いに素だから， ｘ18－１　とｘ21－１　の最大公約数は，ｘ3－１。
ｘ に ｘ＝３ とし， ３18－１　と　３21－１　の最大公約数は，３3－１＝２６。
よって， ３18－１　と　３21－１　の基本サイズは　２６ …［答］

解答・その9

（ペンネ－ム：夜ふかしのつらいおじさん）

この問題はユークリッドの互除法と同じ内容です。 耐数とは、大きい方の数を小さい方の数で割ることを繰り返していったときの商の和です。 基本数とは最後の余りつまり２つの数の最大公約数です。 ２数、Ａ，Ｂ（Ａ＞Ｂ）の最大公約数をＧとします。 すると、Ａ＝Ａ’Ｇ、Ｂ＝Ｂ’Ｇと表せます。 ＡをＢで割ったときの商をＱ、余りをＲとすると、 Ａ＝ＢＱ＋Ｒ Ｒ＝Ａ－ＢＱ 　＝Ａ’Ｇ－Ｂ’ＧＱ 　＝Ｇ(Ａ’－Ｂ’Ｑ) つまり余りは最大公約数Ｇを因数に持ちます。 次にＢをＲ(Ｂ＞Ｒ)で割ります。 この余りも上と同様の考えでＧを因数に持つことが分かります。 このような計算を繰り返していくとそのうちに割り切れます。 その直前の余りがＧになります。 ユークリッドの互除法の特徴はもともとの数の因数を知らなくても良いことです。

この問題で直感的に答が分かるのは（４）です。
　　　３21－１＝｛(３3)7－１｝＝(３3－１){(３3)6＋(３3)5＋(３3)4＋(３3)3＋(３3)2＋(３3)+１}
　　　３18－１＝｛(３3)6－１｝＝(３3－１){(３3)5＋(３3)4＋(３3)3＋(３3)2＋(３3)+１}
より、３3－１＝２６が２数の公約数であることは分かります。

ｘ＝３3とおくと

長方形から正方形へ
より、x6-1とx7-1の最大公約数は、x-1です。

次に解答が分かるのは（３）です。
８００より小さくて、８００との最大公約数が２である数を求めれば良いことになります。
８００＝２5×５2なので、その数の２以外の因数は次のようです。

1101201301
3103203303
7107207307
9109209309
11111211311
13113213313
17117217317
9119219319
21121221321
23123223323
27127227327
29129229329
31131231331
33133233333
37137237337
39139239339
41141241341
43143243343
47147247347
49149249349
51151251351
53153253353
57157257357
59159259359
61161261361
63163263363
67167267367
69169269369
71171271371
73173273373
77177277377
79179279379
81181281381
83183283383
87187287387
89189289389
91191291391
93193293393
97197297397
99199299399

表の数は１から４００までの数で偶数と５の倍数を除いたものです。
以上 １６０ 個です。

（１）は次のように解きます。
はじめに２数のうち大きい方を左、小さい方を右に置きます。 次に「大きい数と小さい数の差」と「小さい方の数」で大きい方を左、小さい方を右に置きます。 以下この手続きを繰り返し２数が同じになれば止めます。

ステップ　　
0233144
114489
28955
35534
43421
52113
6138
785
853
932
1021
1111

より耐数は１１です。

（２）は次のように解きます。
基本数の正方形に何回か正方形を継ぎ足していき長方形を作ります。 初めはどこから始めても良いので右に決めます。 以下正方形を継ぎ足す方向は左右には本質的な差がないので右とします。 以下正方形を継ぎ足す方向は上下には本質的な差がないので下とします。 このように右から初めて、右か下かに正方形を６回継ぎ足すことを考えると以下の結果になります。 ２通りの判断を５回するので、２5＝３２通りの場合があります。 実際は逆にたどって基本形に戻ります。 できあがった長方形を、長い方の辺×短い方の辺として表します。 ７２０＝２4×３2×５なので長い方の辺が７２０の約数になっていれば良いことになります。 次のように８個あります。















解答・その10

（ペンネ－ム：のっこん）

（1）
233÷144＝1　余り89
144÷89＝１　余り55
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
2÷1＝2
商の和は12、つまり正方形が12個できる
よって耐数は　12－1＝11　　　基本サイズは1
（余りがフィボナッチ数列になっていてすごい！）
（233は素数だから基本サイズ1は当たり前といえば当たり前）

（2）
耐数が6だから、正方形は7個できる
つまり割り算をしていった時の商の和が7になればよい
割り算の回数は、720は7の倍数ではないから1回ということはなく、 また、最後の商が1ということはありえないから7回ということもない。
つまり割り算の回数は2～6回と考えてよい。 従って自然数を○として、
　　○＋○＝7、○＋○＋○＝7、○＋○＋○＋○＝7、
　　○＋○＋○＋○＋○＝7、○＋○＋○＋○＋○＋○＝7
となればよい。これを満たすのは、最後の商が1になることはないから次の31通り
　　1－6、2－5、3－4、4－3、5－2
　　1－1－5、1－2－4、2－1－4、1－4－2、4－1－2、
　　1－3－3、3－1－3、2－2－3、2－3－2、3－2－2、
　　1－1－1－4、1－1－2－3、1－2－1－3、2－1－1－3、1－1－3－2、
　　1－3－1－2、3－1－1－2、1－2－2－2、2－1－2－2、2－2－1－2、
　　1－1－1－1－3、1－1－1－2－2、1－1－2－1－2、
　　1－2－1－1－2、2－1－1－1－2、1－1－1－1－1－2

各々について点検すると（これが大変な作業です）
　　（点検例）1－6の時
　　　　720÷x＝1　余りa
　　　　　x÷a＝6　　x＝6aだから　720＝x＋a＝7a・・・・・×
題意を満たすのは次の8通り
【１】3－1－3　　この時は192
【２】2－3－2　　　　〃　　315
【３】1－2－1－3　　　　〃　528
【４】2－1－1－3　　　　〃　280
【５】1－1－3－2　　　　〃　405
【６】3－1－1－2　　　　〃　200
【７】1－1－1－1－3　　〃　440
【８】1－2－1－1－2　　〃　520
よって8個

（3）
800＝25・52
基本サイズが2ということは最大公約数が2ということだから
【１】「2・奇数」となっているものの個数を数える
　　　2、6、10、14、・・・
　　　4n-2＜800　よりその数は200
【２】そのうち、5の倍数となっているものを除く
　　　10、30、50、・・・
　　　20n-10＜800　よりその数は40
　　よって答えは　200－40＝160（個）

(4)
（321－1）÷（318－1）＝33　余り33－1
（318－1）は（36－1）という因子をもち、 （36－1）はまた、（33－1）という因子をもつから、 （318－1）は（33－1）で割り切れる
よって基本サイズは33－1＝26

数学らしい問題を出していただいたことに感謝しています！

解答・その11

（ペンネ－ム：杖のおじさん）

答え
問題１．１１です。　問題２．８です。　問題３．１６０個です。　問題４．基本サイズは２６です。

問題１

ＣＡＳＩＯ　ＦＸ　８７０Ｐでプログラムを作り解きました。　次の通りです。
１０　Ｎ＝０
２０　ＩＮＰＵＴ”タテハ  ？”，Ｘ
３０　ＩＮＰＵＴ”ヨコハ　？”， Ｙ
４０　ＩＦ　Ｘ＞Ｙ　ＴＨＥＮ　Ｘ＝Ｘ－Ｙ　ＥＬＳＥ　Ｙ＝Ｙ－Ｘ
５０　ＩＦ　Ｘ＝Ｙ　ＴＨＥＮ　Ｎ＝Ｎ＋１　：ＧＯＴＯ　８０
６０　Ｎ＝Ｎ＋１
７０　ＧＯＴＯ　４０
８０　ＰＲＩＮＴ”タイスウ＝”；Ｎ；”キホンサイズ＝”；Ｘ
９０　ＧＯＴＯ　１０
Ｘに１４４と入力する。Ｙに２３３と入力する。結果次の答えが表示されました。
答は　耐数＝１１　基本サイズ＝１となります。

問題２
基本サイズ１、長さ７２０について

　１耐数２耐数３耐数４耐数５耐数(　６　耐　数)　
（１，１）（１，２）（１，３）（１，４）（１，５）（１，６）（１，７）（６，７）
　　（２，３）（３，４）（４，５）（５，６）（５，１１）（６，１１）
　　　（２，５）（３，７）（４，９）（４，１３）（９，１３）
　　　（３，５）（４，７）（５，９）（５，１４）（９，１４）
　　　　（２，７）（３，１０）（３，１３）（１０，１３）
　　　　（５，７）（７，１０）（７，１７）（１０，１７）
　　　　（３，８）（４，１１）（４，１５）（１１，１５）
　　　　（５，８）（７，１１）（７，１８）（１１，１８）
　　　　　（２，９）（２，１１）（９，１１）
　　　　　（７，９）（７，１６）（９，１６）
　　　　　（５，１２）（５，１７）（１２，１７）
　　　　　（７，１２）（７，１９）（１２，１９）
　　　　　（３，１１）（３，１４）（１１，１４）
　　　　　（８，１１）（８，１９）（１１，１９）
　　　　　（５，１３）（５，１８）（１３，１８）
　　　　　（８，１３）（８，２１）（１３，２１）

　　 この中で６耐数の右側の数字７，１１，１３，１４，１７，１５，１８，１１，１６， １９，２１で７２０を除算した結果整数になる数は１５，１６，１８です。 従ってその個数は８個です。

問題３
８００の基本サイズ２を縮小して４００の基本サイズ１として最大公約数を計算しました。 下１桁が１，３，７，９があるものが最大公約数の自然個数なので次の式で計算します。 ４００÷１０×４個＝１６０個です。

問題４
３２１－１と３１８－１　の最大公約数を求めます。 ３進法で表現すると２つの数は倍数である事が分かります。従ってその最大公約数は ３進法の２の個数を計算します。 ２０－１７＝３　１０進法に直すと３３－１＝２６です。基本サイズ２６です。

解答・その12

（ペンネ－ム：ヒャクレン・ラランジャ）

(1)耐数：１１、基本サイズ：１
長方形の各辺の長さを(ａ，ｂ)の形で表示する。
（１４４，２３３）
（１４４，８９）
（５５，８９）
（５５，３４）
（２１，３４）
（２１，１３）
（８，１３）
（８，５）
（３，５）
（３，２）
（１，２）
（１，１）

(2)８個
６回の作業が終わった状態から、さかのぼってみる。
６回の作業終了時点の正方形の一辺をａとおく。

（ａ，ａ） ５回の作業終了時
　（２ａ，ａ）
４回の作業終了時
　（３ａ，ａ），（３ａ，２ａ）
３回の作業終了時
　（４ａ，ａ），（４ａ，３ａ），（５ａ，２ａ），（５ａ，３ａ）
２回の作業終了時
　（５ａ，ａ），（５ａ，４ａ），（７ａ，４ａ），（７ａ，３ａ），（７ａ，５ａ），（７ａ，２ａ），
　（８ａ，５ａ），（８ａ，３ａ）
１回の作業終了時
　（６ａ，５ａ），（６ａ，ａ），（９ａ，５ａ），（９ａ，４ａ），（１１ａ，７ａ），（１１ａ，４ａ），
　（１０ａ，７ａ），（１０ａ，３ａ），（１２ａ，７ａ），（１２ａ，５ａ），（９ａ，７ａ），（９ａ，２ａ），
　（１３ａ，８ａ），（１３ａ，５ａ），（１１ａ，８ａ），（１１ａ，３ａ）
もとの長方形
　（１１ａ，６ａ），（１１ａ，５ａ），（７ａ，６ａ），（７ａ，ａ），（１４ａ，９ａ），（１４ａ，５ａ），
　（１３ａ，９ａ），（１３ａ，４ａ），（１８ａ，１１ａ），（１８ａ，７ａ），（１５ａ，１１ａ），（１５ａ，４ａ），
　（１７ａ，１０ａ），（１７ａ，７ａ），（１３ａ，１０ａ），（１３ａ，３ａ），（１９ａ，１２ａ），（1９ａ，７ａ），
　（１７ａ，１２ａ），（１７ａ，５ａ），（１６ａ，９ａ），（１６ａ，７ａ），（１１ａ，９ａ），（１１ａ，２ａ），
　（２１ａ，１３ａ），（２１ａ，８ａ），（１８ａ，１３ａ），（１８ａ，５ａ），（１９ａ，１１ａ），（１９ａ，８ａ），
　（１４ａ，１１ａ），（１４ａ，３ａ）

このうち、長辺が７２０の条件に合うのは、
　（１８ａ，１１ａ），（１８ａ，７ａ），（１５ａ，１１ａ），（１５ａ，４ａ），
　（１６ａ，９ａ），（１６ａ，７ａ），（１８ａ，１３ａ），（１８ａ，５ａ）の８個

(3) １６０個
基本サイズの大きさは、長方形の２辺の最大公約数になる。
８００よりも小さい数で、８００との最大公約数が２になるものを考える。
求める数は、２×Ａ とあらわせる。
ただし、Ａは４００より小さく、２でも５でも割れない数。なぜなら、
　　８００＝２×２×２×２×２×５×５
なので。３９９以下の整数で２でも５でも割れないものの個数は、１６０個。

(4) ２６
(３２１－１)と(３１８－１)の最小公倍数を求める。
　(３２１－１)×(３１８－１)
　(（３３)７－１）×((３３)６－１)
　(２７７－１）×(２７６－１)
ここで一回、正方形を切り取ると、
　(２７７－２７６）×(２７６－１)
　２７６(２７－１）×(２７６－１)
　２７６(２６）×(２７６－１)
ここで右辺を因数分解する
　２７６(２６）×(２７３－１)(２７３＋１)
　２７６(２６）×(２７－１)(２７２＋２７＋１)(２７＋１)(２７２－２７＋１)
　２７６(２６）×(２６)(７５７)(２８)(７０３)
よって、最大公約数は２６

解答・その13

（ペンネ－ム：バルタン星人）

今回は、結構hardでした。

(1) 答え 耐数１１、基本サイズ１
233、89、34、13、5、2、1
144、55、21、 8、3、1
順に考えました。逆から見ると前２項の和となるフィボナッチ数列ですね。

(2)答え８
逆の(1,1)から６回の操作を考えました。１回目は(1,2)だけ。
２回目は1+2=3を1または2と置き換え。このようにすると32通りできる。
全てを求め、そのうち大きい方が720の約数であるものを選びました。
(4,15)×48　１９２　　(11,15)×48　５２８
(7,18)×40　２８０　　(11,18)×40　４４０
(7,16)×45　３１５　　( 9,16)×45　４０５
(5,18)×40　２００　　(13,18)×40　５２０

(3) 答え１６０個
長辺８００、基本サイズ２の組み合わせは、長辺４００、基本サイズ１と 個数は同じ。長辺と短辺が公約数を持つとき、基本サイズは(最大)公約数と なるので基本サイズが１となるのは互いに素な時。 ４００は２４×５２なので１～４００で、２及び５の約数を持たない 個数を求めればよい。
２の約数２００個、５の約数８０個、１０の約数４０個
４００－（２００＋８０－４０）＝１６０

(4)答え２６
　　　 (３２１－１)＝２７×(３１８－１)＋２６
２７回の操作で短辺は２６になる。
　　　(３１８－１)＝(３６－１)×(３１２＋３６＋１)
　　＝(３３－１)×(３３＋１)×(３１２＋３６＋１)
　　＝２６×２８×（７２９×７２９＋７２９＋１）
２６の倍数となるので基本サイズは２６
間違えて耐数まで求めてしまい大変でした。

解答・その14

（ペンネ－ム：巷の夢）

（1）題意より

長方形から正方形へ
と言うように順次正方形を作っていくと11回目で1の正方形となる。因って、耐数は11、基本サイズ1となる。 又、A×Bの長方形のAとBを変化させ、試行錯誤を繰り返すと、基本サイズは数AとBの最大公約数であることが確かめられる。

（2）（1）の逆を試みる。今、長い辺をB、短い辺をAとし、この操作により出来る長方形を（A,B）と表すと、

長方形から正方形へ
これより（1,7）（6,7）などができ長い方の辺720の約数である（4,15）（11,15）など8個となる事が分かる。

（3）（1）の試行錯誤の結果より最大公約数は2であれば良い。 即ち、400までの数のうち、奇数であることが必要。 但し、下桁が5であると最大公約数が5で無くなるため1,3,7及び9でなければならない。 因って、400×4/10＝160が求めるものである。

（4）これまでの議論から両辺の最大公約数を求めれば良い。

長方形から正方形へ
因って、これら2数の最大公約数は となる。これより基本サイズは26である。

解答・その15

（ペンネ－ム：Toru）

これは全くユークリッドの互除法ですね。こんなのが中学数学とは考えられません が。

(1)
　144x233→144x89→55x89→55x34→21x34→21x13→8x13→8x5→3x5→3x2→1x2→1x1
より耐数は１１　基本サイズは１

(2)
1x1から逆に正方形をくっつけていくと２回目以降は縦につけるか横につけるか で、２通りずつあり 　0) 1x1
　1) 1x2
　2) 1x3,3x2
　3) 1x4,4x3,3x5,5x2
　4) 1x5,5x4,4x7,7x3,3x8,8x5,5x7,7x2
　5) 1x6,6x5,5x9,9x4,4x11,11x7,7x10,10x3,3x11,11x8,8x13,13x5,5x12,12x7,7x9,9x2
　6) 1x7,7x6,6x11,11x5,5x14,14x9,9x13,13x4,4x15,15x11,11x18,18x7,7x17,17x10,10x13,
　　13x10,3x14,14x3,11x19,19x8,8x21,21x13,13x18,18x5,5x17,17x12,12x19,19x7,7x16,
　　16x9,9x11,11x2
の３２通りの可能性があるが、長い方が７２０の約数でなければならないので
　720=24x32x5 より
4x15,15x11,11x18,18x7,13x18,18x5 ,7x16,16x9の８通りがある。
それぞれ、短い方の辺（基本サイズ）
192(48),528(48), 440(40),280(40),520(40),200(40),315(45),405(45)

(3)
800 で基本サイズが２であるから 400で１　400と素な数を数えればよい
φ(400)=φ(24x52)=400(1-1/2)(1-1/5)=160　（φはオイラー関数）

(4)
321-1と318-1の最大公約数を求める。
(321-1,318-1) =(321-1-33(318-1),318-1)=(33-1,318-1)=33-1=26

正解者

バルタン星人 のっこん Toru
ヒャクレン・ラランジャ 巷の夢 夜ふかしのつらいおじさん
レイ 転位反応 スモークマン
杖のおじさん こまったコ nao
三角定規 テレスとアリス kohji

まとめ

今月の問題は、ユークリッドの互除法がテーマの問題でしたが、ちょっとハードでしたでしょうか。
ユークリッドの互除法については、夜ふかしのつらいおじさんが説明をしてくださっています。
（１）にある１４４、２３３という数字は、隣り合ったフィボナッチ数ですね。 のっこんさんのご指摘になるように、この操作を繰り返すと、 フィボナッチ数列をさかのぼることになります。 おもしろいですね。
（２）で戸惑っていらっしゃる方が多いように思いますが、 この操作を繰り返すと、最終的には、 ヒャクレン・ラランジャさんの解答にあるように、ａ×ａの正方形になりますから、 そこからさかのぼっていくとよいのではないでしょうか。いずれにしても、漏れなく探していくしかないのかなと思います。

top