ルジンの問題 - 井戸端

ルジンの問題

https://upload.wikimedia.org/wikipedia/commons/6/64/Squaring_the_square.svg

ルジンの問題 - Wikipedia

ルジンの問題（Luzin - のもんだい）とは、正方形に関してニコライ・ルジン (Nikolai Luzin) が考えた問題である。

「任意の正方形を、2個以上の全て異なる大きさの正方形に分割できるか」という問題であり、ルジンはこの問題の解は存在しないと予想したが、その後いくつかの例が発見された。

英語版の記事の方が充実している

Squaring the square - Wikipedia

辺の長さは整数じゃないといけない？yosider.icon

整数の制限がなければ、可能(問題にならない)っぽいから、整数である必要がありそうbiwa.icon

任意の正の実数$ 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)みたいな感じで適当に作ればいい

って思ったけどなんか条件足りない気がするな

面積だけで考えると敷き詰めの条件を表しきれないSummer498.icon

無理数をOKにしたら他の解が得られたりするのだろうかSummer498.icon

有理数の場合は適当にスケーリングしたら整数になる

2個以上の全て異なる大きさの正方形に分割された正方形をPerfect Squared Square (PSS)と呼ぶ

鏡映や回転で同じ分割になるものは除く

以下、PSSを構成する正方形の個数をorderと呼ぶ

最初に見つかったPSSはorder 55で、一辺の長さは4205（1939年にRoland Spragueが発見）

https://upload.wikimedia.org/wikipedia/commons/d/d8/Sprague_squared_square.svg

このPSSは全て異なる大きさの正方形に分割された幾つかの長方形からなる

例えば緑色の部分は縦1885、横1363の長方形である

2つ以上の正方形からなる部分集合が長方形または正方形を成さないPSSをsimpleであると言い、Simple Perfect Squared Square (SPSS)と呼ぶ

SPSSの最小解（orderが最小となる解）は冒頭の図の通り（order 21のSPSSで一辺の長さは112）

1978年にA. J. W. Duijvestijnがコンピュータ探索で発見

cf. Simple perfect squared square of lowest order - ScienceDirect

具体的な探索プログラムは以下のPDFを参照のこと（Duijvestijnの博士論文）

Electronic computation of squared rectangles

Duijvestijnが見つけたorder 22のSPSS(下図右上)は一辺の長さが110であり、これは最小解の辺の長さより短い

下図にはorder 22のSPSSが2種類あるが、実はそのようなSPSSは8種類ある

https://upload.wikimedia.org/wikipedia/commons/9/9f/Smallest_perfect_squared_squares.svg

$ 1\le n \le 37に対するorder$ nのSPSSの数$ a_{n}は以下のOEIS記事を参照

初めの幾つかは$ 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を描画させることも可能

今まで考えたことないタイプの問題で興味深いSummer498.icon

タイリングを4色塗り分けした絵を描くのも面白そう Done

ルジンの問題#64d9f4a5e60035000024f0b6

多分塗り分けも難しいと思う

というか、回路理論と関係あるの意外すぎるな

正方形による分割

回路問題として解けるのすご

長方形バージョンだけか

正方形縛りにするとムズくなりそう？

すごいyosider.icon

解がシンプルじゃないのがまた興味深い

（正方形バージョンの問題を）方積問題とも言うらしい

補遺・方積問題

方形分割とも？

回路に対応付ける手法をSmith networkという？

物理数学 – オススメの参考書 (網羅性重視で厳選紹介) | Math Relish

Smith diagramのほうが正しそう

Brooks, Smith, Stone and Tutte, II

また，正方形の完全正方分割ができたとなると，正三角形の完全正三角分割と立方体の完全立方分割も考えてみたくなりますが，不可能であることが証明されているようです．

補遺・方積問題

日本人の貢献もあったらしい

正方形の内部を總て異る有限個の正方形で隙間なく一重に蔽ふ問題に就て

正方形分割正方形問題　前編 - 空間情報クラブ｜インフォマティクス運営のWebメディア

1991年、彼は世界初の「正方形分割方陣」を発表しました。正方形分割正方形の中に魔方陣をつくってみせたのです。

1978年、デゥイベスチジンによる最小の単純完全正方形分割正方形は21個の正方形でできていますが、それらが魔方陣でできていて、全体の正方形も魔方陣となっている魔方陣です。

https://gyazo.com/235d0dd54c98e50ea10bb1395a671014

正方形分割正方形問題　後編 - 空間情報クラブ｜インフォマティクス運営のWebメディア

svg-hosting で描いたルジンの問題の解の4色塗り分け

https://svg-hosting.vercel.app/api/svg?url=https://scrapbox.io/api/code/villagepump/%E3%83%AB%E3%82%B8%E3%83%B3%E3%81%AE%E5%95%8F%E9%A1%8C/Luzin.svg

https://svg-hosting.vercel.app/api/svg?url=https://scrapbox.io/api/code/villagepump/%E3%83%AB%E3%82%B8%E3%83%B3%E3%81%AE%E5%95%8F%E9%A1%8C/Issacoid-Luzin.svg

code: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"/>

<rect x="50" y="00" width="35" height="35" fill="#efdfcc"/>

<rect x="85" y="00" width="27" height="27" fill="#734e30"/>

<rect x="85" y="27" width="08" height="08" fill="#deb997"/>

<rect x="93" y="27" width="19" height="19" fill="#a88363"/>

<rect x="50" y="35" width="15" height="15" fill="#deb997"/>

<rect x="65" y="35" width="17" height="17" fill="#a88363"/>

<rect x="82" y="35" width="11" height="11" fill="#734e30"/>

<rect x="82" y="46" width="06" height="06" fill="#deb997"/>

<rect x="88" y="46" width="24" height="24" fill="#efdfcc"/>

<rect x="00" y="50" width="29" height="29" fill="#efdfcc"/>

<rect x="29" y="50" width="25" height="25" fill="#734e30"/>

<rect x="54" y="50" width="09" height="09" fill="#a88363"/>

<rect x="63" y="50" width="02" height="02" fill="#734e30"/>

<rect x="63" y="52" width="07" height="07" fill="#efdfcc"/>

<rect x="70" y="52" width="18" height="18" fill="#734e30"/>

<rect x="54" y="59" width="16" height="16" fill="#deb997"/>

<rect x="70" y="70" width="42" height="42" fill="#a88363"/>

<rect x="29" y="75" width="04" height="04" fill="#deb997"/>

<rect x="33" y="75" width="37" height="37" fill="#efdfcc"/>

<rect x="00" y="79" width="33" height="33" fill="#a88363"/>

</svg>

code: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"/>

<rect x="50" y="00" width="35" height="35" fill="#e4d7b5"/>

<rect x="85" y="00" width="27" height="27" fill="#9cbce3"/>

<rect x="85" y="27" width="08" height="08" fill="#6e733b"/>

<rect x="93" y="27" width="19" height="19" fill="#5c89c0"/>

<rect x="50" y="35" width="15" height="15" fill="#6e733b"/>

<rect x="65" y="35" width="17" height="17" fill="#5c89c0"/>

<rect x="82" y="35" width="11" height="11" fill="#9cbce3"/>

<rect x="82" y="46" width="06" height="06" fill="#6e733b"/>

<rect x="88" y="46" width="24" height="24" fill="#e4d7b5"/>

<rect x="00" y="50" width="29" height="29" fill="#e4d7b5"/>

<rect x="29" y="50" width="25" height="25" fill="#9cbce3"/>

<rect x="54" y="50" width="09" height="09" fill="#5c89c0"/>

<rect x="63" y="50" width="02" height="02" fill="#9cbce3"/>

<rect x="63" y="52" width="07" height="07" fill="#e4d7b5"/>

<rect x="70" y="52" width="18" height="18" fill="#9cbce3"/>

<rect x="54" y="59" width="16" height="16" fill="#6e733b"/>

<rect x="70" y="70" width="42" height="42" fill="#5c89c0"/>

<rect x="29" y="75" width="04" height="04" fill="#6e733b"/>

<rect x="33" y="75" width="37" height="37" fill="#e4d7b5"/>

<rect x="00" y="79" width="33" height="33" fill="#5c89c0"/>

</svg>

タイリング