正方化長方形

Tne New Martin Gardner Mathematical Libraryの2冊目にSquaring the Squareという話題があった. 正方化正方形とでもいおうか. 正方形を相異る正方形で埋め尽す問題である. 同じ正方形で埋め尽すなら22が4とか33が9とかに分割すれば出来るが, 相異るとなると出来るかどうか不明である. 本書によると1936年頃, ケンブリッジ大学の4名の学生が挑戦したらしい.

周囲が正方形なら非常に困難だが, 相異る正方形で長方形を敷き詰めるのは, 比較的容易らしい. 下の図の左がその一例で, 横61, 縦69の長方形が相異る正方形で敷き詰めてある. 正方形の中の数が, 正方形の辺の長さで, 最小のは2と書いてある. こういう図形を正方化長方形(squared rectangle)という.

例えばこの上に61掛ける61の正方形, 横に69掛ける69の正方形を置いても, 正方化長方形になるが, 内部に正方化長方形を持たないものだけを単純正方化長方形ということにする.



目から鱗なのは, これが右のような有向グラフ(Smith Diagram)に変換できることだ. つまり左の図の横線を節点にし, 正方形を弧として描き直すと右の図になる. 弧の値は正方形の辺の長さだが, このグラフの電気回路とみると, 弧の値はこの回路の電流となる. また各線の抵抗を1オームとすると, 弧の値は両端の電圧になる.

このグラフでは, 節点の入力弧は横線の上の正方形の幅の和だし, 出力弧は下の正方形の幅の和なので, 電気回路とすると, 入る電流と出る電流は等しことになる. また例えばAとDの間の電圧はAD直接でも, ABCDと回っても同じである. またこの回路のAへ外から入る電流, Fから外へ出る電流を1とすると, 次のような関係が得られる.



の左の図のように,

電流の出入り

A  a + b = 1
B  c + d = b
C  e + f = c
D  g + h = a + e
E  i = d + f + h
F  1 = g + i

電圧関係

AD a = b + c + e
BE c + f = d
CE e + h = f
DF g = h + i

従って次の係数の連立方程式を解く.

    a  b  c  d  e  f  g  h  i
A   1  1                       1
B     -1  1  1                 0
C        -1     1  1           0
D  -1          -1     1  1     0
E           -1    -1    -1  1  0
F                    -1    -1 -1
AD  1 -1 -1    -1              0
BE        1 -1     1           0
CE              1 -1     1     0
DF                    1 -1 -1  0

(define eq '(
  ( 1  1  0  0  0  0  0  0  0  1)
  ( 0 -1  1  1  0  0  0  0  0  0)
  ( 0  0 -1  0  1  1  0  0  0  0)
  (-1  0  0  0 -1  0  1  1  0  0)
  ( 0  0  0 -1  0 -1  0 -1  1  0)
  ( 0  0  0  0  0  0 -1  0 -1 -1)
  ( 1 -1 -1  0 -1  0  0  0  0  0)
  ( 0  0  1 -1  0  1  0  0  0  0)
  ( 0  0  0  0  1 -1  0  1  0  0)
  ( 0  0  0  0  0  0  1 -1 -1  0)
))

とし, 掃出し法のプログラムを書いて解いてみた. Schemeは分数で計算してくれるので, 最後は(-61/37 -28/37)が残る. つまり-61/37i=-28/37 だからi=(/ -28/37 -61/37) -> 28/61 従ってFから出る電流が1なので, g=33/61となる. 従って上の右の図のように, 33と28が得られる.

右の図はもう少し複雑な回路である.

    a  b  c  d  e  f  g  h  i  j  k  l  m
A   1  1  1                                1
B  -1        1  1                          0
C     -1           1  1                    0
D              -1 -1     1                 0
E           -1                -1 -1    -1 -1
F                    -1     1  1    -1     0
G                       -1 -1     1        0
H        -1                          1  1  0
AD  1 -1        1 -1                       0
AF     1 -1           1             -1     0
BE           1 -1       -1       -1        0
CG                 1 -1  1 -1              0
FE                          1 -1  1        0
HE                             1     1 -1  0

(define eq '(
  ( 1  1  1  0  0  0  0  0  0  0  0  0  0  1)
  (-1  0  0  1  1  0  0  0  0  0  0  0  0  0)
  ( 0 -1  0  0  0  1  1  0  0  0  0  0  0  0)
  ( 0  0  0  0 -1 -1  0  1  0  0  0  0  0  0)
  ( 0  0  0 -1  0  0  0  0  0 -1 -1  0 -1 -1)
  ( 0  0  0  0  0  0 -1  0  1  1  0 -1  0  0)
  ( 0  0  0  0  0  0  0 -1 -1  0  1  0  0  0)
  ( 0  0 -1  0  0  0  0  0  0  0  0  1  1  0)
  ( 1 -1  0  0  1 -1  0  0  0  0  0  0  0  0)
  ( 0  1 -1  0  0  0  1  0  0  0  0 -1  0  0)
  ( 0  0  0  1 -1  0  0 -1  0  0 -1  0  0  0)
  ( 0  0  0  0  0  1 -1  1 -1  0  0  0  0  0)
  ( 0  0  0  0  0  0  0  0  1 -1  1  0  0  0)
  ( 0  0  0  0  0  0  0  0  0  1  0  1 -1  0)
))

掃出した最後が(-336/167 -99/167)となり, (i j k l m)が後から順に(5/112 3/14 19/112 9/112 33/112) と得られる. つまり横幅は112の正方化長方形になったわけだ.

(ウェブでこういうページをみつけた.)