数学サイト
http://blog.livedoor.jp/mazra627/
から
TV「たけしのコマ大数学科」より
第156回「ダイアゴナル」
 
問題1:
 
1辺の長さ1の正方形のタイル800枚を隙間なく並べて、
縦25、横32の長方形を作ります。
この長方形の対角線1本が通過するタイルの枚数を求めてください。
 
さらに一般的に
問題2:
 
1辺の長さ1の正方形のタイルを隙間なく並べて、
縦m、横nの長方形を作ります。(整数mとnは互いに素)
この長方形の対角線1本が通過するタイルの枚数を求めてください。
 
問題3:
 
1辺の長さ1の正方形のタイルを隙間なく並べて、
縦m、横nの長方形を作ります。(mとnは整数)
mとnの最大公約数をGとする。
この長方形の対角線1本が通過するタイルの枚数を求めてください。
 
 
まず図1のように小さい長方形を考えてみる。
 
イメージ 1
 
図1の黒い線は、横4:縦3の長方形の対角線である。
4と3は互いに素である(公約数を持たない)ので、
長方形の対角線は格子点(正方形の頂点)を通らない。
対角線は長方形内の横の線2本と、縦の線3本と交わる。
交点数は2+3=5個である。
左下から対角線が通過する正方形タイルの数は、
最初の1個+交点を通るとき1つずつ増える。――――――――(1)
∴ 通過するタイルの数=1+交点数=6枚となる。――――(2)
 
図1の赤い線は、横4:縦2の長方形の対角線である。
4と2は最大公約数が2なので、2:1の長方形が2つ並んでいる。
2:1の長方形において対角線は横の線0本と縦の線1本と交わる。
長方形内の交点数は1個である。
4:2の長方形の対角線と格子線との交点数は、
1×2+格子点1個=3個となる。
最初の1個+交点を通るとき1つずつ増えることに変わりはなく、――(1)
∴ 通過するタイルの数=1+交点数=4枚となる。――――(3)
また、(2:1の長方形のタイル2枚)
      × 最大公約数2=4枚とも言える。―――――(4)
 
これらのことを踏まえて、
 
問題2の解答例として:
mとnは互いに素であるから、格子点を通らず、
横の線が(m-1)本、縦の線が(n-1)本だから、
長方形内の交点数は、(m-1)+(n-1)
通過するタイルの数は、(1)と同様に、
最初の1個+交点を通るとき1つずつ増えるので、
 1+(m-1)+(n-1)=m+n-1 となる。---(問題2答え)
 
したがって
 
問題1の解答として:
25=5^2 と 32=2^5 は互いに素であるから、
通過するタイルの数は、25+32-1=56枚 ----(問題1答え)
 
問題3の解答例:
イメージ 2

最大公約数Gなので、m=pG,n=qG と表すことが出来る。
そして、p,q は、互いに素である。
p:q の長方形内の交点数は、(p-1)+(q-1)
m:n の長方形の対角線上に、p:q の長方形G個を並べた形となる。
(3)の考え方では、m:n の長方形内の交点数は
((p-1)+(q-1))×G
   +(通過する長方形内の格子点数が(G-1))
=m+n-2G+G-1=m+n-G-1
∴ m:n の長方形において通過するタイルの数は(1)より、
 1を足して、m+n-G ----(問題3の答え?)
(4)の考え方では、
通過するタイルの数は、
 (p+q-1)×G=m+n-G ----(問題3の答え?)
 
※ (3)(4)は、4+2-2=4 ということになる。
また
問題1と違って、例えば
縦25:横35の長方形の場合は、最大公約数5だから、
通過するタイルの数は、25+35-5=55 となる・・と思う。
 
(2011年11月28日、同日若干修正)
-------------------------------------------------
なんか、今までに比べると比較的やさしい問題を、
やたら面倒くさく考えてしまった気もします・・・
 
目も頭も冴えているわけでもなく
夜の狭い洞窟の奥の灯りの下に
眠れない時間を過ごしている
苔のようにへばりついて
 
私はこの程度ということで、
・・・一応書いたので載せときます。失礼。