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$?

  • $\begingroup$ Is it just me, or does this problem sound a little too close to Project Euler problem 139? $\endgroup$ – Mike Apr 24 '12 at 0:40
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Apr 24 '12 at 0:51
  • $\begingroup$ Here's a link: projecteuler.net/problem=139. Personally, I don't see much resemblance between the two problems. $\endgroup$ – Gerry Myerson Apr 24 '12 at 0:54
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Apr 24 '12 at 0:58
  • $\begingroup$ en.wikipedia.org/wiki/Polyomino $\endgroup$ – User3910 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.