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.

Can anyone help me with this problem? It just popped to my mind!!!

we have a $2n\times 2n$ grid sheet and a connected shape $L$ consisting of $2n-1$ grid squares. we've cut two copies of $L$ out of the sheet. Is it always possible to cut a third copy of $L$?

I think the answer is yes, but I couldn't solve it. any Ideas?

share|improve this question
    
Should rotations and reflections be counted as copies? –  Adam Bailey Feb 19 '12 at 21:05
    
yes, they are counted as copies. –  Goodarz Mehr Feb 20 '12 at 5:15
add comment

2 Answers

up vote 5 down vote accepted

Let $n=4$. Label the squares $(a,b)$, $1\le a\le8$, $1\le b\le8$. Cut out the identical shapes $$(3,3),(4,3),(5,3),(6,3),(7,3),(5,2),(5,4)$$ and $$(2,6),(3,6),(4,6),(5,6),(6,6),(4,5),(4,7)$$ You'll find you can't cut out another copy of this shape.

Proof: any copy of this shape must have a row of five, horizontally or vertically. The row of five can't be along an edge of the square because there must be a square on either side of the row of five. No horizontal row, other than an edge, has five contiguous squares, once you have cut out the two shapes. The only columns with five contiguous squares, other than the edge columns, are columns 2 and 7, and those two locations for the 3rd shape are blocked by the missing squares at $(3,3)$ and $(6,6)$, respectively.

share|improve this answer
    
Beautiful and elegant solution for this case. can we generalize it to all large $n$? and another question, with the same conditions as above, suppose we have cut one copy of $L$ out of the sheet, can we always cut a second one? –  Goodarz Mehr Feb 20 '12 at 5:39
    
For the case n = 4, here is a proof that a second copy of L can always be cut. –  Adam Bailey Feb 21 '12 at 10:03
    
I have posted a solution for $n=3r+1$, $r=1,2,\dots$ at MO. You wrote, "I made a figure for all $2n\times2n$ grid sheets that could be placed such that no other figure could be cut out" over at MO - doesn't this mean you already have a negative answer to your question, "suppose we have cut one copy of $L$ out of the sheet, can we always cut a second one?" –  Gerry Myerson Feb 21 '12 at 10:03
    
Apologies, I seem to be pressing a wrong button that submits a comment too early. –  Adam Bailey Feb 21 '12 at 10:11
    
For n = 4, here is an outline proof that a second copy can always be cut. Most connected shapes of 7 squares can be enclosed by a 7 x 3 rectangle. This leaves 5 free rows or 5 free columns. 3 of these must be above, below or to one side, where a second 7 x 3 rectangle can fit. If the shape cannot fit a 7 x 3 rectangle, it must fit a 4 x 4 square. One quarter of that square (ie one 2 x 2 square in a corner must be empty, leaving an L-shape forming three-quarters of a 4 x 4 square. Wherever such an L-shape is located it is always possible to fit a second such shape. –  Adam Bailey Feb 21 '12 at 10:58
show 1 more comment

I was blocked from adding this to Gerry's answer, so here it is separately:
          enter image description here

share|improve this answer
add comment

Your Answer

 
discard

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

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