Communications of the ACM

Last byte

Upstart Puzzles: Ice Trap

By Dennis Shasha
Communications of the ACM, January 2016, Vol. 59 No. 1, Page 136
10.1145/2851212
Comments

Imagine a 500-square-by-500-square red/black ice checkerboard with walls along all four edges. A frictionless hockey puck is moving diagonally above the checkerboard in a northwest, northeast, southeast, or southwest direction (you do not know which or where the puck started) at a speed of one diagonal square in each time unit. And you want to trap it in a one-square-by-one-square location.

You can put up horizontal (east-west) or vertical (north-south) walls of any length across the checkerboard, but your total wall length is limited to some total T. In order to build your first wall of length L, you must wait at least ceiling (L/10) time units from the start of the game. To build any subsequent wall of length L′, you must wait at least ceiling (L′/10) time units from the time you built your last wall. Once you are allowed to put up a wall, it appears instantly. You may likewise tear down your built walls instantly at any time. If, as you attempt to put up a wall, the puck is in one of the squares the wall covers, then the wall will not be built (and you will be told the wall would have hit a puck). You can build a new wall after L/10 further time units.

If the puck hits one of your walls or a fixed wall, it will ricochet to the reflecting diagonal; for example, if the puck moves southeast and hits your north-south wall, it will ricochet in a southwest direction one square south of the square from where it hit the wall, while also changing the color square on the checkerboard from black to red or red to black.

We consider three detection scenarios:

Which wall, side, where, hit. If the puck hits any one of the walls you put up, you know which wall was hit, on which side, and where. But you do not learn when the puck hits the permanent side walls.

Which wall hit. If the puck hits any one of your walls, you know which wall was hit but not where the puck hit.

Know a wall was hit. If the puck hits any one of your walls, you know only that some wall has been hit but not which one.

For each of these scenarios, your goal is to confine the puck to a region of area one square by one square in as little time as possible (worst case), no matter where the puck began or which direction it was going initially.

How would you guarantee to confine the puck in a one-by-one square given only a length of 502 squares in wall length in the most difficult scenario (the second one)?

Solution. The following solution sketch is due to NYU freshman Dan Simon. Let us fix the southwest checker square to be (0,0), where the first coordinate represents the north-south direction. After waiting 50 time units, put up a north-south wall from (0,1) to (499,1). The puck will eventually hit that wall. If it hits soon after again, then you have trapped the puck in the narrow alleyway between (0,0) and (499,0). Otherwise the puck is traveling east, so 50 units later, you can tear down that wall and put up another from (0,53) to (499,53). That wall will reflect the puck back. You can then tear down that wall, and 52 time units later, you can put up a new wall from (0,1) to (499,1).

You have now trapped the puck in an alleyway of one-unit thickness. Now put a single barrier at (250,0). The puck will hit it in at most 500 time units. Now put up a barrier at (252,0). If the puck hits it, you have trapped the puck. Otherwise, put up a barrier at (246, 0) and at (248,0) after the puck hits.

Upstart 1. The minimum conceivable wall length that could be sufficient is three checkerboard squares if you could somehow force the puck into a corner with the fixed walls. Can you indeed trap the puck that way? If not, what is the minimum length you need to trap the puck and how?

Upstart 2. Find optimal worst-case guarantees in all three detection scenarios for the minimum wall length.

Back to Top

Back to Top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2016 ACM, Inc.

---

No entries found