ルジンの問題
>ルジンの問題（Luzin - のもんだい）とは、正方形に関してニコライ・ルジン (Nikolai Luzin) が考えた問題である。
>「任意の正方形を、2個以上の全て異なる大きさの正方形に分割できるか」という問題であり、ルジンはこの問題の解は存在しないと予想したが、その後いくつかの例が発見された。
英語版の記事の方が充実している
辺の長さは整数じゃないといけない？
整数の制限がなければ、可能(問題にならない)っぽいから、整数である必要がありそう
任意の正の実数xについて、x^2 = a^2 + b^2を満たすような、実数a, b(a\not =b)は存在する
a, bは、a^2 = (x^2 /3), b^2 = (x^2 \times 2/3)みたいな感じで適当に作ればいい
って思ったけどなんか条件足りない気がするな
面積だけで考えると敷き詰めの条件を表しきれない
無理数をOKにしたら他の解が得られたりするのだろうか
有理数の場合は適当にスケーリングしたら整数になる
2個以上の全て異なる大きさの正方形に分割された正方形をPerfect Squared Square (PSS)と呼ぶ
鏡映や回転で同じ分割になるものは除く
以下、PSSを構成する正方形の個数をorderと呼ぶ
最初に見つかったPSSはorder 55で、一辺の長さは4205（1939年にRoland Spragueが発見）
このPSSは全て異なる大きさの正方形に分割された幾つかの長方形からなる
例えば緑色の部分は縦1885、横1363の長方形である
2つ以上の正方形からなる部分集合が長方形または正方形を成さないPSSをsimpleであると言い、Simple Perfect Squared Square (SPSS)と呼ぶ
SPSSの最小解（orderが最小となる解）は冒頭の図の通り（order 21のSPSSで一辺の長さは112）
1978年にA. J. W. Duijvestijnがコンピュータ探索で発見
具体的な探索プログラムは以下のPDFを参照のこと（Duijvestijnの博士論文）
Duijvestijnが見つけたorder 22のSPSS(下図右上)は一辺の長さが110であり、これは最小解の辺の長さより短い
下図にはorder 22のSPSSが2種類あるが、実はそのようなSPSSは8種類ある
初めの幾つかはa_{i}=0\; (1\le i \le 20),a_{21}=1,a_{22}=8,a_{23}=12,a_{24}=26, \dotscである
Squaring.net：ルジンの問題あるいはその類似問題についての、歴史的経緯を含めた極めて詳細なデータベース
特にルジンの問題と関連するページはSimple Perfect Squared Squaresを参照
Orderを選択してブラウザ上でSPSSを描画させることも可能
今まで考えたことないタイプの問題で興味深い
タイリングを4色塗り分けした絵を描くのも面白そう Done
多分塗り分けも難しいと思う
というか、回路理論と関係あるの意外すぎるな
回路問題として解けるのすご
長方形バージョンだけか
正方形縛りにするとムズくなりそう？
すごい
解がシンプルじゃないのがまた興味深い
（正方形バージョンの問題を）方積問題とも言うらしい
方形分割とも？
回路に対応付ける手法をSmith networkという？
Smith diagramのほうが正しそう
> また，正方形の完全正方分割ができたとなると，正三角形の完全正三角分割と立方体の完全立方分割も考えてみたくなりますが，不可能であることが証明されているようです．
日本人の貢献もあったらしい
> 1991年、彼は世界初の「正方形分割方陣」を発表しました。正方形分割正方形の中に魔方陣をつくってみせたのです。
> 1978年、デゥイベスチジンによる最小の単純完全正方形分割正方形は21個の正方形でできていますが、それらが魔方陣でできていて、全体の正方形も魔方陣となっている魔方陣です。
>
svg-hosting で描いたルジンの問題の解の4色塗り分け
Luzin.svg<svg width="244" height="244" viewBox="0 0 122 122" xmlns="http://www.w3.org/2000/svg">
<rect x="00" y="00" width="50" height="50" fill="#a88363"/><!--50-->
<rect x="50" y="00" width="35" height="35" fill="#efdfcc"/><!--35-->
<rect x="85" y="00" width="27" height="27" fill="#734e30"/><!--27-->
<rect x="85" y="27" width="08" height="08" fill="#deb997"/><!--8-->
<rect x="93" y="27" width="19" height="19" fill="#a88363"/><!--19-->
<rect x="50" y="35" width="15" height="15" fill="#deb997"/><!--15-->
<rect x="65" y="35" width="17" height="17" fill="#a88363"/><!--17-->
<rect x="82" y="35" width="11" height="11" fill="#734e30"/><!--11-->
<rect x="82" y="46" width="06" height="06" fill="#deb997"/><!--6-->
<rect x="88" y="46" width="24" height="24" fill="#efdfcc"/><!--24-->
<rect x="00" y="50" width="29" height="29" fill="#efdfcc"/><!--29-->
<rect x="29" y="50" width="25" height="25" fill="#734e30"/><!--25-->
<rect x="54" y="50" width="09" height="09" fill="#a88363"/><!--9-->
<rect x="63" y="50" width="02" height="02" fill="#734e30"/><!--2-->
<rect x="63" y="52" width="07" height="07" fill="#efdfcc"/><!--7-->
<rect x="70" y="52" width="18" height="18" fill="#734e30"/><!--18-->
<rect x="54" y="59" width="16" height="16" fill="#deb997"/><!--16-->
<rect x="70" y="70" width="42" height="42" fill="#a88363"/><!--42-->
<rect x="29" y="75" width="04" height="04" fill="#deb997"/><!--4-->
<rect x="33" y="75" width="37" height="37" fill="#efdfcc"/><!--37-->
<rect x="00" y="79" width="33" height="33" fill="#a88363"/><!--33-->
</svg>
Issacoid-Luzin.svg<svg width="244" height="244" viewBox="0 0 122 122" xmlns="http://www.w3.org/2000/svg">
<rect x="00" y="00" width="50" height="50" fill="#5c89c0"/><!--50-->
<rect x="50" y="00" width="35" height="35" fill="#e4d7b5"/><!--35-->
<rect x="85" y="00" width="27" height="27" fill="#9cbce3"/><!--27-->
<rect x="85" y="27" width="08" height="08" fill="#6e733b"/><!--8-->
<rect x="93" y="27" width="19" height="19" fill="#5c89c0"/><!--19-->
<rect x="50" y="35" width="15" height="15" fill="#6e733b"/><!--15-->
<rect x="65" y="35" width="17" height="17" fill="#5c89c0"/><!--17-->
<rect x="82" y="35" width="11" height="11" fill="#9cbce3"/><!--11-->
<rect x="82" y="46" width="06" height="06" fill="#6e733b"/><!--6-->
<rect x="88" y="46" width="24" height="24" fill="#e4d7b5"/><!--24-->
<rect x="00" y="50" width="29" height="29" fill="#e4d7b5"/><!--29-->
<rect x="29" y="50" width="25" height="25" fill="#9cbce3"/><!--25-->
<rect x="54" y="50" width="09" height="09" fill="#5c89c0"/><!--9-->
<rect x="63" y="50" width="02" height="02" fill="#9cbce3"/><!--2-->
<rect x="63" y="52" width="07" height="07" fill="#e4d7b5"/><!--7-->
<rect x="70" y="52" width="18" height="18" fill="#9cbce3"/><!--18-->
<rect x="54" y="59" width="16" height="16" fill="#6e733b"/><!--16-->
<rect x="70" y="70" width="42" height="42" fill="#5c89c0"/><!--42-->
<rect x="29" y="75" width="04" height="04" fill="#6e733b"/><!--4-->
<rect x="33" y="75" width="37" height="37" fill="#e4d7b5"/><!--37-->
<rect x="00" y="79" width="33" height="33" fill="#5c89c0"/><!--33-->
</svg>