正方形を異なる正方形に分ける

同義語：完全正方形分割Bouwkampの記号squaring the squareperfect squared square

概要

前提知識: 長方形を正方形に分ける, 平方数, 数列の和と差分

高校での出発点：正方形を正方形で埋める

長方形を正方形に分けるでは、横 $33$、縦 $32$ の長方形や横 $69$、縦 $61$ の長方形が、大きさがすべて違う 9 個の正方形に分けられることを見た。どちらも縦と横がわずかに違う。では、縦と横が等しい長方形、つまり正方形そのものを、大きさがすべて違う正方形に分けることはできるだろうか。
大きさが同じものを許せば、正方形を正方形に分けるのはやさしい。

同じ大きさを許して正方形を分ける

一辺 $2$ の正方形は、一辺 $1$ の正方形 $4$ 個に分けられる。
一辺 $3$ の正方形は、一辺 $2$ の正方形 $1$ 個と一辺 $1$ の正方形 $5$ 個、合わせて $6$ 個に分けられる（図 1）。面積の和は $2^2+5\times1^2=4+5=9=3^2$ である。
一辺 $4$ の正方形は、一辺 $3$ の正方形 $1$ 個と一辺 $1$ の正方形 $7$ 個、合わせて $8$ 個に分けられる（図 2）。面積の和は $3^2+7\times1^2=9+7=16=4^2$ である。
分割の中の正方形を 1 つ選んで、縦横に 2 等分して 4 個に分けると、個数は $3$ 増える。(1)〜(3) の $4$、$6$、$8$ 個から始めて $3$ ずつ増やすと、$6,7,8,9,10,\dots$ と $6$ 以上のどの個数にも分けられる（$6$ 以上の整数は、$6,7,8$ のどれかに $3$ を何回か足した数である）。

一辺 3 の正方形を、一辺 2 の正方形 1 個と一辺 1 の正方形 5 個に分けた図

一辺 4 の正方形を、一辺 3 の正方形 1 個と一辺 1 の正方形 7 個に分けた図

大きさがすべて違う正方形で埋めようとすると、まず面積の和が合わなければならない。面積だけなら、ちょうど合う例がある。

一辺 1 から 24 までの正方形の面積の和

一辺 $1,2,\dots,24$ の $24$ 個の正方形の面積の和は、2 乗の和の公式（数列の和と差分）から
$$ 1^2+2^2+\cdots+24^2=\frac{24\cdot25\cdot49}{6}=4900=70^2 $$
で、一辺 $70$ の正方形の面積に等しい。ところが、この $24$ 個を並べて一辺 $70$ の正方形を作ることはできないことが知られている（Wei26。この記事では証明しない）。面積の和が合うことは、分けられるための必要条件にすぎない。

この記事で答える問いは次の 3 つである。

正方形を、大きさがすべて違う正方形に分けることはできるか。→ thm-sqs-112
分割を数字だけで書き表し、正しいことを確かめるにはどうすればよいか。→ def-sqs-code、lem-sqs-procedure

そのような分割で、いちばん小さい正方形はどこにあるか。→ cor-sqs-smallest

高校の計算	この記事の言葉	大学の言葉
面積の和 $1^2+\cdots+n^2$	分けられるための必要条件	—
上から順に並べて幅を足す	Bouwkamp の記号と並べ方の手順	分割の符号化
辺の長さの足し算が合うか	各段の空きの幅と群の和	平面グラフと電気回路

言葉の準備：完全正方形分割と Bouwkamp の記号

正方形分割、大きさがすべて違うこと、完全長方形は長方形を正方形に分けるの定義のとおりとする。長方形を $R$ とし、次の 3 つの条件（以下、分割の条件という）を満たす有限個の正方形 $Q_1,\dots,Q_n$ を $R$ の正方形分割といったのだった。
(R1) どの $Q_i$ も $R$ に含まれ、$Q_i$ の辺は $R$ の辺に平行である。
(R2) 異なる 2 つの正方形は内部に共通の点をもたない。
(R3) $Q_1,\dots,Q_n$ を合わせると $R$ 全体になる。

完全正方形分割

正方形の正方形分割で、2 個以上の正方形からなり、大きさがすべて違うものを 完全正方形分割（perfect squared square）という。正方形の個数をその分割の個数（位数）という。

完全正方形分割は、長方形を正方形に分けるの完全長方形のうち、外形がたまたま正方形になった特別な場合である。
分割を人に伝えるには、図を送るのがいちばん分かりやすいが、数字だけで伝える方法もある。以下、大きい正方形を一辺 $L$ とし、横の位置 $x$（$0\le x\le L$）と、上の辺から下へ測った深さで点の位置を表す。

Bouwkamp の記号と並べ方の手順

正の整数を並べた群をいくつか順に並べたもの
$$ [a_1,a_2,\dots],\ [b_1,b_2,\dots],\ \dots $$
を Bouwkamp の記号 という。これを次の手順で一辺 $L$ の正方形の中に並べる（以下、手順 (i)〜(iii) という）。
途中の各時点で、それぞれの横の位置 $x$ について、上の辺からどの深さまで正方形で埋まったかを $h(x)$ と書く（最初はどの $x$ でも $h(x)=0$）。$h(x)$ がいちばん小さい値をとる $x$ の範囲のうち、いちばん左にある区間（その値がとぎれずに続く最大の区間）を空きという。空きの左端を $x_0$、幅を $w$、深さを $d$ とする。
(R1) 次の群の数 $c_1,c_2,\dots,c_k$ について、$c_1+c_2+\cdots+c_k=w$ であることを確かめる。等しくなければ、その記号は並べられない。
(R2) 一辺 $c_1,c_2,\dots,c_k$ の正方形を、空きの左端 $x_0$ から左から順に、上の辺を深さ $d$ にそろえて隙間なく並べる。
(R3) すべての群を並べ終えたとき、どの $x$ でも $h(x)=L$ になっていれば、並べ方は完成したという。

言いかえると、群は「上の辺の深さがそろっていて隣り合う正方形の組」で、手順は「いちばん浅く、いちばん左の空きに、次の群を詰める」ことである（BTB11 の問題 10 の答え）。

横 33、縦 32 の長方形の記号を読む

長方形を正方形に分けるの横 $33$、縦 $32$ の分割は、記号 $[18,15],[7,8],[14,4],[10,1],[9]$ で表される（BTB11 の問題 12）。手順どおりに並べてみる。長方形なので、横を $33$、最後の深さを $32$ として手順を使う。
(1) 最初は空きが $0\le x\le33$ の全体で、幅 $33$。$18+15=33$ なので、$18$ と $15$ を上の辺にそろえて並べる。$h$ は $0\le x\le18$ で $18$、$18\le x\le33$ で $15$ になる。
(2) いちばん浅いのは深さ $15$ の $18\le x\le33$ で、幅 $15$。$7+8=15$ なので、$7$ と $8$ を並べる。$h$ は $18\le x\le25$ で $22$、$25\le x\le33$ で $23$ になる。
(3) いちばん浅いのは深さ $18$ の $0\le x\le18$ で、幅 $18$。$14+4=18$ なので、$14$ と $4$ を並べる。$h$ は $0\le x\le14$ で $32$、$14\le x\le18$ で $22$ になる。
(4) いちばん浅いのは深さ $22$ の $14\le x\le25$（$4$ の下と $7$ の下がつながる）で、幅 $11$。$10+1=11$ なので、$10$ と $1$ を並べる。$h$ は $14\le x\le24$ で $32$、$24\le x\le25$ で $23$ になる。
(5) いちばん浅いのは深さ $23$ の $24\le x\le33$ で、幅 $9$。$9$ を並べると、どの $x$ でも $h(x)=32$ になり、並べ方が完成する。

手順が完成すれば、並べた正方形は本当に分割になっている。

並べ方の手順は分割を与える

Bouwkamp の記号を def-sqs-code の手順で一辺 $L$ の正方形に並べ、並べ方が完成したとする。このとき、並べた正方形の全体は一辺 $L$ の正方形の正方形分割である。

手順の各時点で、次の (ア) が成り立つことを、群を 1 つ並べるごとに確かめる。
(ア) それまでに並べた正方形は、内部に共通の点をもたず、合わせると「横の位置 $x$ ごとに、上の辺から深さ $h(x)$ までの部分」とちょうど一致する。
最初は何も並べておらず、$h(x)=0$ なので (ア) が成り立つ。(ア) が成り立つ時点で次の群を並べるとする。空きの左端を $x_0$、幅を $w$、深さを $d$ とすると、空きの上の $x$ では $h(x)=d$ である。手順 (i) から $c_1+\cdots+c_k=w$ なので、手順 (ii) で並べた正方形は、空きの区間 $x_0\le x\le x_0+w$ を、左から長さ $c_1,c_2,\dots,c_k$ の区間に分けた上に 1 つずつ乗る。一辺 $c_j$ の正方形は、その区間の上で深さ $d$ から $d+c_j$ までの部分を占める。

新しい正方形どうしは、横の区間が端点でしか重ならないので、内部に共通の点をもたない。
新しい正方形の内部の点は深さが $d$ より大きく、その横の位置では $h(x)=d$ なので、(ア) からそれまでの正方形のどれにも入らない。よって古い正方形とも内部に共通の点をもたない。
並べた後の $h$ は、空きの区間の $j$ 番目の小区間で $d+c_j$、それ以外では変わらない。新しい正方形は、ちょうど深さ $d$ から $d+c_j$ までを埋めたので、並べた後も (ア) が成り立つ。
並べ方が完成すると、どの $x$ でも $h(x)=L$ である。(ア) から、並べた正方形は内部に共通の点をもたず（分割の条件 (ii)）、合わせると一辺 $L$ の正方形全体になる（分割の条件 (iii)）。$h$ は並べるたびに増えるだけで、最後に $L$ になるので、どの正方形も深さ $L$ より下にははみ出さない。横は空きの中に並べるので $0\le x\le L$ からはみ出さない。辺は大きい正方形の辺に平行である（分割の条件 (i)）。

主定理：一辺 112 の正方形を 21 個の正方形に分ける

21 個の完全正方形分割

一辺 $112$ の正方形は、一辺
$$ 50,\ 42,\ 37,\ 35,\ 33,\ 29,\ 27,\ 25,\ 24,\ 19,\ 18,\ 17,\ 16,\ 15,\ 11,\ 9,\ 8,\ 7,\ 6,\ 4,\ 2 $$
の、大きさがすべて違う $21$ 個の正方形に分けられる。分割は Bouwkamp の記号
$$ [50,35,27],\ [8,19],\ [15,17,11],\ [6,24],\ [29,25,9,2],\ [7,18],\ [16],\ [42],\ [4,37],\ [33] $$
で表される（図 3）。

一辺 112 の正方形を大きさがすべて違う 21 個の正方形に分けた図。いちばん小さい一辺 2 の正方形は内部にある

lem-sqs-procedure から、上の記号を def-sqs-code の手順で $L=112$ として並べ、各段で手順 (i) の等式が成り立ち、最後にどの $x$ でも $h(x)=112$ になることを確かめればよい。10 個の群を順に並べると、次の表のようになる。

段	並べる群	空きの左端 $x$	空きの深さ	空きの幅	群の和
1	$50,35,27$	$0$	$0$	$112$	$50+35+27=112$
2	$8,19$	$85$	$27$	$27$	$8+19=27$
3	$15,17,11$	$50$	$35$	$43$	$15+17+11=43$
4	$6,24$	$82$	$46$	$30$	$6+24=30$
5	$29,25,9,2$	$0$	$50$	$65$	$29+25+9+2=65$
6	$7,18$	$63$	$52$	$25$	$7+18=25$
7	$16$	$54$	$59$	$16$	$16$
8	$42$	$70$	$70$	$42$	$42$
9	$4,37$	$29$	$75$	$41$	$4+37=41$
10	$33$	$0$	$79$	$33$	$33$

各段の空きは、その前の段までの $h$ から決まる。最初の 3 段を詳しく見る。
段 1．最初は $h(x)=0$ で、空きは $0\le x\le112$ の全体、幅 $112$ である。$50,35,27$ を並べると、$h$ は $0\le x\le50$ で $50$、$50\le x\le85$ で $35$、$85\le x\le112$ で $27$ になる（図 4）。
段 2．いちばん浅いのは深さ $27$ の $85\le x\le112$ で、幅 $27$ である。$8,19$ を並べると、$85\le x\le93$ は $27+8=35$、$93\le x\le112$ は $27+19=46$ になる。
段 3．$h$ は $0\le x\le50$ で $50$、$50\le x\le93$ で $35$（$35$ の下と $8$ の下がつながる）、$93\le x\le112$ で $46$ なので、いちばん浅いのは深さ $35$ の $50\le x\le93$ で、幅 $43$ である。$15,17,11$ を並べる。
段 4 以降も同じように、その時点の $h$ から空きを求めると表のとおりになる（図 5 は段 4 の後。各段の後の $h$ は下の折りたたみにある）。どの段でも空きの幅と群の和が等しいので、手順 (i) が成り立つ。段 10 を並べた後は、どの $x$ でも $h(x)=112$ になるので、並べ方は完成する。lem-sqs-procedure から、21 個の正方形は一辺 $112$ の正方形の正方形分割である。
21 個の一辺の長さは、上に書いたとおり $50$ から $2$ まですべて違う。よって、これは完全正方形分割である。

各段を並べた後の深さ $h(x)$ の一覧を開く

段	並べた後の $h$（区間：深さ）
1	$0\le x\le50$：$50$、$50\le x\le85$：$35$、$85\le x\le112$：$27$
2	$0\le x\le50$：$50$、$50\le x\le93$：$35$、$93\le x\le112$：$46$
3	$0\le x\le65$：$50$、$65\le x\le82$：$52$、$82\le x\le112$：$46$
4	$0\le x\le65$：$50$、$65\le x\le88$：$52$、$88\le x\le112$：$70$
5	$0\le x\le29$：$79$、$29\le x\le54$：$75$、$54\le x\le63$：$59$、$63\le x\le88$：$52$、$88\le x\le112$：$70$
6	$0\le x\le29$：$79$、$29\le x\le54$：$75$、$54\le x\le70$：$59$、$70\le x\le112$：$70$
7	$0\le x\le29$：$79$、$29\le x\le70$：$75$、$70\le x\le112$：$70$
8	$0\le x\le29$：$79$、$29\le x\le70$：$75$、$70\le x\le112$：$112$
9	$0\le x\le33$：$79$、$33\le x\le112$：$112$
10	$0\le x\le112$：$112$

段 3 の後で $50\le x\le65$ が $35+15=50$ になり、左の $0\le x\le50$ の深さ $50$ とつながる。段 5 の後で $63\le x\le65$ は $50+2=52$ になり、右の $65\le x\le88$ の深さ $52$ とつながる。

段 1 の後。赤い線は次の空きで、深さ 27、幅 27

段 4 の後。緑は段 4 で並べた 6 と 24、赤い線は次の空きで、深さ 50、幅 65

面積の和で確かめる

分割になっていれば、21 個の正方形の面積の和は $112^2=12544$ に等しいはずである。実際、
$$ \begin{aligned} &50^2+42^2+37^2+35^2+33^2+29^2+27^2\\ &\quad=2500+1764+1369+1225+1089+841+729=9517,\\ &25^2+24^2+19^2+18^2+17^2+16^2+15^2\\ &\quad=625+576+361+324+289+256+225=2656,\\ &11^2+9^2+8^2+7^2+6^2+4^2+2^2\\ &\quad=121+81+64+49+36+16+4=371 \end{aligned} $$
で、$9517+2656+371=12544$ となり一致する。ex-sqs-24 で見たとおり、面積の和が一致するだけでは分割になるとは言えない。thm-sqs-112 の証明は、並べ方の手順が完成することで示した。

図 3 を拡大しても縮小しても、正方形の大きさの比は変わらない。これから次が分かる（BTB11 §1.5.1）。

どんな大きさの正方形も分けられる

一辺 $L$（$L>0$、整数でなくてもよい）の正方形は、大きさがすべて違う $21$ 個の正方形に分けられる。

thm-sqs-112 の分割で、すべての点の座標を $\dfrac L{112}$ 倍する。正方形は一辺が $\dfrac L{112}$ 倍の正方形に移り、重ならず隙間がないことも、大きさがすべて違うことも変わらない。一辺 $112$ の正方形は一辺 $L$ の正方形に移る。

いちばん小さい正方形の位置

長方形を正方形に分けるの定理「いちばん小さい正方形の位置」は、正方形も長方形の 1 つなので、完全正方形分割にもそのまま使える。

いちばん小さい正方形は周に触れない

どの完全正方形分割でも、いちばん小さい正方形は、大きい正方形の周と共通の点をもたない。また、完全正方形分割の正方形は 5 個以上である。

正方形は縦と横が等しい長方形なので、完全正方形分割は、長方形を大きさがすべて違う 2 個以上の正方形に分けたものである。よって長方形を正方形に分けるの定理「いちばん小さい正方形の位置」から前半が、同じ記事の系「4 個以下では分けられない」から後半が従う。

21 個の分割で確かめる

thm-sqs-112 の分割で、いちばん小さい一辺 $2$ の正方形は、段 5 で左端 $x=63$、深さ $50$ に置かれた。つまり $63\le x\le65$、深さ $50$ から $52$ までの部分で、周（$x=0$、$x=112$、深さ $0$、深さ $112$）のどれにも触れていない。まわりを囲むのは、上の $15$（段 3、$50\le x\le65$、深さ $35$ から $50$）、右の $17$（段 3、$65\le x\le82$、深さ $35$ から $52$）、下の $7$（段 6、$63\le x\le70$、深さ $52$ から $59$）、左の $9$（段 5、$54\le x\le63$、深さ $50$ から $59$）の 4 つである。
2 番目に小さい一辺 $4$ の正方形も、段 9 で $29\le x\le33$、深さ $75$ から $79$ に置かれ、周に触れていない（長方形を正方形に分けるの演習「2 番目に小さい正方形」の主張のとおり）。

21 個より少ない個数の完全正方形分割はない。Wei26 によれば、$21$ は可能な最小の個数であり、21 個の分割のうち、どの一部の正方形を集めても長方形にならないもの（単純なもの）は thm-sqs-112 の 1 つだけで、1978 年に A. J. W. Duijvestijn が見つけた。この記事では 21 個が最小であることは証明しない。

例と反例

Bouwkamp の記号は、群の順序と、群の中の数の順序まで含めて 1 つの分割を表す。順序を変えると並べられなくなる。また、面積の和が合うことだけでは分割にならない。

外す条件	反例	成り立たなくなること
群の順序を守る	thm-sqs-112 の記号の第 2 群と第 3 群を入れ替える	手順 (i) の等式（空きの幅と群の和）
群の中の数の順序を守る	第 1 群を $[27,35,50]$ と逆に並べる	手順 (i) の等式
並べ方が完成する（面積の和だけを見る）	一辺 $1$ から $24$ の $24$ 個（面積の和は $70^2$）	一辺 $70$ の正方形の分割になる
大きさがすべて違う	一辺 $3$ の正方形を $2$ と $1$ が $5$ 個で分ける	完全正方形分割である

反例：群の順序を入れ替える

記号の第 2 群 $[8,19]$ と第 3 群 $[15,17,11]$ を入れ替えて
$$ [50,35,27],\ [15,17,11],\ [8,19],\ \dots $$
とする。段 1 は thm-sqs-112 の証明と同じで、次の空きは深さ $27$ の $85\le x\le112$、幅 $27$ である。ところが次の群の和は $15+17+11=43$ で、$43\ne27$ なので手順 (i) が成り立たず、並べられない（図 6）。右の辺からはみ出してしまう。

段 1 の後の幅 27 の空きに、和が 43 の 15、17、11 を並べようとすると、右の辺からはみ出す

反例：群の中の順序を逆にする

第 1 群を $[27,35,50]$ と逆に並べると、段 1 で $27,35,50$ が左から並び、$h$ は $0\le x\le27$ で $27$、$27\le x\le62$ で $35$、$62\le x\le112$ で $50$ になる。次の空きは深さ $27$ の $0\le x\le27$、幅 $27$ だが、第 2 群の和は $8+19=27$ で一致する。そこで $8,19$ を並べると、$h$ は $0\le x\le8$ で $35$、$8\le x\le27$ で $46$ になり、次の空きは深さ $35$ の $0\le x\le8$ と $27\le x\le62$ のうち左の $0\le x\le8$、幅 $8$ である。第 3 群の和は $43$ で、$43\ne8$ なので並べられない。図 3 を左右に裏返した分割なら並べられるが、その記号は別のものになる。

反例：大きさが同じものを含む

ex-sqs-easy (2) の一辺 $3$ の正方形の分割は、正方形分割ではあるが、一辺 $1$ の正方形が $5$ 個あるので完全正方形分割ではない。いちばん小さい一辺 $1$ の正方形は、どれも周に触れている。cor-sqs-smallest の結論は、大きさがすべて違うことを外すと成り立たない。

大学数学で見る：正方形の正方形分割の探索

大きさがすべて違う正方形で正方形を分けられるかという問題は、1935 年に Cambridge 大学の学生だった Brooks・Smith・Stone・Tutte の 4 人が取り組み、分割を見つけただけでなく、平面グラフや電気回路との深いつながりを見つけた（BTB11 §1.5.1）。

問題の由来と記録を開く

BTB11 §1.5.1 によると、Stone がこの問題を持ち出したきっかけは、Dudeney のパズルの本（1902 年）の「Lady Isabel's Casket」という問題だった。また 4 人は、Lusin が「正方形は大きさがすべて違う正方形には分けられない」と予想していたことを知り、それを否定することを目標にした。

Wei26 によれば、1939 年に R. Sprague が 55 個の完全正方形分割を発表しており、21 個の単純な完全正方形分割（thm-sqs-112）は 1978 年に Duijvestijn が見つけた。

長方形を正方形に分けるの「文字でおく方法」は、正方形の一辺を未知数とする連立一次方程式を立てて解くことである。4 人が見つけた電気回路とのつながりの内容には、この記事では立ち入らない。

演習

横 69、縦 61 の記号を並べる

横 $69$、縦 $61$ の長方形の記号 $[36,33],[5,28],[25,9,2],[7],[16]$ を def-sqs-code の手順で並べ、各段の空きの左端・深さ・幅と群の和を求めよ。いちばん小さい正方形の位置も答えよ。

解答を開く

段 1：空きは $0\le x\le69$、深さ $0$、幅 $69=36+33$。並べた後の $h$ は $0\le x\le36$ で $36$、$36\le x\le69$ で $33$。

段 2：空きは $36\le x\le69$、深さ $33$、幅 $33=5+28$。$h$ は $36\le x\le41$ で $38$、$41\le x\le69$ で $61$。

段 3：空きは $0\le x\le36$、深さ $36$、幅 $36=25+9+2$。$h$ は $0\le x\le25$ で $61$、$25\le x\le34$ で $45$、$34\le x\le36$ で $38$。

段 4：空きは $34\le x\le41$（$2$ の下と $5$ の下がつながる）、深さ $38$、幅 $7$。$h$ は $34\le x\le41$ で $45$。

段 5：空きは $25\le x\le41$、深さ $45$、幅 $16$。並べると、どの $x$ でも $h(x)=61$ で完成する。

いちばん小さい一辺 $2$ の正方形は段 3 で $34\le x\le36$、深さ $36$ から $38$ に置かれ、周に触れない。

一辺 1 の正方形の分割

一辺 $1$ の正方形を、大きさがすべて違う $21$ 個の正方形に分けたとき、いちばん大きい正方形といちばん小さい正方形の一辺を求めよ。

解答を開く

cor-sqs-scale の証明のとおり、thm-sqs-112 の分割を $\dfrac1{112}$ 倍する。いちばん大きい正方形の一辺は $\dfrac{50}{112}=\dfrac{25}{56}$、いちばん小さい正方形の一辺は $\dfrac2{112}=\dfrac1{56}$ である。

さらに先へ

立体で同じことを考えると、答えは逆になる。直方体（立方体を含む）は、大きさがすべて違う有限個の立方体には分けられない。次に読む直方体を異なる立方体に分けるで、cor-sqs-smallest の考え方をくり返し使って証明する。
長方形を正方形に分けられる条件（辺の比が有理数）は長方形を正方形に分けるで扱った。
平方数の和が平方数になる例（$1^2+\cdots+24^2=70^2$）は、平方数の話題としても面白い。