A Fresh Irregular-Chessboard Puzzle
One of my all-time favorite puzzles is about tiling a chessboard with 1-by-2 dominoes. But the chessboard is special: two cells at the opposite corners are removed. A similar elegant chessboard puzzle recently appeared on Facebook.
Puzzle. Our special chessboard has one corner cell removed. On each of the remaining cells, there is an ant. At a signal, each ant moves two cells horizontally or vertically (for example, an ant can move from b3 to b5). Is it possible that after all the ants perform their move, each of the 63 cells will have an ant?
This puzzle is a variation of another puzzle, where all the setup is the same, but each ant moves only one cell horizontally or vertically. You can start with this variation, as it is easier.
Share:
Grant Stenger:
I love this. Another variation that I’ll never forget from a trading interview is “Can you pack 53 bricks of dimensions 1 x 1 x 4 into a 6 x 6 x 6 box?”
7 February 2023, 2:01 pmCarl Feynman:
No. The ants are constrained to move to cells with the same parity in x and y. We can just consider the pattern of the ants whose parities match one of the removed squares. There are fifteen such squares. Now think about the paths followed by chains of ants who take the places of the next ant in the chain. In order for the ants to take up every square, such chains must form loops. A loop on a square grid must be of even length. But an odd number like fifteen cannot be a sum of even numbers.
8 February 2023, 10:56 amBruce Fleischer:
The first aha is finding the right coloring pattern. For the ants, Carl’s 15 squares form a 4×4 board (less one corner) on which ants move one space. With usual chess coloring, (x+y) mod 2, all ants move to the opposite color, but there are eight squares of one color and only 7 of the other.
Grant’s puzzle is very nice, with at least two aha moments. Use 4 colors for 1x1x1 cells inside the box, assigned by (x+y+z) mod 4. Then, a brick occupies one cell of each color regardless of placement. The coloring partitions the cells into sets of sizes 53, 55, 55, 53. So if 53 bricks can be packed, every one of the cells with the 1st and 4th colors must be occupied. Next, the box can be rotated to put any of its 4 long diagonals along the line (0,0,0)-(6,6,6). These rotations generate different colorings. Any packing will leave 4 empty 1x1x1 cells. For any cell you try to leave unoccupied, one of the colorings has that cell in a set of 53, so that cell must be occupied. This contradiction implies there is no such packing.
8 February 2023, 9:11 pmrosie:
Grant’s problem: Partition the 6x6x6 box into a 3x3x3 array of 2x2x2 cubes. Colour the cubes alternately black and white, starting with black. Each brick occupies 2 black and 2 white, thus all 53 occupy a total of 106 of each. But there are only 13*8=104 white cells.
9 February 2023, 10:37 amCyber K:
Grant’s puzzle also nice.
One of my favourite “tiling” puzzles was given in a high school state championship in one of the former Yugoslavia countries in the 90s:
“You have triominos – L-shaped 3-square dominoes. Prove that any 8×8 board with one tile missing anywhere can be covered with triominos”.
The actual problem was slightly different but I feel it’s easier in a sense. It needs a small aha moment.
9 February 2023, 9:49 pm