Squaring the square

related topics
{math, number, function}
{@card@, make, design}
{township, household, population}
{system, computer, user}
{build, building, house}
{village, small, smallsup}
{work, book, publish}

Squaring the square is the problem of tiling an integral square using only other integral squares. (An integral square is a square whose sides have integer length.) The name was coined in a humorous analogy with squaring the circle. Squaring the square is an easy task unless additional conditions are set. The most studied restriction is that the squaring be perfect, meaning that the sizes of the smaller squares are all different. A related problem is squaring the plane, which can be done even with the restriction that each natural number occurs exactly once as a size of a square in the tiling.

Contents

Perfect squared squares

A "perfect" squared square is a square such that each of the smaller squares has a different size.

It is first recorded as being studied by R. L. Brooks, C. A. B. Smith, A. H. Stone, and W. T. Tutte, at Cambridge University. They transformed the square tiling into an equivalent electrical circuit — they called it "Smith diagram" — by considering the squares as resistors that connected to their neighbors at their top and bottom edges, and then applied Kirchhoff's circuit laws and circuit decomposition techniques to that circuit.

The first perfect squared square was found by Roland Sprague in 1939.

If we take such a tiling and enlarge it so that the formerly smallest tile now has the size of the square S we started out from, then we see that we obtain from this a tiling of the plane with integral squares, each having a different size.

Martin Gardner has published an extensive [1] article written by W. T. Tutte about the early history of squaring the square.

Simple squared squares

A "simple" squared square is one where no subset of the squares forms a rectangle or square, otherwise it is "compound". The smallest simple perfect squared square was discovered by A. J. W. Duijvestijn using a computer search. His tiling uses 21 squares, and has been proved to be minimal. The smallest perfect compound squared square was discovered by T.H. Willcocks in 1946 and has 24 squares; however, it was not until 1982 that Duijvestijn, Pasquale Joseph Federico and P. Leeuw mathematically proved it to be the lowest-order example.[1]

Full article ▸

related documents
Superellipse
Sorting
Lyapunov fractal
Partition of unity
Composite number
Best-first search
Nearest neighbour algorithm
Blum Blum Shub
Complete measure
Weak entity
EXPSPACE
RP (complexity)
Zero divisor
Normal morphism
Almost everywhere
Pole (complex analysis)
Axiom of union
Sophie Germain prime
Chosen-plaintext attack
Zhu Shijie
Baire category theorem
NP-easy
Tree structure
Wikipedia:Searching bug reports
Up to
HTML scripting
Hamiltonian path problem
Jess programming language
Complete category
Laurent polynomial