# Tiling pythagorean triples with minimal polyominoes

Given a Pythagorean triple $(a,b,c)$ satisfying $a^2+b^2=c^2$, how to calculate the least number of polyominoes of total squares $c^2$, needed, such that both the square $c^2$ can be build by piecing them together, as well as the two separate squares of side length $a$ and $b$?

-
Is it just me, or does this problem sound a little too close to Project Euler problem 139? –  Mike Apr 24 '12 at 0:40
I suppose it means that Mike has looked at Project Euler problem 139 and is wondering whether your problem is very similar. If it is, that's a bad thing, since the PE people don't want anyone getting help on this (or any other) website. It would perhaps have been helpful had Mike linked to PE 139. –  Gerry Myerson Apr 24 '12 at 0:51
Here's a link: projecteuler.net/problem=139. Personally, I don't see much resemblance between the two problems. –  Gerry Myerson Apr 24 '12 at 0:54
There is a well-known way to cut any two squares into a total of 5 pieces which can then be used to form a single square. However, the 5 pieces are not polyominoes, so this is of no help. –  Gerry Myerson Apr 24 '12 at 0:58
en.wikipedia.org/wiki/Polyomino –  Dale Apr 26 '12 at 0:10

WLOG let $(a, b, c)=1$. Then there is an upper bound of $2+a+b-c$. This bound is sharp for the pair $(3, 4, 5)$, and all the other pairs I've tested. It is attainable as follows:

Let one piece be a $a\times a$ square, and another be a $b\times b$ square with a $(a+b-c)\times (a+b-c)$ square removed from a corner. Now, note that in the $c\times c$ square, there are $2$ blocks remaining, each $(c-a)\times (c-b)$. In the pair of smaller squares, there is a $(a+b-c)\times (a+b-c)$ square remaining.

Now let $(c-a, c-b)=d$. Thus $d^2|2(c-a)(c-b)=(a+b-c)^2\implies d|a+b-c$. So $d|a, d|b\implies d=1$. This, together with $2(c-a)(c-b)=(a+b-c)^2$, means that $c-a, c-b$ are, in some order, $2p^2$ and $q^2$ for $(p, q)=1$ and $2pq=a+b-c$. Now each of the $(c-a)\times (c-b)$ blocks can be dissected into $pq$ equally sized blocks, each $2p\times q$ in dimension. These can be reassembled into a $2pq\times 2pq$ block, as desired.

This gives a total of $2+2pq=2+a+b-c$ blocks. In the example of $a=8, b=15, c=17$, this method produces the following set:

-1 $8\times 8$ block

-1 $15\times 15$ block with an upper corner of $6 \times 6$ missing

-6 $2\times 3$ blocks

For a total of $2+(8+15-17)=8$ blocks.

Note: If $(a, b, c)=d>1$, then this upper bound is just $2+\frac{a+b-c}{d}$.

Note: $(a_1, a_2, ...)$ denotes the $\gcd$ of $a_1, a_2, ...$.

-

For the 3,4,5 triple, many solutions are posted at the Dec 2009 Math Magic. For the 3-4-5, 4 polyominoes are needed.

Various solutions are also given in Dissections: Plane and Fancy.

-