16
$\begingroup$

Alice has a squared paper 8 by 8. She cuts out one 1x1 square from it, at row N, column M. Bob cuts the rest of the paper into pieces. Once he is done, Alice asks Bob to put the pieces together in a way that they form 8x8 paper with missing 1x1 square at row X, column Y. What is the minimal number of pieces Bob must make to always be able to do what Alice says?

For example, Bob can separate all 1x1 squares making 63 pieces, then he can satisfy Alice whatever X and Y she chose. But 63 is too many, he can do better.

$\endgroup$
  • $\begingroup$ Is Bob allowed to rotate or flip his pieces of paper when composing the solution? $\endgroup$ – CiaPan Jan 29 '17 at 21:27
  • $\begingroup$ @CiaPan, he can rotate and flip, yes. $\endgroup$ – klm123 Jan 29 '17 at 21:39
8
$\begingroup$

Proof of optimality:

elias has shown how to do it with 3 pieces. This is optimal.

Suppose that Bob cuts the paper into two pieces. In order to be able to put the missing square in the corners, there must be an orientation in which the cuts go down and right from the missing square, never going to the left of the vertical gray line or above the horizontal one:

diagram

The optimal case would actually be to take the whole rectangle, and I will talk as though he does, but the same applies if he loses parts of it. It's just that losing parts will add more restrictions because we won't be able to apply as many reflections and rotations and still fit in the gap in the L-shaped piece.

The rectangle must go up against two edges because it has to fit within the hole in the L-shaped piece. (If the original missing square was against the edge, the piece is no longer L-shaped, but the rectangle must then go up against three edges). If it touches the top edge then the vertical position of the gap must be against the top edge (if the left or top edge of the rectangle is placed against the top edge of the square), the rectangle's width minus one squares below it (if the right edge is placed against the top edge), or the rectangle's height minus one squares below it (if the rectangles bottom edge is placed against the top edge). If it touches the bottom edge of the square then the vertical position must be against the bottom edge, width minus one squares above it, or height minus one squares above it. That's only at most six different values, and he needs to make eight.

Alternatively,

the L shape can be rotated to put the rectangle in any of the 4 corners. The rectangle itself has at most 8 distinct orientations, so we have at most 32 distinct configurations, and we need 64.

$\endgroup$
  • 1
    $\begingroup$ Sorry, I can't find it: Why the grey rectangle can't lose parts? It will still fit in a corner. $\endgroup$ – klm123 Jan 30 '17 at 7:36
  • $\begingroup$ @klm123, I don't understand the question. I explicitly said that it can lose parts, but that losing parts adds restrictions. $\endgroup$ – Peter Taylor Jan 30 '17 at 11:49
  • $\begingroup$ I think I've got it now: due to restrictions in that case you can't have more than 6 placements. Now I don't understand the last pharagraph. Could you elaborate " If it touches the top edge then the vertical position of the gap must be against the top edge, width minus one squares below it, or height minus one squares below it." please? why "must" and what are "width" and "height"? $\endgroup$ – klm123 Jan 30 '17 at 12:04
  • $\begingroup$ @klm123, cases expanded. But since I was editing anyway, I've added a simpler proof which occurred to me later. $\endgroup$ – Peter Taylor Jan 30 '17 at 12:11
19
$\begingroup$

I think it is possible to do with

3 pieces.

Which look like

L shaped things of different sizes:
an 8x8 square missing a corner of 4x4,
a 4x4 square missing a corner of 2x2, and
a 2x2 square missing a corner of 1x1.

$\endgroup$
  • $\begingroup$ This should be it. But still - can you prove that Bob can't do better? $\endgroup$ – klm123 Jan 29 '17 at 22:36
  • $\begingroup$ Well, obviously it cannot be done with one piece. So the question is if it can be done with two. Or much more, why it cannot be done with two. Still thinking on it. I'm thinking on a reasoning based on how many bits of information is needed to store the position of the hole, and how many different configurations are possible with two pieces. If the former is greater than the latter, we are done. $\endgroup$ – elias Jan 29 '17 at 22:45
  • $\begingroup$ @elias I had hoped for the same at first, but there are pairs of pieces that allow 64 different arrangements, though it's unclear if they can be made to have the holes in 64 different places. $\endgroup$ – xnor Jan 30 '17 at 2:41
  • $\begingroup$ Nice construction: it can clearly be extended to any $m \times n$. The tricky bit is proving it optimal for larger cases. $\endgroup$ – Peter Taylor Jan 30 '17 at 7:39
  • $\begingroup$ I think I have an actual proof, but I need to think it through again. Probably I'll post it tomorrow. $\endgroup$ – elias Jan 30 '17 at 9:35
9
$\begingroup$

Bob can satisfy any Alice's request with 5 pieces of paper: two rectangles 8x4 and 4x2, two squares 4x4 and 2x2 and one piece of three unit squares in an L shape.
I'm not sure, however, if that is an actual minimum.

Image:


enter image description here

EDIT
The answer by elias is much better than mine. Is is based on the same concept of iterative covering the un-punched area, but...

it covers 3/4 of a remaining figure in each step:
enter image description here
while I have stopped at covering just a half (except the last step, where I cover last 3 squares in a single L-piece).

$\endgroup$
  • $\begingroup$ Who cares whether or not this happens to be minimal, it's beautiful $\endgroup$ – humn Jan 30 '17 at 2:41
  • 1
    $\begingroup$ @humn The question is 'What is the minimal number of pieces Bob must make to always be able to do what Alice says?' so at least the question asker cares. $\endgroup$ – CiaPan Jan 30 '17 at 7:36
  • 5
    $\begingroup$ Your answer - especially the picture - was a big help for me to come up with my answer with slightly improving that. Thanks! $\endgroup$ – elias Jan 30 '17 at 7:43
1
$\begingroup$

I'm not particularly experienced with proofs, but I think I have an idea of why (the number given in other answers) is minimal for the question asked:

Because the board is a square and the side length is a power of two, a line running through the midpoint of the side will never pass through a cell (always between two cells).

Consequently:

No matter which cell Alice removes, it will always be in one quadrant of the board. Similarly, no matter which position Alice asks for it to be in when reconstructed, it will always be in one quadrant of the board. Because Bob can rotate and flip the pieces, the remaining three quadrants are irrelevant and can be removed as a single piece.

This means that:

The board is now a 4 x 4 board, square, with a side length that is a power of two. Again there a line dissecting the board perfectly in half will not pass through any cell, horizontally or vertically, but always between two cells.

Again:

No matter which cell Alice removes, and where she requires the hole to appear in the reconstructed board, it will always be in one quadrant. The remaining three quarters of the smaller board are irrelevant and can be removed as a single piece.

This can continue until:

The cell removed represents one quarter of the remaining board (in this case, this is at this point, however on a larger board, this process would continue, similarly, if Alice cut a 2 x 2 piece from the board, this would occur after removing the first three quarters of the board). When the cell removed represents one quarter of the remaining board, this piece may be rotated or flipped into whichever orientation is required.

The cell removed...

Represents one sixty-fourth of the original board, and one quarter of the final piece. One sixty-fourth is one quarter cubed, which is I think the reason that three is minimal.

This approach could be scaled for any board size...

So long as the side length is a power of two times the side length of the cell(s) removed. I'm not sure how of how this would need to be changed if the board was rectangular, or if the side length was odd, for example (although I suspect it will be the largest integer number of cells less than half the rows/columns, so just slightly less than three-quarters, when removing pieces).

As I said, I'm not experienced/adept at proofs, but this seems to make sense as to the reason. Perhaps someone else can double-check my working?

EDIT: This is perhaps analogous to:

A guessing game, where the approach taken is to halve the possible range (assuming you're told "higher" or "lower") and then doing the same again, until reaching the number. In this case, we are constantly narrowing the cell location to a quarter of a quarter of a quarter (and so on, in the case of a larger board). As each piece is placed, it is rotated/flipped to position the empty space remaining in the correct quadrant of the quadrant being partially filled by the newest piece. This means that we are only able to section off three-quarters of the empty space at a time, which is why the cell(s) removed will represent a quarter of the square around the smallest piece.

$\endgroup$

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.