2012年6月18日月曜日

Polyaの問題

彼の名著 How to Solve It に演習問題が20ある. その19番はこうだ.

The side of a regular hexagon is of length n (n is an integer). By equidistant parallels to its sides the hexagon is divided into T equilateral triangles each of which has sides of length 1. Let V denote the number of vertices appearing in this division, and L the number of boundary lines of length 1. (A boundary line belongs to one or two triangles, a vertex to two or more triangles.) When n = 1, which is the simplest case, T = 6, V = 7, L = 12. Consider the general case and express T, V, and L in terms of n. (Guessing is good, proving is better.)


とりあえずn=1,2,3の絵を描いてみる。



こういう図は, 幾何学と同じで正確に描くことが重要である. 幸いPostScriptで奇麗に描けた.

さて, 大きい図で全部数えるのは面倒だし, 間違えの元だ. うまい具合に中の方は赤で囲んだ左隣りと同じだから, 一番外の皮の部分だけに注目する. またそれも6回対称だから, 1/6だけ数えればよい.

n=3の図で数えると, T は5個増えた. n=2では3増えたから,  ΔT(n)=2n -1であろう. 青い点をつけた頂点V は3増えたから, これはΔV(n)=nだ. Lは8だからΔL(n)=3n -1.

従って1辺がnの時の総和はn=0の時の値に, これらの式の6倍を, nを1からnまでの和にし, 定数はnを掛けて足せばよい.

だから
T(n) = 6·2n(n+1)/2-6n = 6n2+6n-6n = 6n2.

V(n) = 6n(n+1)/2+1 = 3n2+3n+1.

L(n)=6·3n(n+1)/2-6n = 9n2+9n-6n = 9n2+3n.


簡単すぎた. 食後の一休みにはちょうどよいかも. PostScriptの絵を描いたり, HTMLで式を書いたりで, 結構時間は掛かったが.

2012年6月15日金曜日

ハノイの塔

Winning Waysに情報科学標準問題のハノイの塔の話題があった.

ハノイの塔の円板の動かし方は誰でも知っているが, 任意の回数の手順の後, 各円板のある杭を示すアルゴリズムについてである.

円板4枚でまずやってみる. +-+-+線の上は3本の杭に円板が乗っている様子で円板を8,4,2,1とする.
1
2     2                                     1     1
4     4     4     4   1     1 1     1 2     2     2
8     8 1   8 1 2 8   2 8 4 2 8 4 2 8 4   8 4     4 8
+-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
 0000  0001  0021  0022  0122  0120  0110  0111  2111

                                        1
                                  2     2
  2 1     1 1     1   4     4     4     4
  4 8 2 4 8 2 4 8 2   8 2 1 8   1 8     8
+-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+
 2112  2102  2100  2200  2201  2221  2222

+の杭を左から0,1,2とし, 各円板がどの杭にいるかを線の下に書いた. 当然円板8421の順だ.

さて, Winning Waysによるとn回目の後の様子は, nを二進法に展開し, 1,2,4,8,...の各ビットが1ならそれぞれ, 1, 21, 122, 2111に置き換え, 各桁を3を法として足す.

7回目で計算すると7=(111)2だから
0001
0021
0122
----
0111

となって円板8が杭0, 残りは杭1にあることが分かる.

schemeでプログラムを書くと
(define (mod3+ . d) (modulo (apply + d) 3))

(define (foo l)
(if (null? (car l)) '()
   (cons (apply mod3+ (map car l)) (foo (map cdr l)))))

(define (han n)
 (let ((b (n2bs n 4)))
  (foo (map (lambda (w p)
   (if (= p 1) w '(0 0 0 0)))
    '((2 1 1 1) (0 1 2 2) (0 0 2 1) (0 0 0 1)) b))))

各移動後の様子の計算の結果が
((0 0 0 0) (0 0 0 1) (0 0 2 1) (0 0 2 2) (0 1 2 2) (0 1 2 0)
 (0 1 1 0) (0 1 1 1) (2 1 1 1) (2 1 1 2) (2 1 0 2) (2 1 0 0)
 (2 2 0 0) (2 2 0 1) (2 2 2 1) (2 2 2 2))

となり上のと一致する.

ではなぜこれでよいか.

円板の移動はよく知られているように,
1は1,3,5,...回目に0→1→2→0→1→2→...と動き, 2は2,6,10,...回目に逆回りに動く.



そこで各円板が各移動後にいる杭を書くことが出来る.

  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15

1 0  1  1  2  2  0  0  1  1  2  2  0  0  1  1  2
2 0  0  2  2  2  2  1  1  1  1  0  0  0  0  2  2
4 0  0  0  0  1  1  1  1  1  1  1  1  2  2  2  2
8 0  0  0  0  0  0  0  0  2  2  2  2  2  2  2  2


1回の時は二進表記は 0 0 0 1 なので, 上の1の列 0 0 0 1 を使う. 2回は 0 0 1 0 なので2の列 0 0 2 1 を使うことにする. 3回は1の列と2の列から3の列が得られるかと思うが, 単に足せば 0 0 2 2 となりよさそうだ. この伝でいろいろな列を3を法として足してみるといつもうまく行くことが分かる.

場当たり的なのがうまくいったので, 本質的なことを考えると, 8の円板が動く前と後との1から4までの円板の動きは, 前が 0 0 0 から 1 1 1 への移動, 後が 1 1 1 から 2 2 2 への移動だが, 移動のパターンは同じである. 最初 0 0 0 0 から8の移動直前の 0 1 1 1 までと, 8の移動後の 2 1 1 1 から最後の 2 2 2 2 までは, 結局 2 1 1 1 に 0 1 1 1 を足すに他ならない. それが4や2の円板でも同じなのだから当然なわけだ.

2012年6月14日木曜日

曜日の計算

2012年6月13日の私のブログ「復活祭公式」にある, Winning Waysが「3月28日 Doomsday(最後の審判の日)」という日の曜日は実はなかなか重要である.

曜日としては3月28日は3月0日と同じだが, この曜日は4月4日, 6月6日, 8月8日, 10月10日, 12月12日の曜日と一致する. (これらを目印の日といおう.) 4月から後については, 偶数4≤m≤10のm月m日と(m+2)月(m+2)日の間隔は, 大の月が1回と小の月が1回と2日あるから31+30+2=63で, これが7で整除出来るから同じなわけだ.

5月以降の奇数月については, 大の月m∈{5,7}ではm月(m+4)日, 小の月m∈{9,11}ではm月(m-4)日が同じ曜日になる. つまり大の月のm月m日と次の(m+1)月(m+1)日の間隔は31+1=32日, 従ってm月(m+4)日から後の目印の日までの間隔は4日減って28日になる. 小の月のm月m日と(m+1)月(m+1)日の間隔は30+1=31日, m月(m-4)日から後の目印の日までの間隔は4日増えて35日になり, どちらも7で整除できる.  ブラボー!

このように4を足したり引いたりするより, 4ヶ月離れた5月9日と9月5日, 7月11日と11月7日が目印の日と私は覚えているが, 次のパラグラフの1月のことを考えると+4日という情報は覚えておく価値がある.

さてその4月より前の月はどうか. 3月は最初に書いたように0日が目印の日だ. 3月が31日あり, 4月4日までは35日あるから確かに. もちろん3月は大の月だから, 3月(3+4)日が目印の日になる, 1月と2月については前年の13月と14月と思えはよいが, 14月14日は途中に大の月が2回あるから, 上の偶数月とは同じ関係にはならない. が, 上記のような理由を理解していれば2月は14-1=13日が前年の目印の曜日になる. また1月は大の月だから13-1+4と1月16日になる.

昨年の目印の曜日は月曜であった. 今年のカレンダーを見直すと, 1月16日, 2月13日は, 月曜で当たりだ. 今年は来年の2月まで水曜, 水曜と唱えていれば, 各月の曜日の計算はお茶の子である.

2012年6月13日水曜日

復活祭公式

復活祭からずいぶんたって, いまや聖ヨハネ節が近い. 気が抜けた話題だが, Winning Waysを眺めていたら, そこにも復活祭公式があった. 存外簡単である.

復活祭は春分満月の後の日曜であり, そこで春分満月の公式が重要である.

本書によると, 春分満月の日は

(4月19日=3月50日)-(11G+C)mod 30

だが, それが4月19日なら4月18日にする; 4月18日でG>=12なら4月17日にする.
ただし黄金数Gは
G=(年 mod 19)+1
世紀項Cは
19xx, 20xx, 21xx年は-6.

2012年で計算すると

(+ (modulo 2012 19) 1) => 18   ;G
(modulo (+ (* 11 18) -6) 30) => 12

従って19-12で4月7日になる.

次に本書によると3月28日をDoomsday(最後の審判の日)といい, 今年は水曜であった. すると3月25日が日曜, 4月1日が日曜, 4月8日が日曜で, 復活祭はまだ記憶にあるように4月8日であった.

Doomsdayの曜日は, (世紀初頭のDoomsday+その後の年に12が含まれる数+その余りの数+その余りに4が含まれる数)mod 7と計算でき, 21世紀初頭(2000年)は火曜であった.

従って2012年は

(let ((y 12))
(+ (quotient y 12) (modulo y 12) (quotient (modulo y 12) 4)))
=> 1

で水曜だ.

Gregorian暦の曜日は400年で一周するから, 世紀初頭の曜日は2000年の火曜から始まり, 2100年日曜, 2200年金曜, 2300年水曜で循環する. (100年に閏年が24回だと5日進み, 25回だと6日進む. 2000年3月28日は閏日を過ぎているから, 2100年3月28日までは25回だと6日進む. 2000年3月28日は閏日を過ぎているから, 2100年3月28日までは5日進んで, 水木金土日, 次も月火水木金, 次も土日月火水, 最後が6日進んで木金土日月火になるわけだ.)

我々は当面火曜を覚えておけば暮らしていける.

2012年6月2日土曜日

Life Game

前回のこのブログでは, キックバックを利用した希薄銃の実現法を述べた. その少し先にConwayはグライダーの列から連続する3機のグライダーを消滅させる方法を書いている.

120クロック毎に打ち出されるグライダーの列があるとする.

(i)   1機目のグライダーが別のグライダーでキックバックされ, 元の方向へ戻る.
(ii)  2機目が戻ってきた1機目と正面衝突し, ブロックを生じる.
(iii) 3機目がこのブロックに衝突して消える.

これを読んでなるほどと思ってもよいが, やはりシミュレートしてみたい.



この図はグライダーの列が右上から左下へ飛んでいるところで,先頭のaがまさにキッバックされる位置にいる. 後続のbとcは120クロック離れている.dはキックバックを仕掛けるグライダーで, 左上から右下へ飛んでいる. その先にイーターEを置く.

この時点のクロックを0としよう.

次の図は, クロック8で, キックバックが終わり,1機目(a)が向きを反転したところである.



この2つの図の間の様子は前回のブログのキックバックの遷移図の0から8である.

その後しばらくしてクロック60では1機目(a)と2機目(b)があわや衝突寸前になる.



クロック66でこの2機はブロックになる.



次はクロック172で, 3機目(c)がブロックに迫る.



クロック176ではブロックと機体の破片だけになり, 次のクロックでは何もなくなる.



この図で右上に見えるeはちょうどキックバックのグライダーが来るのでなければ, 消えることなく左下へ進む.

これで安心して先が読める. この機構を利用し, グライダー列による情報を複製する話にるのだが,  それも結構複雑で, Life Gameは万能とはいえ素子があまり単純な故であろう.

うまく動くシミュレーションを眺めるのは楽しい.