Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I came up with the following conjecture the other day, and was wondering if the result was well-known or even true:

Define $f(P)$ for a polyomino $P$ (without holes) to be the least number of total pieces in which two copies of $P$ can be split such that these pieces can be rearranged to form a copy of $P$ scaled up by $\sqrt{2}$.

Conjecture: For a polyomino $P$ with area $A$, we have $f(P)\le A+3$.

This bound seems very sharp for small polyominoes. So far I've shown that $f(P)\le A+3$ holds for all rectangle polyominoes with a relatively simple construction. Is this true in general? Or is there any weaker non-trivial (i.e., better than $f(P)\le 4A$) bound we can prove in the general case or some specific case?

share|improve this question
2  
I got a slightly nontrivial lower bound of $2.5A$ for all polynomioes except the single monomino. The proof is simple - first check all polynomioes that can't be split up into two pieces of size >= 2. Then for all other polynomioes, we can split them into two smaller ones and solve each half separately. I wouldn't be surprised if, following this same method and just checking larger shapes, we could prove fairly good bounds of the form "$f(P) \leq cA$ for sufficiently large polynomioes". –  Lopsy Dec 8 '12 at 4:57
1  
By the way, in case you're doing this on paper like me, here's a fairly quick way to find good splittings of most polynominoes: draw two copies of the polynomino, meshed so they fit together as well as possible; draw an outline of the larger poynomino diagonally covering as much as possible of the smaller two; and then use as few splits as possible to fill in the gaps. –  Lopsy Dec 8 '12 at 5:03
    
@Gerry Myerson: I have edited, it was indeed supposed to be polyonimo. –  Apple Dec 8 '12 at 13:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.