Renata the robot packs boxes in a warehouse. Each box is a cube of side length 1
foot. The warehouse
oor is a square, 12 feet on each side, and is divided into a 12-by-12
grid of square tiles 1 foot on a side. Each tile can either support one box or be empty. The
warehouse has exactly one door, which opens onto one of the corner tiles.
Renata ts on a tile and can roll between tiles that share a side. To access a box, Renata
must be able to roll along a path of empty tiles starting at the door and ending at a tile
sharing a side with that box
Show that Renata cannot pack 95 boxes into the warehouse and still be able to access
any box.
foot. The warehouse
oor is a square, 12 feet on each side, and is divided into a 12-by-12
grid of square tiles 1 foot on a side. Each tile can either support one box or be empty. The
warehouse has exactly one door, which opens onto one of the corner tiles.
Renata ts on a tile and can roll between tiles that share a side. To access a box, Renata
must be able to roll along a path of empty tiles starting at the door and ending at a tile
sharing a side with that box
Show that Renata cannot pack 95 boxes into the warehouse and still be able to access
any box.
-
95 boxes means 144 - 95 = 49 empty tiles.
Most tiles need to connect to two empty tiles, so that a "corridor" is made for Renata. That means that most tiles can access at most two boxes.
The only exception is a tile at the end of a corridor. It only needs to connect to one other empty tile, so can access 3 boxes.
If we arrange the the empty tiles in a single line (one long corridor), there is only one end tile. We can gain an extra tile by adding a "Y" junction, but every "Y" junction tile touches 3 blank tiles (so only 1 box). In other words, adding "Y" juctions gains nothing.
But there are a few other tiles which can only access one box:
* The first tile is in the corner so can only access one box.
* the second tile touches two other empty tiles, and is on the edge, so can only access one box.
* Every time the corridor turns a corner, the two empty tiles adjacent to the corner share a box (draw a picture and you'll see why), so every corner removes one extra box which can be accessed.
So if there are n empty tiles and c corners, then the most boxes we can access is:
1 + 1 + 2(n-3) + 3 - c = 2n - 1 - c
n = 49.
We want 2n - 1 - c >= 95
=> 98 - 1 - c >= 95
=> 2 - c >= 0
=> c <= 2
In other words, if there are 2 or fewer corners to turn, this is achievable. For instance, if the array is 3*48 (instead of 12*12) then it can be done: have an empty corner tile, plus an empty corridor in the middle of 3 rows. That's 49 empty tiles, and every box is accessible.
But to access a 12*12 array, more than 2 corners are required. For a atart, to go around the perimeter, 3 corners are required. So it can't be done.
p.s. It can be done with 50 empty tiles. Just make a spiral.
Most tiles need to connect to two empty tiles, so that a "corridor" is made for Renata. That means that most tiles can access at most two boxes.
The only exception is a tile at the end of a corridor. It only needs to connect to one other empty tile, so can access 3 boxes.
If we arrange the the empty tiles in a single line (one long corridor), there is only one end tile. We can gain an extra tile by adding a "Y" junction, but every "Y" junction tile touches 3 blank tiles (so only 1 box). In other words, adding "Y" juctions gains nothing.
But there are a few other tiles which can only access one box:
* The first tile is in the corner so can only access one box.
* the second tile touches two other empty tiles, and is on the edge, so can only access one box.
* Every time the corridor turns a corner, the two empty tiles adjacent to the corner share a box (draw a picture and you'll see why), so every corner removes one extra box which can be accessed.
So if there are n empty tiles and c corners, then the most boxes we can access is:
1 + 1 + 2(n-3) + 3 - c = 2n - 1 - c
n = 49.
We want 2n - 1 - c >= 95
=> 98 - 1 - c >= 95
=> 2 - c >= 0
=> c <= 2
In other words, if there are 2 or fewer corners to turn, this is achievable. For instance, if the array is 3*48 (instead of 12*12) then it can be done: have an empty corner tile, plus an empty corridor in the middle of 3 rows. That's 49 empty tiles, and every box is accessible.
But to access a 12*12 array, more than 2 corners are required. For a atart, to go around the perimeter, 3 corners are required. So it can't be done.
p.s. It can be done with 50 empty tiles. Just make a spiral.