Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Dissection of a square into n similar rectangles via guillotine cuts
from dataclasses import dataclass
from typing import Any
from sage.all import *
n = 4
# A guillotine partition is a binary tree of horizontal and vertical cuts.
# In our problem each leaf node is a horizontal or vertical rectangle.
# For example, 3 vertical cuts and 4 vertical rectangles produce [ | | | ]
@dataclass
class CH:
c0: Any
c1: Any
@dataclass
class CV:
c0: Any
c1: Any
@dataclass
class RH:
pass
@dataclass
class RV:
pass
# First we generate the partitions.
# At the root, due to symmetry we only need one of CH or CV.
def guillotine(n, root=False):
if n <= 1:
yield RH()
yield RV()
else:
for i in range(1, n//2 + 1):
for c0 in guillotine(i):
for c1 in guillotine(n-i):
yield CH(c0, c1)
if not root:
yield CV(c0, c1)
# Then, we find the aspect ratios of the partitions,
# assuming the aspect ratios of the leaves are 1:u,
# and solve for the values of u that yield squares.
u = QQ['u'].0
def simplify(p0, p1):
q = p0.gcd(p1)
return (p0//q, p1//q)
def aspect(t):
if isinstance(t, RH):
return (u,1)
elif isinstance(t, RV):
return (1,u)
elif isinstance(t, CH):
(w0,h0) = aspect(t.c0)
(w1,h1) = aspect(t.c1)
return simplify(w0*w1, w0*h1 + w1*h0)
elif isinstance(t, CV):
(w0,h0) = aspect(t.c0)
(w1,h1) = aspect(t.c1)
return simplify(w0*h1 + w1*h0, h0*h1)
d = {aspect(t):t for t in guillotine(n, True)}
def genroots(d):
for a, t in d.items():
rs = (a[0]-a[1]).roots(ring=RR)
for r in rs:
if r[0] >= 1:
yield(1/r[0], r[0], a, t)
l = sorted(list(genroots(d)), key=lambda i: i[0])
for i in l:
print(i)
@narain
Copy link
Author

narain commented Dec 19, 2022

As requested by John C. Baez, a list of the polynomials that the ratios are roots of for n = 5.

u - 5
u^3 - 4*u^2 + u - 3
u^3 - 4*u^2 + 2*u - 4
2*u - 7
u^3 - 4*u^2 + 3*u - 3
2*u^3 - 6*u^2 + u - 2
u^3 - 3*u^2 + 2*u - 5
u^3 - 3*u^2 + 2*u - 4
2*u^3 - 6*u^2 + 2*u - 2
u^3 - 3*u^2 + u - 1
3*u - 8
u^3 - 3*u^2 + 3*u - 5
2*u^3 - 5*u^2 + u - 2
u^5 - 3*u^4 + 3*u^3 - 4*u^2 + u - 1
-2*u^2 + 6*u - 3
2*u^3 - 5*u^2 + 2*u - 3
3*u - 7
u^4 - 3*u^3 + 3*u^2 - 4*u + 2
2*u^3 - 5*u^2 + 3*u - 3
u^3 - 3*u^2 + 4*u - 4
-u^2 + 4*u - 4
4*u - 8
3*u^3 - 6*u^2 + u - 1
2*u^3 - 4*u^2 + 2*u - 3
u^3 - 2*u^2 + 3*u - 5
3*u^3 - 6*u^2 + 2*u - 2
u^5 - 2*u^4 + 3*u^3 - 5*u^2 + u - 1
2*u^3 - 4*u^2 + 3*u - 4
4*u - 7
u^3 - 2*u^2 + 4*u - 6
-u^3 + 3*u^2 - 4*u + 3
2*u^3 - 5*u^2 + 4*u - 2
2*u^3 - 4*u^2 + 3*u - 3
3*u^3 - 5*u^2 + 2*u - 3
5*u - 8
u^5 - 2*u^4 + 3*u^3 - 4*u^2 + u - 1
-3*u^2 + 6*u - 2
2*u^4 - 4*u^3 + 3*u^2 - 3*u + 1
3*u^3 - 5*u^2 + 2*u - 2
4*u^3 - 6*u^2 + u - 1
-2*u^3 + 4*u^2 - 3*u + 2
2*u^3 - 3*u^2 + 3*u - 4
u^5 - 2*u^4 + 3*u^3 - 4*u^2 + 2*u - 1
5*u - 7
u^3 - 2*u^2 + 3*u - 3
2*u^3 - 3*u^2 + 2*u - 2
-u^3 + 2*u^2 - 4*u + 4
3*u^3 - 5*u^2 + 3*u - 2
3*u^3 - 4*u^2 + u - 1
4*u^3 - 6*u^2 + 2*u - 1
4*u - 5
2*u^3 - 3*u^2 + 4*u - 4
-5*u + 6
6*u - 7

By my count there are 51 different ratios. But there are more than 51 polynomials above, because some of them yield equal roots.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment