Universal dissection

Question

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.

Answer 1

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:

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.

Answer 2

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.

Answer 3

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:

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:

while I have stopped at covering just a half (except the last step, where I cover last 3 squares in a single L-piece).

Answer 4

Building on the answers by Elias and CiaPan... Elias gave this "binary search"-based answer.

But it's interesting to notice that we can also do it with this "unbalanced binary search":

Or even like these:

Or the two solutions with the red piece on the outside, which I'm too lazy to draw out.

I don't know if there are other solutions. I actually asked about the existence of other solutions (Cover 63 squares of a chess board, differently) before noticing that this question already existed.

Answer 5

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.