パズルの国のアリス

大工が請け負った タイル貼り工事(解答)

坂井 公(筑波大学) 題字・イラスト:斉藤重之

 ウォーミングアップ問題は簡単だろう。例えば,5cm×8cmのタイルを使って,縦に12枚,横に10枚並べれば60cm×80cmのスペースを埋めることができる。残る部分は60cm×20cmだが,今度は,タイルの向きを90度変えて縦に7枚,横に4枚並べれば,56cm×20cmの部分が埋まる。最後の4cm×20cmの部分は残った2枚のタイルを2等分し,5cm×4cmの4枚にして埋めればよい。切断するタイルを1枚だけにして,同じことができるとは筆者には思えないが,そういうやり方を見つけたり,できないという証明を得たりされた読者は,是非,連絡いただきたい。

 さて,本当に考えていただきたかったのは,タイルをそのまま並べるだけでは60cm×1mのスペースを埋められないという証明だ。この問題のポイントはタイルの寸法のうち8cmの方である。結論をいうと,そういうタイルを並べて覆うことができる長方形領域は,縦か横の一方の長さが8cmの倍数だと断言できるのだ。1mと60cmはどちらも8cmの倍数でないから,問題のスペースは5cm×8cmのタイルだけでは覆えない。

 実は,タイルのもう一方の寸法は重要ではない。だから,それを変えたタイルが色々あっても,問題は解決しない。なるべく一般的な形で,この事実を述べるなら,「ある長方形が様々なサイズの数多くの長方形に分割されたとする。この分割後の長方形のどれをとっても片方の辺長がaの倍数であるとすると,元の長方形の辺長も一方はaの倍数である」ということになる。

 あるいは,縮尺を変えて,aを単位長としてとれば「分割後の長方形のどれをとっても片方の辺が整数長であるとすると,元の長方形の辺も一方は整数長である」と言い換えられる。これが一番わかりやすそうなので,以降は,この形で問題を考えていくことにしよう。

 実は,ちょっと古いが,ワゴンという人がこの問題に着目し,なんと14種類もの証明を集めたという記事を1987年のアメリカ数学月報(The American Mathematical Monthly)に書いている。その記事はWagonとtilingくらいをキーワードとしてインターネット検索すれば簡単に入手できるので,気になる人は参照されたい。また,このコラムの種本に使っている『とっておきの数学パズル』(下記を参照)にもウィンクラーが考えた15番目の証明が載っている。これらの証明の中には似たようなものもあるが,特徴的なものをいくつか拾ってみたい。

 ものの順序として,最初に見いだされたアイデアから始めよう。しかし,これは,大学初年級以上のやや高度な数学を使うので,この種の議論が不得手な読者は,とばしてもらってかまわない。もとの長方形Rの左下の頂点を原点として,通常の平面座標を導入する。そして,複素関数fxy)=e2πi(x+y)=cos(2π(xy))+isin(2π(xy))の2重積分について考察するのだ。RR1R2,…,Rnというn個の長方形に分割されているとすると,各Riの辺の一方は整数長ということから

201301_a_img1

が簡単に示される。従って,Rの上辺をyb,右辺をxaとすると,

201301_a_img2

となるが,この左辺が0であるためにはaまたはbが整数でなければならないということが,やはり簡単に示され,結論が得られる。

 上の式の意味がわかる人は,証明の細部は自分で埋められるだろうから,これ以上の説明は要るまい。関数fを変えることで,もう少し初等的な証明も得られる。しかし,「微積分」にアレルギーがある読者のために,別の証明を紹介しよう。

 各Riの境界線をずらして面積を考えることで別証明が得られる。Riの左右の境界をxaixbiとし,上下の境界をyciydiとしよう。aiが整数ならaiaiと定め,aiが整数でなければaifloor_laifloor_r+1/2と定める(floor_laifloor_rai以下の最大の整数)。bicidiも同様に定め,xaixbiyciydiで囲まれた領域をRiとする。このようにすると,例えばaibiとなって,領域Riが1本の線分に縮退してしまうようなことがありうるがそれはかまわない。重要なのはRiを集めればRの境界に同様な処置を施した領域R’になることだ。Rの右の境界をxaとし,上の境界をybとするとき,abがどちらも整数でなければ,R’の縦横の長さはどちらも奇数/2という形になるから,R’の面積は奇数/4という形になる。一方,Riの横幅が整数だとしたら,左右の境界を上のように移動しても,同じようにずれるだけだから,横幅は変わらない。縦幅はずらし方から整数/2の形になるので,Riの面積も整数/2の形になる。Riの縦幅が整数だとしても同じことであり,Riの面積はやはり整数/2の形になる。整数/2の形の数をいくら足し合わせても奇数/4の形にはならないので,abの一方は整数であることが結論される。

 この「ずらし」のテクニックは,この問題にはとても有効なようだ。ワゴンが挙げた14種の証明の中には,細部は微妙に異なるが,ずらしによるものが他にも2つあった。

 もう一つの代表的なテクニックはグラフを用いるものである。各長方形Riの4頂点の座標を調べ,その座標値がともに整数であればRiの重心とその頂点を路で結んで作られるグラフを考えよう。Riの片方の辺は整数長だということから,その重心と結ばれる頂点の数は,0,2,4のいずれか,すなわち偶数であることが容易にわかる。また,各頂点は,分割前の長方形R自身の4つの頂点を除いてどれも,2個または4個の長方形の頂点になっているので,それと結ばれる重心の数も偶数である。

 Rの左下の頂点(0,0)は左下隅の長方形の重心と結ばれているので,そこを出発点として同じ路を通らないようにグラフ上を旅することを考えよう。いわゆるオイラー路(一筆書き)である。グラフは有限だから,やがて旅は続けられなくなるが,その終点は,オイラー路の基本的な性質より,奇数次の点(奇数本の路が合流している点)か出発点である。奇数次の点はRの頂点しかなく,同じ路を通らない限り出発点に戻ることは不可能だから,終点はRの別の頂点だ。そこの座標は,グラフの定義より,両方とも整数だから,Rの縦横の一方は整数長であることがわかる。

 このようにグラフを利用する証明も何通りもある。ウィンクラーの本にある15番目の証明もこのアプローチの変形といえよう。読者も色々と挑戦されたい。特に,積分,ずらし,グラフのどれとも異なる新しい証明を思いつかれたら連絡してもらえるとうれしい。

参考にした本
Mathematical Puzzles:A Connoisseur's Collection(2004)
Mathematical Mind-Benders(2007) P. Winkler著

問題はこちらです