|
問題637の解答です ^^
http://www.junko-k.com/mondai/mondai128.htm Orz〜
再掲：
縦の長さも横の長さも整数であるような、正方形でない長方形の形をした紙がある。この紙に対して、次の ような操作を繰り返す。
（操作）
その長方形にふくまれる最大の正方形を切り落とす。
操作後の紙が長方形であれば、操作を続け、操作後の紙が正方形であれば、そこで操作を終わる。 操作が終わるまでの回数を、元の長方形の「耐数」、最後に残った正方形の１辺の長さを、元の 長方形の「基本サイズ」ということにする。
例えば、２×５の長方形は、図のように操作が繰り返されるので、耐数３、基本サイズ１となる。
(1) １４４×２３３の長方形の耐数、基本サイズを求めよ。
(2) 短い方の辺の長さが整数、長い方の辺の長さが７２０である長方形で、耐数が６であるようなものはいくつあるか。
(3) 短い方の辺の長さが整数、長い方の辺の長さが８００である長方形で、基本サイズが２であるようなものはいくつあるか。
(4) (３２１−１)×(３１８−１)の長方形の基本サイズを求めよ。
解答
・転位反応さんのもの Orz〜
(1) 長方形の長い方の辺の長さを短い方の辺の長さで割って、切り出せる正方形の個数をカウントする。
［長方形の長い方の辺の長さ］＝［正方形の個数］×［短い方の辺の長さ］＋［余った辺の長さ］
の計算式で整理すると以下の通り。
計算式 切り出した正方形の個数の累計
233＝1×144＋89 1
144＝1×89＋55 2
89＝1×55＋34 3
55＝1×34＋21 4
34＝1×21＋13 5
21＝1×13＋8 6
13＝1×8＋5 7
8＝1×5＋3 8
5＝1×3＋2 9
3＝1×2＋1 10
2＝2×1 12
よって、この長方形の耐数は１１、基本サイズは１
この方法は、ユークリッドの互除法により最大公約数を求めることに等しい。
(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
わたしも近いことを考えてたんですけどね。。。^^;
・Toruさんのもの Orz〜
これは全くユークリッドの互除法ですね。こんなのが中学数学とは考えられませんが。
(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
どこでわたしは間違ったのかよ〜く考えてみよっと。^^;v
|
コメント（0）
