Challenge!

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

128.長方形から正方形へ

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

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

長方形から正方形へ

(1) 144×233の長方形の耐数、基本サイズを求めよ。
(2) 短い方の辺の長さが整数、長い方の辺の長さが720である長方形で、耐数が6であるようなものはいくつあるか。
(3) 短い方の辺の長さが整数、長い方の辺の長さが800である長方形で、基本サイズが2であるようなものはいくつあるか。
(4) (321−1)×(318−1)の長方形の基本サイズを求めよ。


問題の出典

広中杯ハイレベル中学数学に挑戦
算数オリンピック委員会監修
講談社ブルーバックス
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)基本サイズ 1、耐数 11

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

(3) 160個

(4)基本サイズ 26、ちなみに耐数は 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

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

(2) 長方形の耐数が6であることは、7個の正方形から構成されていることを意味し、
そのうち最小の正方形の辺の長さは、長方形の縦と横の辺の長さの最大公約数に等しい。
ここで、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

さて、基本サイズaの正方形2個から出発して、常により大きな正方形ができるように全部で7個の 正方形を組合せると下記の長方形を作成できる。この長方形は面積最大で長い方の辺の長さも最大である。 横の辺の長さは21aなので、21a=720としてa≒34。よって、36以上の最大公約数を考えれば良い。 さらに、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

検証結果は、下記の通り8通り
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)
  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・・・0

答え 耐数11 基本サイズ1

(2)
耐数が6ということは、正方形7つに切り分けられればよい。
一番小さい正方形のサイズを(1)として、(1)×2、(2)×3、(7)×2に 切り分けると長い方の辺の長さが(16)になって720が割り切れる。
この場合 (720、315)の長方形ができ、基本サイズは45になる。
同様にして、(1) ×2、(2)×3、(7)×1、(9)×1に切り分けても長い方の辺は(16)に なり、やはり基本サイズ45で、(720、405)の長方形ができる。
同様にして、調べた結果をまとめると、

基本サイズ40のばあい
(720、280):(1)×3、(3)×1、(4)×1、(7)×2
(720、440):(1)×3、(3)×1、(4)×1、(7)×1、(9)×1
(720、200):(1)×2、(2)×1、(3)×1、(5)×3
(720、520):(1)×2、(2)×1、(3)×1、(5)×2、(13)×1

基本サイズ45のばあい
(720、315):(1)×2、(2)×3、(7)×2
(720、405):(1)×2、(2)×3、(7)×1、(9)×1

基本サイズ48のばあい
(720、192):(1)×3、(3)×1、(4)×3
(720、528):(1)×3、(3)×1、(4)×2、(11)×1

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

(1)×7のばあい 長い方の辺(7)短い方の辺(1)
(1)×6、(6)×1のばあい (7)と(6)
(1)×5、(5)×2のばあい (11)と(5)
(1)×5、(5)×1、(6)×1のばあい (11)と(6)
(1)×4、(4)×3のばあい (13)と(4)
(1)×4、(4)×2、(9)×1のばあい (13)と(9)
(1)×4、(4)×1、(5)×2のばあい (14)と(5)
(1)×4、(4)×1、(5)×1、(9)×1のばあい (14)と(9)
(1)×3、(3)×4のばあい (13)と(3)
(1)×3、(3)×3、(10)×1のばあい (13)と(10)
(1)×3、(3)×2、(7)×2のばあい (17)と(7)
(1)×3、(3)×2、(7)×1、(10)×1のばあい (17)と(10)
(1)×3、(3)×1、(4)×3のばあい (15)と(4)
(1)×3、(3)×1、(4)×2、(T1)×1のばあい (15)と(11)
(1)×3、(3)×1、(4)×1、(7)×2のばあい (18)と(7)
(1)×3、(3)×1、(4)×1、(7)×1、(T1)×1のばあい (18)と(11)
(1)×2、(2)×5のばあい (11)と(2)
(1)×2、(2)×4、(9)×1のばあい (11)と(9)
(1)×2、(2)×3、(7)×2のばあい (16)と(7)
(1)×2、(2)×3、(7)×1、(9)×1のばあい (16)と(9)
(1)×2、(2)×2、(5)×3のばあい (17)と(5)
(1)×2、(2)×2、(5)×2、(T2)×1のばあい (17)と(12)
(1)×2、(2)×2、(5)×1、(7)×2のばあい (19)と(7)
(1)×2、(2)×2、(5)×1、(7)×1、(T2)×1のばあい (19)と(12)
(1)×2、(2)×1、(3)×4のばあい (14)と(3)
(1)×2、(2)×1、(3)×3、(T1)×1のばあい (14)と(11)
(1)×2、(2)×1、(3)×2、(8)×2のばあい (19)と(8)
(1)×2、(2)×1、(3)×2、(8)×1、(T1)×1のばあい (19)と(11)
(1)×2、(2)×1、(3)×1、(5)×3のばあい (18)と(5)
(1)×2、(2)×1、(3)×1、(5)×2、(T3)×1のばあい (18)と(13)
(1)×2、(2)×1、(3)×1、(5)×1、(8)×2のばあい (21)と(8)
(1)×2、(2)×1、(3)×1、(5)×1、(8)×1、(T3)×1のばあい (21)と(13)

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

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

   800÷2=400

400と素になる数はたとえば1。 800と1×2=2は基本サイズが2になる。また、そのつぎは3。 800と3×2=6も最大公約数または基本サイズは2になる。 400の素因数は2と5なので、

   400÷2=200 400÷5=80 400÷10=40

で、200+80ー40=240個が2または5で割り切れる数。 残りの400―240=160は400と共通の因数を持たない。

答え160個

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

   (321−1)÷(318−1)=3・・・3ー1
   (318−1)÷(3ー1)=315+312+3+3+3+1・・・0

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

耐数はできた正方形の数引く1なので3+315+312+3+3 +3+1ー1=315+312+3+3+3×2 また基本サイズは最後に割り切った数なので3ー1=26


解答・その7

(ペンネ−ム:kohji)

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

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

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

(1)
(操作A)を繰り返すと、
   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)
題意の(操作)において(操作A)を繰り返す回数をmとする。
またn回目の(操作A)の整数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

(ペンネ−ム:三角定規)

(1)
(233,144)→(144,89)→(89,55)→(55,34)→(34,21)→(21,13)→(13,8)→
 →(8,5)→(5,3)→(3,2)→(2,1)→(1,1)
となるから,耐数 11,基本サイズ 1 …[答]

(2)
どのように式を立てればいいのかわからなかったため,エクセルで虱潰しをしてみました。その結果,
  (720,528)<基本サイズ48>,(720,520)<40>,(720,440)<40>,(720,405)<45>
  (720,315)<45>,(720,280)<40>,(720,200)<40>,(720,192)<48> の 8個 … [答]

(3)
基本サイズが 2 ということは,800 と N の最大公約数が 2 ということで,
800=25×52 だから,題意を満たす N の条件は,
   (1) 素因数 2 を1個だけ持つ。
   (2) 素因数 5 を持たない。
この2つの条件を満たす整数は,
1〜400 までの奇数(200個)から 5 の倍数を除いたもの(160個)を 2 倍した偶数 で,その個数は,160 個…[答]

(4)
   x18−1=(x3−1)(x15+x12+x9+x6+x3+1)
   x21−1=(x3−1)(x18+x15+x12+x9+x6+x3+1)
15+x12+x9+x6+x3+1 と x18+x15+x12+x9+x6+x3+1 は互いに素だから, x18−1 とx21−1 の最大公約数は,x3−1。
x に x=3 とし, 318−1 と 321−1 の最大公約数は,33−1=26。
よって, 318−1 と 321−1 の基本サイズは 26 …[答]


解答・その9

(ペンネ−ム:夜ふかしのつらいおじさん)

この問題はユークリッドの互除法と同じ内容です。 耐数とは、大きい方の数を小さい方の数で割ることを繰り返していったときの商の和です。 基本数とは最後の余りつまり2つの数の最大公約数です。 2数、A,B(A>B)の最大公約数をGとします。 すると、A=A’G、B=B’Gと表せます。 AをBで割ったときの商をQ、余りをRとすると、 A=BQ+R R=A−BQ  =A’G−B’GQ  =G(A’−B’Q) つまり余りは最大公約数Gを因数に持ちます。 次にBをR(B>R)で割ります。 この余りも上と同様の考えでGを因数に持つことが分かります。 このような計算を繰り返していくとそのうちに割り切れます。 その直前の余りがGになります。 ユークリッドの互除法の特徴はもともとの数の因数を知らなくても良いことです。

この問題で直感的に答が分かるのは(4)です。
   321−1={(33)7−1}=(33−1){(33)6+(33)5+(33)4+(33)3+(33)2+(33)+1}
   318−1={(33)6−1}=(33−1){(33)5+(33)4+(33)3+(33)2+(33)+1}
より、33−1=26が2数の公約数であることは分かります。

x=33とおくと

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

次に解答が分かるのは(3)です。
800より小さくて、800との最大公約数が2である数を求めれば良いことになります。
800=25×52なので、その数の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

表の数は1から400までの数で偶数と5の倍数を除いたものです。
以上 160 個です。

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

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

より耐数は11です。

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
















解答・その10

(ペンネ−ム:のっこん)

(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
商の和は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通り
【1】3−1−3  この時は192
【2】2−3−2    〃  315
【3】1−2−1−3    〃 528
【4】2−1−1−3    〃 280
【5】1−1−3−2    〃 405
【6】3−1−1−2    〃 200
【7】1−1−1−1−3  〃 440
【8】1−2−1−1−2  〃 520
よって8個

(3)
800=25・52
基本サイズが2ということは最大公約数が2ということだから
【1】「2・奇数」となっているものの個数を数える
   2、6、10、14、・・・
   4n-2<800 よりその数は200
【2】そのうち、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

(ペンネ−ム:杖のおじさん)

答え
問題1.11です。 問題2.8です。 問題3.160個です。 問題4.基本サイズは26です。

問題1

CASIO FX 870Pでプログラムを作り解きました。 次の通りです。
10 N=0
20 INPUT”タテハ  ?”,X
30 INPUT”ヨコハ ?”, Y
40 IF X>Y THEN X=X−Y ELSE Y=Y−X
50 IF X=Y THEN N=N+1 :GOTO 80
60 N=N+1
70 GOTO 40
80 PRINT”タイスウ=”;N;”キホンサイズ=”;X
90 GOTO 10
Xに144と入力する。Yに233と入力する。結果次の答えが表示されました。
答は 耐数=11 基本サイズ=1となります。

問題2
基本サイズ1、長さ720について

 1耐数2耐数3耐数4耐数5耐数( 6 耐 数) 
(1,1)(1,2)(1,3)(1,4)(1,5)(1,6)(1,7)(6,7)
  (2,3)(3,4)(4,5)(5,6)(5,11)(6,11)
   (2,5)(3,7)(4,9)(4,13)(9,13)
   (3,5)(4,7)(5,9)(5,14)(9,14)
    (2,7)(3,10)(3,13)(10,13)
    (5,7)(7,10)(7,17)(10,17)
    (3,8)(4,11)(4,15)(11,15)
    (5,8)(7,11)(7,18)(11,18)
     (2,9)(2,11)(9,11)
     (7,9)(7,16)(9,16)
     (5,12)(5,17)(12,17)
     (7,12)(7,19)(12,19)
     (3,11)(3,14)(11,14)
     (8,11)(8,19)(11,19)
     (5,13)(5,18)(13,18)
     (8,13)(8,21)(13,21)

   この中で6耐数の右側の数字7,11,13,14,17,15,18,11,16, 19,21で720を除算した結果整数になる数は15,16,18です。 従ってその個数は8個です。

問題3
800の基本サイズ2を縮小して400の基本サイズ1として最大公約数を計算しました。 下1桁が1,3,7,9があるものが最大公約数の自然個数なので次の式で計算します。 400÷10×4個=160個です。

問題4
21−1と318−1 の最大公約数を求めます。 3進法で表現すると2つの数は倍数である事が分かります。従ってその最大公約数は 3進法の2の個数を計算します。 20−17=3 10進法に直すと3−1=26です。基本サイズ26です。


解答・その12

(ペンネ−ム:ヒャクレン・ラランジャ)

(1)耐数:11、基本サイズ:1
長方形の各辺の長さを(a,b)の形で表示する。
(144,233)
(144,89)
(55,89)
(55,34)
(21,34)
(21,13)
(8,13)
(8,5)
(3,5)
(3,2)
(1,2)
(1,1)

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

(a,a) 5回の作業終了時
 (2a,a)
4回の作業終了時
 (3a,a),(3a,2a)
3回の作業終了時
 (4a,a),(4a,3a),(5a,2a),(5a,3a)
2回の作業終了時
 (5a,a),(5a,4a),(7a,4a),(7a,3a),(7a,5a),(7a,2a),
 (8a,5a),(8a,3a)
1回の作業終了時
 (6a,5a),(6a,a),(9a,5a),(9a,4a),(11a,7a),(11a,4a),
 (10a,7a),(10a,3a),(12a,7a),(12a,5a),(9a,7a),(9a,2a),
 (13a,8a),(13a,5a),(11a,8a),(11a,3a)
もとの長方形
 (11a,6a),(11a,5a),(7a,6a),(7a,a),(14a,9a),(14a,5a),
 (13a,9a),(13a,4a),(18a,11a),(18a,7a),(15a,11a),(15a,4a),
 (17a,10a),(17a,7a),(13a,10a),(13a,3a),(19a,12a),(19a,7a),
 (17a,12a),(17a,5a),(16a,9a),(16a,7a),(11a,9a),(11a,2a),
 (21a,13a),(21a,8a),(18a,13a),(18a,5a),(19a,11a),(19a,8a),
 (14a,11a),(14a,3a)

このうち、長辺が720の条件に合うのは、
 (18a,11a),(18a,7a),(15a,11a),(15a,4a),
 (16a,9a),(16a,7a),(18a,13a),(18a,5a)の8個

(3) 160個
基本サイズの大きさは、長方形の2辺の最大公約数になる。
800よりも小さい数で、800との最大公約数が2になるものを考える。
求める数は、2×A とあらわせる。
ただし、Aは400より小さく、2でも5でも割れない数。なぜなら、
  800=2×2×2×2×2×5×5
なので。399以下の整数で2でも5でも割れないものの個数は、160個。

(4) 26
(321−1)と(318−1)の最小公倍数を求める。
 (321−1)×(318−1)
 ((3)−1)×((3)−1)
 (27−1)×(27−1)
ここで一回、正方形を切り取ると、
 (27−27)×(27−1)
 27(27−1)×(27−1)
 27(26)×(27−1)
ここで右辺を因数分解する
 27(26)×(27−1)(27+1)
 27(26)×(27−1)(27+27+1)(27+1)(27−27+1)
 27(26)×(26)(757)(28)(703)
よって、最大公約数は26


解答・その13

(ペンネ−ム:バルタン星人)

今回は、結構hardでした。

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

(2)答え8
逆の(1,1)から6回の操作を考えました。1回目は(1,2)だけ。
2回目は1+2=3を1または2と置き換え。このようにすると32通りできる。
全てを求め、そのうち大きい方が720の約数であるものを選びました。
(4,15)×48 192  (11,15)×48 528
(7,18)×40 280  (11,18)×40 440
(7,16)×45 315  ( 9,16)×45 405
(5,18)×40 200  (13,18)×40 520

(3) 答え160個
長辺800、基本サイズ2の組み合わせは、長辺400、基本サイズ1と 個数は同じ。長辺と短辺が公約数を持つとき、基本サイズは(最大)公約数と なるので基本サイズが1となるのは互いに素な時。 400は2×5なので1〜400で、2及び5の約数を持たない 個数を求めればよい。
2の約数200個、5の約数80個、10の約数40個
400−(200+80−40)=160

(4)答え26
    (321−1)=27×(318−1)+26
27回の操作で短辺は26になる。
   (318−1)=(3−1)×(312+3+1)
  =(3−1)×(3+1)×(312+3+1)
  =26×28×(729×729+729+1)
26の倍数となるので基本サイズは26
間違えて耐数まで求めてしまい大変でした。


解答・その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
より耐数は11 基本サイズは1

(2)
1x1から逆に正方形をくっつけていくと2回目以降は縦につけるか横につけるか で、2通りずつあり  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
の32通りの可能性があるが、長い方が720の約数でなければならないので
 720=24x32x5 より
4x15,15x11,11x18,18x7,13x18,18x5 ,7x16,16x9の8通りがある。
それぞれ、短い方の辺(基本サイズ)
192(48),528(48), 440(40),280(40),520(40),200(40),315(45),405(45)

(3)
800 で基本サイズが2であるから 400で1 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

まとめ

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


top