パズルの国のアリス

フレームと筋交い(解答)

 筋交いの入れ方の1つを見つけるのは簡単だろう。例えば,最左列と最下行のマス全部に筋交いを入れれば安定する(3×4の場合を下図に示す)。

 しかし,筋交いの入れ方はそれ以外にもあり,例えば縦横のサイズの差が1ならば,対角線上のマス2列すべてに入れてもよい(下図)。

 このどちらの場合も,筋交いの数はmn−1と表せる。また,1×nのフレームの場合,全部に筋交いを入れる必要があるのは明らかだから,このmn−1が筋交いの数として必要かつ十分であることが予想される。そしてそれは実際正しい。

 もちろん,どこに筋交いを入れてもよいわけではないが,実は,その場所を定めるのも簡単である。最初のうちは好きなところに筋交いを入れていけばよい。するとだんだんと正方形の形を保つマス目が増えていくから,まだ正方形になっていない場所があれば,そういうところを1つ選んで筋交いを入れる。こうして全マス目が正方形を保つようになったら終了である。しかし,このときにちょうど mn−1個の筋交いが入っているというのは納得しがたいかもしれない。

 その説明にはグラフ理論を用いるのがよいのだが,その前に,筋交いを入れるというのがどういうことなのか分析しておこう。下図左は何も筋交いの入っていないフレームであるが,まったくでたらめというわけではない。赤の辺はいずれも平行である。2本ずつで平行四辺形(ひし形)の対辺を構成しているのだからこれは当然だ。同様に青の辺もすべて平行である。さて,右上のマス目に筋交いを入れるとどうなるか考えてみよう(下図右)。この結果,赤の辺と青の辺が垂直になる。ポイントは,筋交いを入れた当のマス目の辺だけでなく,どの赤の辺と青の辺も垂直になるということだ。

 mnのフレームの場合を考えると,まず,(上の赤の辺のように)横方向に n+1本並ぶ平行辺のグループがm個ある。それらのグループを上からG1,G2,…,Gmと名づけよう。同様に,(青の辺のように)縦方向にm+1本並ぶ平行辺のグループがn個あるので,左からH1,H2, …,Hnと名づけよう。上からi番目,左からj番目のマス目に筋交いを入れるということは,Giに属する辺とHjに属する辺とを垂直にするということに他ならない。

 このあたりでグラフ理論に登場願おう。紙の左側にグループG1,G2,…,Gmを表すm個の点を描く。右側にはグループH1, H2, …,Hnを表すn個の点を描く。この左右の点を辺でいくつか結んだグラフを考え,そのグラフでGiHjが結ばれているとき,上からi番目,左からj番目のマス目に筋交いを入れる。するとGiの辺とHjの辺とは直交する。さて,このmn個の点からなるグラフが連結(どの2点をとっても,何本かの線をたどることでその2点がつながっている)としよう。このときどのGiの辺とどのHjの辺も垂直になることは明らかであろう。従ってフレームのマス目はどれも正方形でありフレームは安定する。逆にグラフが非連結とすれば,異なる連結成分に属するグループ内の辺同士はその交叉角に関して何の制約も受けない。従ってフレームは不安定になる。mn個の点を結んで連結にするために必要かつ十分な辺の数は,もちろんmn−1である。

 最初の3×4のフレームの筋交いの例について,このグラフを描くと下図のようになり,これらはもちろん連結である。

参考にした本
Mathematical Puzzles:A Connoisseur's Collection(2004),
Mathematical Mind-Benders(2007) P. Winkler。
邦訳は『とっておきの数学パズル』(2011年),『続・とっておきの数学パズル』(2012年),ピーター・ウィンクラー著,坂井公・ 岩沢宏和・小副川健訳,日本評論社。

問題はこちらです