2011年7月30日土曜日

条件付きの倍数

「とっておきの数学パズル」に0,1,2という問題があった. 2.2

「十進表記で0と1のみからなる自然数nの0でない倍数が存在する」というのである.

計算してみると0から9のnについて, 次のようになる. つまり3は37倍すると1だけの十進数111となる.

n 倍 十進表記
0 1 0
1 1 1
2 5 10
3 37 111
4 25 100
5 2 10
6 185 1110
7 143 1001
8 125 1000
9 12345679 111111111

この9の場合はタイガー計算器でよく遊んだ計算である.

十進表記の求め方を考えてみた. %で剰余を表すと, 3の場合は, 1%3=1, 10%3=1, 100%3=1だから, 111ではその和が3, つまり剰余が0, よって111は3の倍数である.

7の場合は, 1%7=1, 10%7=3, 100%7=2, 1000%7=6だから, 和が7の倍数になるように1と1000を選び, 1001が7の倍数となるわけだ.

そこで早速プログラムを考えてみる.

10のべきをnで割った剰余のべき集合の和のnによる剰余が0のものを求めたい.

まず(0)なるリストを用意する. これは空のべき集合である. 次に10の0乗, 1をnで割った剰余1を, これまでのリストの各要素に足し, (1)が出来, これを(0)の前にappendする. (1 0)が出来る.

次は10の1乗, 10をnで割った剰余を, これまでのリストの各要素に足す. nが7なら, 剰余3を足し, (4 3)が出来る. appendすると(4 3 1 0)になる. それぞれ(11 10 1 0)を7で割った剰余である.

同様に100を7で割った剰余2を足すと(6 5 3 2)が出来, appendして(6 5 3 2 4 3 1 0)になる. この段階では, 最後の0以外に7の倍数はないので, まだ続ける.

1000でやると剰余は10の時の剰余3と100の時の剰余2の積で6. よって新しいリストは(12 11 9 8 10 9 7 6)となり, べき集合に7の倍数7が現れた.

7は新しいリストにあるから1000番台は1, リストの右半分にあるから, 100番台は0, そのまた右半分にあるから, 10番台も0, その(7 0)では左にあるから, 1番台は1で, 結局1001が7の0と1による倍数(の最小のもの)であった.

Schemeのプログラムは次のとおり.

(define (zeroone n e rs)
(let* ((r (modulo e n))
(rs1 (map (lambda (x) (modulo (+ x r) n)) rs)))
(if (member 0 rs1)
(- (length (member 0 (append rs1 rs))) 1)
(zeroone n (* e 10) (append rs1 rs)))))

引数のeは10の順次のべきで, 最初の起動では1, rsはリストで最初は(0). let*で用意するrはこの桁の剰余, rs1は新しいリストである. let*の後の本体のifは, 新しいリストに0があるかを見, あればその位置を返す. なければ次の桁へ進む.

起動は次のようにする.

(zeroone 13 1 '(0))

9が結果の値だが, これを二進で1001としたのが求める十進表記になる. n=2から20までの値は

(map (lambda (x) (zeroone x 1 '(0))) (a2b 2 21)) =>
(2 7 4 2 14 9 8 511 2 3 28 9 18 14 16 29 1022 25 4)

二進で示すと

(map (lambda (x) (number->string (zeroone x 1 '(0)) 2))
(a2b 2 21)) =>
("10" "111" "100" "10" "1110" "1001" "1000" "111111111"
"10" "11" "11100" "1001" "10010" "1110" "10000" "11101"
"1111111110" "11001" "100")


ところでこういう倍数が存在する理由はなにか. 10のべきをnで割った剰余を表示してみると:

(define (foo n)
(map (lambda (x) (modulo (expt 10 x) n)) (a2b 0 20)))

(foo 2) =>
(1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(foo 3) =>
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(foo 4) =>
(1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(foo 5) =>
(1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(foo 6) =>
(1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4)
(foo 7) =>
(1 3 2 6 4 5 1 3 2 6 4 5 1 3 2 6 4 5 1 3)
(foo 8) =>
(1 2 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(foo 9) =>
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

のようで, 0があるものはその桁を1つとれば完成. 0がないものは剰余だから当然同じ数が何回も現れる. その桁をn個足せば当然nの倍数が得られるわけだ.

面白い問題であった. ところでこういう条件付き倍数の生成を対数表の計算で利用した人がいた. Edward Sangのその話は次回に.

2011年7月28日木曜日

板チョコ分割

数日前に書いた私のツィッター

割れ目でm×nのピースになる板チョコ. 割れ目に沿って割りピースにまで分ける時の割る回数は, 割る順に関係なく一定とパズル本にあった. 証明は易しい. トーナメントの試合数を思い出す.

について書いてみたい.

これは先頃頂いた, ピーター・ウィンクラー著, 坂井, 岩沢, 小副川訳「とっておきの数学パズル」にあったものだ. 8.11

やってみよう.



2×3だと, たしかにすべて5回だ.



3×4だと, 11回. ということは, m×n-1かもしれない.

そこで数学的帰納法のお出ましとなる.



m×nに分割する回数をf(m,n)と書き, m×n-1であろうとして証明する. f(1,1)は分割するまでもなく1区画になっているから, 1×1-1=0だ.

n≥1,n'≥1,n+n'>1について, nとn'の幅に分割したとする. 分割に1回かかるから, f(1,n+n')=f(1,n)+f(1,n')+1={仮定により}(n-1)+(n'-1)+1=n+n'-1. 横1列の板チョコの分割はf(1,n)=n-1で良さそうである.




今度は縦がm≥1,m'≥1でm+m'列ある板チョコを, m列とm'列に分割したとする. 分割に今度も1回かかるから,

f(m+m',n)=f(m,n)+f(m',n)+1={仮定により}(m×n-1)+(m'×n-1)+1
=(m+m')×n-1

確かにf(m,n)=m×n-1であった.


こんなに簡単な式だと, もっと別のエレガントな考え方がありそうだ.




板チョコは最初 ひと(1)塊である. 1回分割すると, ふた(2)塊になる. そのいずれかを分割すると, 3塊になる. つまり, t回分割すると, t+1塊が得られる. 斯くしてm×n塊が得られるまでには, m×n-1回の分割が必要なのであった.


問題を解くとき, とりあえず絶対に答がえられそうな, 正面からの道をとる. それで答が得られてから, 次にもっとうまい手がないか探すのが, 私の普段のやり方だ. プログラムを書くときもそうで, きたなくてもよいから, まず動くプログラムを書く. すると見通しがよくなり, さらにきれいで速いプログラムが得られるのである.

2011年7月23日土曜日

ラスターグラフィック

TAOCPV4F1はビット操作が前半の話題で, 当然ラスターグラフィックの話も登場する. そのうち, 細線化アルゴリズムの話は前に書いた. 今回は, 塗り潰しについて.

ビットマップが閉曲線で囲まれている時, その内部を塗り潰したい. PostScriptなら, 閉曲線を描き. strokeの代りにfillとすればよい. ProcessingならFill(色); としておくと, その色で塗り潰してくれるから, 簡単である.

それを自分でやる方法が, filling algorithmである.

TAOCPによると, 正方形ピクセルの2次元配列を, 円錐曲線が正方形の中心のいずれの側を通るかにより, 縦横の線の境界で分離するのは簡単だそうである.

下の図はTAOCPの7.1.3(171)を私が描き直したもので, 黒の曲線で示す, 円錐曲線の代表選手, 長軸20, 短軸10の楕円の長軸の右端の辺りのピクセルの様子である. 右下の黒丸の座標が(20,0)だ.



ピクセルの格子点は, x, yが整数値のところに対応している. 座標の整数値の間にピクセルがあるから, ピクセルの中央の座標には, 1/2が付くわけだが, それはいやらしいから, ピクセルの右上の隅の座標で指定する.

従って, ピクセル(20,0)は, 黒丸の左下のピクセルである.

さて, このピクセルを塗るべきか否かは, ピクセルの中央における, 楕円の式の値の正負で決める. 丁度0のところを楕円が通る. 楕円の式は(x/20)2+(y/10)2-1=0だが, ピクセルの中央の値は, xとyからそれぞれ1/2を引いて計算する.

つまり, ピクセル(x,y)の中央の値は,
((x-1/2)/20)2+((y-1/2)/10)2-1
=(x2-x+1/4)/400+(y2-y+1/4)/100-1

1/4や1/100がついて回って, これもやめたいから整数係数にする

400倍して
x2-x+1/4+4y2-4y+1-400
4倍して
4x2-4x+1+16y2-16y+4-1600
=4x2+16y2-4x-16y+1+4-1600
=4x2+16y2-4x-16y+-1595
これをQ(x,y)とする. このx,yに20,0を入れると, その左下のピクセルの中央の値, Q(20,0)=-75が得られる.

こういう値を, この図のピクセルについて計算した結果が, ピクセルの下の方の数値である. これが分かると, 正と負のピクセルの境界が, 塗る塗らぬの境界になる.

この図には, すべてのピクセルの値が計算してあるが, 曲線が左上へ単調に伸びると分かっていれば, 上隣りのピクセルの値を計算し, 負なら上へ進み, 正なら左へ進めば良い. すなわち, 今黒丸の点にいて, 上のピクセルが-75なので, 赤線のように境界を上に延ばす. その上も-43なので, 上へ延ばす. その上は21だから左へ行く. その上は-131だから上へ. というように進むと, 左上へ単調に進む第1象限の部分の境界が得られる.

ところで, 一般的な円錐曲線の式Q(x,y)=ax2+bxy+cy2+dx+ey+fの順次の計算は, Qx(x,y)=2ax+by+d, Qy(x,y)=bx+2cy+eを保持していると, 簡単に求まるということを見つけた知恵者がいて, これを3レジスタ法という. それを使ったアルゴリズムがTAOCPにあるが, 例によってgoto文だらけなので, Scheme風に書いたプログラムが以下である. 関数定義の後のTと番号のコメントは, TAOCPのアルゴリズムTの番号である.

(define (algorithm713t x x1 y y1 a b c d e f)
(define (q x y) (+ (* a x x) (* b x y)
(* c y y) (* d x) (* e y) f))
(define (qx x y) (+ (* 2 a x) (* b y) d))
(define (qy x y) (+ (* b x) (* 2 c y) e))
(let ((qreg 0) (rreg 0) (sreg 0))

(call-with-current-continuation
(lambda (exit)
(define (left) (display "left\n")
(bit-string-xor!
(list-ref hs (+ y 11)) (- xmax x)))
(define (right) (display "right\n")
(bit-string-xor!
(list-ref hs (+ y 11)) (- xmax (+ x 1))))
(define (up) (display "up\n"))
(define (down) (display "down\n"))
(define (initset x y a c)
(set! qreg (q x y)) (set! rreg (+ (qx x y) a))
(set! sreg (+ (qy x y) c)))
(define (update rs ab bc)
(set! qreg (+ qreg rs)) (set! rreg (+ rreg ab))
(set! sreg (+ sreg bc)))

(define (hfinish) ;T10
(cond ((< x x1) (right) (set! x (+ x 1)) (hfinish))
((> x x1) (left) (set! x (- x 1)) (hfinish))
(else (exit 'ok))))
(define (vfinish) ;T11
(cond ((< y y1) (up) (set! y (+ y 1)) (vfinish))
((> y y1) (down) (set! y (- y 1)) (vfinish))
(else (exit 'ok))))

(define (moveup) (up) (set! y (+ y 1)) ;T6
(if (= y y1) (hfinish) (update sreg b (* 2 c))))
(define (movedown) (down) (set! y (- y 1)) ;T7
(if (= y y1) (hfinish)
(update (- sreg) (- b) (- (* 2 c)))))
(define (moveleft) (left) (set! x (- x 1)) ;T8
(if (= x x1) (vfinish)
(update (- rreg) (- (* 2 a)) (- b))))
(define (moveright) (right) (set! x (+ x 1)) ;T9
(if (= x x1) (vfinish) (update rreg (* 2 a) b)))
(define (rightup) ;T2
(if (< qreg 0) (moveright) (moveup)) (rightup))
(define (downright) ;T3
(if (< qreg 0) (movedown) (moveright)) (downright))
(define (upleft) ;T4
(if (< qreg 0) (moveup) (moveleft)) (upleft))
(define (leftdown) ;T5
(if (< qreg 0) (moveleft) (movedown)) (leftdown))

(if (= x x1) (vfinish))
(if (= y y1) (hfinish))
(if (< x x1)
(if (< y y1)
(begin (initset (+ x 1) (+ y 1) a c) (rightup))
(begin (initset (+ x 1) y a (- c)) (downright)))
(if (< y y1)
(begin (initset x (+ y 1) (- a) c) (upleft))
(begin (initset x y (- a) (- c)) (leftdown))))
))))

こう定義してから, 順次の象限について

(algorithm713t 20 0 0 10 4 0 16 -4 -16 -1595)
(algorithm713t 0 -20 10 0 4 0 16 -4 -16 -1595)
(algorithm713t -20 0 0 -10 4 0 16 -4 -16 -1595)
(algorithm713t 0 20 -10 0 4 0 16 -4 -16 -1595)

のように呼ぶと, 下のような境界が得られる.



しかし, 境界だけでは塗り潰したことにならない. 塗り潰しの実装はこのようにする. 境界の横線の真上のピクセルを1に, それ以外を0のビット列の配列hs[-11..10], bs[-11..10]を用意する. 私流のプログラムでは,

(define hs
(map (lambda (x) (make-bit-string 42 #f)) (a2b -11 11)))
(define bs
(map (lambda (x) (make-bit-string 42 #f)) (a2b -11 11)))

これはMIT Schemeにある長さ42ビットのbit-stringで, 初期値はオール0である. リストの長さは22だ.

上のプログラムの, 下請け関数leftとrightのところは,

(define (left) (display "left\n")
(bit-string-xor! (list-ref hs (+ y 11)) (- xmax x)))
(define (right) (display "right\n")
(bit-string-xor! (list-ref hs (+ y 11)) (- xmax (+ x 1))))

となっていて, 横向きの境界に対応するビットを0から1にしている. その結果, 1周すると, hsとして(最下行がリストの先頭)

#*000000000000000111111111111000000000000000
#*000000000011111000000000000111110000000000
#*000000001100000000000000000000001100000000
#*000000110000000000000000000000000011000000
#*000011000000000000000000000000000000110000
#*000100000000000000000000000000000000001000
#*001000000000000000000000000000000000000100
#*000000000000000000000000000000000000000000
#*010000000000000000000000000000000000000010
#*000000000000000000000000000000000000000000
#*000000000000000000000000000000000000000000
#*000000000000000000000000000000000000000000
#*010000000000000000000000000000000000000010
#*000000000000000000000000000000000000000000
#*001000000000000000000000000000000000000100
#*000100000000000000000000000000000000001000
#*000011000000000000000000000000000000110000
#*000000110000000000000000000000000011000000
#*000000001100000000000000000000001100000000
#*000000000011111000000000000111110000000000
#*000000000000000111111111111000000000000000
#*000000000000000000000000000000000000000000

のようなビット列が得られる. hsが出来たら,

(do ((i 1 (+ i 1))) ((= i 22))
(list-set! bs i (bit-string-xor (list-ref bs (- i 1))
(list-ref hs i))))

のプログラムで, bsが作れる. bsはこういう値である.

#*000000000000000000000000000000000000000000
#*000000000000000111111111111000000000000000
#*000000000011111111111111111111110000000000
#*000000001111111111111111111111111100000000
#*000000111111111111111111111111111111000000
#*000011111111111111111111111111111111110000
#*000111111111111111111111111111111111111000
#*001111111111111111111111111111111111111100
#*001111111111111111111111111111111111111100
#*011111111111111111111111111111111111111110
#*011111111111111111111111111111111111111110
#*011111111111111111111111111111111111111110
#*011111111111111111111111111111111111111110
#*001111111111111111111111111111111111111100
#*001111111111111111111111111111111111111100
#*000111111111111111111111111111111111111000
#*000011111111111111111111111111111111110000
#*000000111111111111111111111111111111000000
#*000000001111111111111111111111111100000000
#*000000000011111111111111111111110000000000
#*000000000000000111111111111000000000000000
#*000000000000000000000000000000000000000000

タイプの文字の縦横比は1:1でなく, これは正しい形ではない. 再びMIT Schemeの機能graphicsを利用すると,

(define mydevice (make-graphics-device 'x))
(graphics-set-coordinate-limits mydevice -24 -24 24 24)
(do ((i 0 (+ i 1))) ((= i 22))
(let ((b (list-ref bs i)))
(do ((j 0 (+ j 1))) ((= j 42))
(if (bit-string-ref b j)
(graphics-operation mydevice 'fill-circle
(- 21 j) (- i 11) 0.5)))))

によって, 次のようなパターンが得られる.

2011年7月9日土曜日

多面体描画道楽

Archimedesに興味をもって, その多面体を描いてきた. 今回はその総括である. この多面体は13種ある. まとめると以下の通り.

ます, 英語名と日本語名を並べる. 次の行は(pi npi)のリストで, 正pi角形の面がnpi枚あることを示す. 多面体屋なら, この情報から稜の数と頂点の数は計算できるので, その情報をここには記載しない. その次は各頂点について, 何角形が集まっているかを示すリストである. これがこの立方体の実在正を示すキューになる.

日付がある項は, その日のこのブログに絵があったことを示す.

a. truncated tetrahedron 切頭四面体
((3 4) (6 4)) (3 6 6)
2008年10月29日

b. cub octahedron 立方 八面体
((3 8) (4 6)) (3 4 3 4)

c. truncated octahedron 切頭八面体
(4 6) (6 8)) (4 6 6)
2008年10月29日

d. truncated cube 切頭立方体
((3 8) (8 6)) (3 8 8)

e. rhomb cub octahedron 斜方立方 八面体
((3 8) (4 18)) (3 4 4 4)

f. truncated cub octahedron 切頭立方 八面体
((4 12) (6 8) (8 6)) (4 6 8)

g. icosi dodecahedron 二十 十二面体
((3 20) (5 12)) (3 5 3 5)

h. truncated icosahedron 切頭二十面体
((5 12) (6 20)) (5 6 6)
2008年10月29日

i. truncated dodecahedron 切頭十二面体
((3 20) (10 12)) (3 10 10)

j. snub cube 変形立方体
((3 32) (4 6)) (3 3 3 3 5)
2011年6月30日

k. rhomb icosi dodecahedron 斜方二十 十二面体
((3 20) (4 30) (5 12)) (3 4 5 4)
2011年6月19日

l. truncated icosi dodecahedron 切頭二十 十二面体
((4 30) (6 20) (10 12)) (4 6 8)
2011年6月29日

m. snub dodecahedron 変形十二面体
((3 80) (5 12)) (3 3 3 3 5)
2011年7月7日

それ以外のを以下に示す. 描いた時が違うので, 描画法がばらばらだが, ご容赦を. また時間のある時に揃えることもあろう.



立方 八面体

切頭立方体


斜方立方八面体


切頭立方八面体


二十 十二面体


切頭十二面体


ところで私はこれらの立体の頂点の座標を計算し, PostScriptでプログラムして描いただけだが, 東京理科大学 近代科学資料館には菱田為吉氏による, 木製の多面体模型がある. 私は資料館に行くたびに, うっとりと眺めてくる.

Platonの5個の正多面体, Archimedesの13個の多面体は, 立体マニアの興味を引き続けてきた. 私もそれに取り込まれた1人である.

2011年7月7日木曜日

多面体描画道楽

Archimedesの多面体の最後は, snubdodecahedron, 日本語では変形正十二面体という.

ものの本によると, この立体は, 三角形が80, 五角形が12で構成される. 従って稜は(3×80+5×12)/2=150, 頂点は150+2-(80+12)=60である.

正十二面体は, 正五角形の面が12, 頂点はHamilton巡礼で良く知られた20, 稜(辺)はEulerの式から12+20-2=30あった. 従って, 変形正十二面体では, 正五角形は正十二面体の面に対応し, 三角形は頂点+2×稜である.

さて, 下の図を見て欲しい. 大きい正五角形が3つ描いてある. 左の上と下は, x軸の方から見て正面になるものだ. 右の寝そべったのは, y軸方向から見えるものだ.



それぞれの正五角形の中に, 適当に縮小した正五角形を描き, それをθだけ傾ける. 縮小しただけでは, 斜方正十二面体になる. 今回は傾けるのが味噌だ. 縮小したことで 元は3つの正五角形が1点に集まっていたものが, 図のE, H, Fのように分かれ, 三角形EHFが出来る.

また元は1つの辺だったものが, AEとGFに分かれる. 傾けたため, AとFが近づき, それを結ぶと, 三角形AFGと三角形FAEが図のように出来る.

つまり1つの頂点が1つの三角形, 1つの辺が2つの三角形になるから, 前述のように20+30*2=80の三角形になる.

従って, この立体の図を描くためには, 赤で示した線分の長さが等しくなるように, 縮小比と回転角を決めなければならない.

正面上の辺AEを持つ正五角形の各頂点の立体座標が分かれば, 下の辺FGを持つ正五角形の各頂点の立体座標は, 上の座標をx軸について, 180度回転すれば得られるということから始まり, すべての面の頂点の座標はなんとか軸対称回転で計算出来, 思い通りの変形正十二面体の図が得られるはずである.

いつものように, 1辺が2の正五角形で出来た正十二面体で計算する. 正五角形の中心までの高さは, tan 54°=1.3763819204711734; 上の頂点までの高さは, tan72°=3.0776835371752527; 半径はこの差だから 1.7013016167040793. その中に半径rに内接する正五角形を作る.

その中心から見た頂点の座標をまず計算する. 72n+36°の正弦と余弦をsn0やcs0のように書くことにする.

rとθが与えられると, 以下のプログラムは, 3次元に変換し, 各点のx,y,z座標を計算する. うっとうしいが全部書くと



これらの点から, AF, FE, EH, HFの距離とAEの距離の差の絶対値の和を最小にするrとθを決めたい. こんな式は, これ以上計算する気にならないので, 今回は山登り法で最適値を探すようにした.

とりあえず, rを0.8, 0.85, ... 1.25, thetaを0, 0.5, ...0.45と変え, この関数の値をプロットすると, この範囲に最小値があるらしい.



大体r=0.95, θ=0.21 radianあたりが解らしい. PostScriptで描画するから, この程度の値で充分である.



今回の描画プログラムは, 見えない面の破線は, 一度しか描かないようにしているから, 破線がきれいに見えている.

2011年7月3日日曜日

八方睨みの猫

ご近所の知友 金子和夫氏の個展があった. 鉛筆画の「八方睨みの猫」が評判である. チラシからその一部をスキャンさせていただいた. この猫ちゃんには, 金子家で会ったことがある. 可愛い猫だ.



ところで八方睨みとは, この猫をどの方向から見ても, 猫は見られている方を向いているように見えるということである. このチラシを, 右左に傾けても, 上下から眺めても, 確かに視線はこちらを向いている.

実はこの猫だけでなく, 多くの肖像画の目付きも, 大体はこうなっている.

歩きながら月をみると, 歩くにつれて, いつまでも月が付けて来るように, 絵の前を通り過ぎても, 肖像の眼の視線はずーっと自分を追ってくる. 私は若い頃は, これを不思議に思っていた. また, それについて, おそらく黒目が眼の中央にあるからだろうと想像してた.

大学院生の頃, 研究室でこれが話題になったことがあり, 高橋秀俊先生は「黒目が真ん中だから」とこともなげにいわれ, 私としては, 決着がついている.

この猫の黒目は, 上下左右の真ん中にある. 従って四方八方を睨むことになる.

私は, ご存じのようにPostScriptで絵を描くのが大好き人間だ. で, さっそくやってみた. それぞれの絵では, 上から黒目が右より, 中央, 左よりに描いてある. やはり中央のが八方睨みに見える.



横方向から見ても, (つまり横方向を縮小しても)



のようになろう. 真昼の猫の眼のように, 細くなっても同じだろうか.

2011年7月2日土曜日

再帰曲線

私が昭和13年4月に出会った算術の教科書の表紙の再帰曲線の続きである.

収束点の座標が1,1と分かったからには, さらに直観的でエレガントな求め方があるに違いないと思う.

次のように考えて見た.




A点から上向きに出発する. 4歩進みB点に至る. ここは次に下向きに出発する点である. ABの直線を赤のように引く. Bから4歩進むと, 先ほどとは上下左右が入れ替わり, C点に至るが, これは赤線の上に来るはずである. 従って, 4歩毎の点は, 右上に行ったり, 左下へ行ったりするが, 赤線の上にある. つまり, 収束するのは赤線の上である.

上向きに進み終ったD点から, 同じように考える. 4歩進むと下向きに進み終ったE点に至る. DEに青で直線を引く. Eから4歩進んだF点も同じように青線上にあるはずだ. 従って, 収束点は青線上にある.

赤線はy=x, 青線はy=1だから, 交点は1,1だ.

Gorge Polyaの「いかにして問題を解くか」には, 問題を解いた後で, もう一度振り返れと書いてある. もっとうまい解法が見つかるかも知れないからである.

とりあえずは数値計算で遮二無二解いたとしても, その後, 今回のような解法が見つかると, やはり嬉しい.

2011年7月1日金曜日

再帰曲線

はるか昔のことを思い出した. 小学校に入学したら, 算術という科目があった. (その後しばらくして, 算数と名前が変った.) その教科書の表紙に面白い図形があったのを鮮明に覚えている. 少しずつ小さくなった直角二等辺三角形が繋がっているのが見える.



(教科書の絵はウェブページwww-cc.gakushuin.ac.jp/~851051/maed/09sakurai.pdfにもあった.)

これをいつまでも続けていくとどうなるかというのが, その図形を見たときのとっさの疑問であった.

70余年を経て, 計算してみた.



これは上に伸びる三角形の列の外側の線を描いたものだ. 最初の二等辺の長さを1とする. 真上に1だけ伸びると, 45°右に折れ, √(1/2)だけ伸びるという操作を繰り返す. 8回すすむと, 次はまた真上に進むから, ここで1サイクル終了したとして, この座標を計算すると,

x座標は 0+0.5+0.5+0.25+0-0.125-0.125-0.0625=0.9375
y座標は 1+0.5+0-0.25-0.25-0.125+0-0.0625=0.9375

である. 最初に1伸びたのが, 1サイクル終ると, 次は1/16だけ真上に伸びるから, 次のサイクルの終りの座標は, xもyも 0.9375+0.9375/16 だ. さらに次はこれに0.9375/162を足すことになるから, 初項が0.9375で公比が1/16の無限級数を計算することになる.

0.9375/(1-1/16)

だけれど, 0.9375が1-1/16だったから, この値は1だ. (上の図の赤線が1,1を示す.)

なーんだ, という結論だが, やっとせいせいした.