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$?
Tiling pythagorean triples with minimal polyominoes
-
0Is it just me, or does this problem sound a little too close to Project Euler problem 139? – 2012-04-24
-
0I 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. – 2012-04-24
-
0Here's a link: http://projecteuler.net/problem=139. Personally, I don't see much resemblance between the two problems. – 2012-04-24
-
0There 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. – 2012-04-24
-
0http://en.wikipedia.org/wiki/Polyomino – 2012-04-26
2 Answers
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.