1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Why insist that the grid size be even? Seems more natural to ask this for $(n-1)$-ominos in an $n \times n$ grid, as long as there's no immediate counterexample with $n$ odd. $\endgroup$ – Noam D. Elkies Feb 20 '12 at 5:47
  • $\begingroup$ If the shape is at most 2n/5 squares wide, the answer is yes. For n =11, consider an S shape that fits in a 5 by 9 rectangle. It is possible to cut out 3 copies of s, but just barely. Perhaps someone can tweak this into a counterexample. Gerhard "Ask Me About System Design" Paseman, 2012.02.19 $\endgroup$ – Gerhard Paseman Feb 20 '12 at 6:43
  • $\begingroup$ I assume you mean the shape can be rotated, but can it be reflected? $\endgroup$ – Zack Wolske Feb 20 '12 at 7:28
  • $\begingroup$ why not four copies? $\endgroup$ – alberto.bosia Feb 20 '12 at 8:02
  • $\begingroup$ @Noam D.Elkies: I made a figure for all $2n\times 2n$ grid sheets that could be placed such that no other figure could be cut out, that's why I'm intrested for the grid size to be even. @Zack Wolske: yes, it can be also rotated and reflected. @alberto.bosia: I could make a counter example for that case. $\endgroup$ – Goodarz Feb 20 '12 at 8:53
4
$\begingroup$

Asked and answered at https://math.stackexchange.com/questions/111011/two-shapes-in-a-2n-times-2n-grid-sheet-can-we-pick-third-one/111196#111196

EDIT: I was hoping that my answer for the size 8 grid would generalize readily to larger squares, but so far the only ones I can handle are size $6k+2$, $k=1,2,\dots$. The piece is a cross with mutually bisecting lines of $4k+1$ and $2k+1$ squares. The two crosses are placed in the same orientation and in such a way that the short lines of squares meet at a single point, that point being the center of the big square. An argument similar to the one given at m.se shows that there are very few places to put a third line of $4k+1$ squares:

  1. You can put it too close to the edge of the big square to allow for the line of $2k+1$, or

  2. You can put it in either of two places where it runs from an edge of the big square just past a long arm of one piece and just short of a long arm of the other piece. But this third line can't be part of a third piece because its short arm would overlap a long arm of one of the first two pieces.

[Added by J.O'Rourke:]
           alt text

$\endgroup$
  • $\begingroup$ yes, I asked the question there, but that answer is for the case when $n=4$, I want a solution (or counter-example) for all $n$. $\endgroup$ – Goodarz Feb 20 '12 at 11:42
  • 3
    $\begingroup$ The point is that when you ask a question here (or on m.se) you should indicate what you already know and what you've already done, and that includes letting people know if you've already posted the question elsewhere. $\endgroup$ – Gerry Myerson Feb 20 '12 at 22:22
  • $\begingroup$ @Joseph, many thanks for adding the diagram. $\endgroup$ – Gerry Myerson Feb 21 '12 at 21:55

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.