# 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 –  JoeHobbit 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, ...$.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9551504850387573, "perplexity": 284.8406837195973}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2014-10/segments/1393999653644/warc/CC-MAIN-20140305060733-00051-ip-10-183-142-35.ec2.internal.warc.gz"}