12
$\begingroup$

Professor Halfbrain has spent his entire weekend by cutting lots of wooden $50\times50$ checkerboards into lots of polyominoes. He looked at various pattern polyominoes with area $49$, and always tried to cut as many copies of the pattern as possible out of some wooden $50\times50$ checkerboard. The pattern polyomino could be rotated and flipped over, but it always had to be aligned with the cells of the checkerboard. For most patterns, the professor was able to cut quite a number of copies while wasting only a small fraction of the checkerboard area.

Professor Halfbrain has also proved two extremely deep theorems on such checkerboard cuttings.

Professor Halfbrain's first theorem: For every possible polyomino pattern of area $49$, it is possible to cut at least one copy of the pattern out of a wooden $50\times50$ checkerboard.

Professor Halfbrain's second theorem: There exist polyomino patterns of area $49$, for which it is not possible to cut 52 copies of the pattern out of a wooden $50\times50$ checkerboard.

This puzzle asks you to improve the two theorems of professor Halfbrain and to make them even deeper. Find an integer $x$, so that "one copy" in the first theorem may be replaced by "$x$ copies", and so that "52 copies" in the second theorem may be replaced by "$x+1$ copies" (again yielding true statements, of course).

$\endgroup$
  • $\begingroup$ Can you clarify for me: When the professor cuts X copies of P out of a 100x100 board, does he use a single wooden board for all those copies, or does he mean to find X different copy-cuts cut from X different wooden boards? $\endgroup$ – BmyGuest Feb 8 '15 at 17:15
  • 2
    $\begingroup$ Also the puzzle seems very "mathy" in its statement. Maybe you could draw a broader audience by illustrating what you mean on a smaller grid? Pictures always help. (Only after 5th read I've understood the task.) $\endgroup$ – BmyGuest Feb 8 '15 at 17:17
  • 1
    $\begingroup$ Can the polyominos be assumed to be simply connected, or are polyominos with a hole allowed for? $\endgroup$ – Johannes Feb 8 '15 at 22:44
  • $\begingroup$ @Johannes: I have corrected x and x+1; thanks! For the holes: Yes, polyominoes with holes are allowed. $\endgroup$ – Gamow Feb 9 '15 at 9:00
  • $\begingroup$ for second theorem: there is no polyomino of area 49 that could be cut 52 times from a 50*50 checkboard. Total area would be 49*52 = 2548 and board area is only 50*50 = 2500. I guess you meant 51, not 52 $\endgroup$ – Novarg Feb 10 '15 at 11:26
10
$\begingroup$

The answer is

$x=4$.

Here's the proof, step by step (EDIT: the result was right, but the specific argument had a hole; I think I've patched that now) :

If the minimal bounding box of a 49-cell polynomino is $x\times y$, then $x+y\leq 50$.
Proof: by induction. A 1-cell polyomino fits in a $1\times 1$ box, so its semiperimeter (i.e., $x+y$) is 2. Every $(n+1)$-cell polyomino is formed by adding a cell to an $n$-cell polyomino, and that additional cell can increase the $x$ size of the bounding box or increase the $y$ size of the bounding box, but not both, so if every $n$-cell polyomino fits in a box of semiperimeter $n+1$, then every $(n+1)$-cell polyomino fits in a box of semiperimeter $(n+1)+1$.

Four $x\times y$ rectangles with $x+y\leq50$ always fit into a $50\times50$ square.
Proof: by construction. Use a 'pinwheel' arrangement where the two $x\times y$ boxes in the NE and SW corners are placed with $x$ horizontal and $y$ vertical, and the two in the other corners are placed with $y$ horizontal and $x$ vertical.

Five copies of a 'Plus' polyomino (with two length-$25$ arms intersecting in the middle) can't be placed in a $50\times50$ square.
Proof: First, a few subfacts. For convenience, I'm going to define the $50\times 50$ square as running from $\langle-25,-25\rangle$ to $\langle25,25\rangle$.
a) The center of any Plus must be inside the inner square from $\langle-13,-13\rangle$ to $\langle13,13\rangle$ (or else it'll go outside the bounds of the $50\times50$ board).
b) The center of one Plus can't be placed anywhere in the bounding box of another (or else the two will overlap on their arms).
c) If the center of a Plus is placed anywhere in a $13\times 13$ box, its bounding box covers that entire space.
Now consider the four quadrants from $\langle0,0\rangle$ out to $\langle\pm13,\pm13\rangle$. By b) and c), each of these quadrants can only have one Plus's center placed within it, but between them these quadrants cover the entire 'legal' space (per a) ) for placing Plus polyominoes. Since we can fit only one per quadrant, we can fit at most four.

$\endgroup$
4
$\begingroup$

You can make a polyomino consisting of a 13x14 square with an 11x12 hole in the middle with one missing corner tile. This can only fit 9 times into the 50x50 board. I believe this is the worst possible fit, so I would substitute 'nine' and 'ten' for 'one' and '52' in the first and second theorems respectively.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ I believe there are worse fits than the rectangle. $\endgroup$ – Lopsy Feb 21 '15 at 0:56

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.