Optimization-Doing More with Less

Dig That!

Imagine a road grid with seven rows as in Figure 1-11.

Figure 1-11: Somewhere between Start and End in this road network is an eight-block tunnel some bad guys have built.

Some bad guys have placed a tunnel from the bottom, beginning at the intersection marked Start in the south, and ending at End in the north. The tunnel follows the path of the roads somehow but may wind around. It is also a simple path (no dead ends and no loops along the way). You want to probe a minimum number of times and yet be able to find the exact route of the tunnel.

A probe device takes an hour to set up. We can set them up at intersections or in the middle of the street. If you establish a probe on a street, you can tell whether the tunnel follows the street. If you set the probe up at an intersection, you can tell whether the tunnel passes through the intersection, and, if so, according to the engineering team, which adjacent streets it goes to.

1. If the tunnel is at most eight blocks long and begins at Start and ends at End, then what is the minimum number of probe devices you would need to guarantee to determine the precise route of the tunnel in one hour?

2. If you had only one probe, what is the minimum time it would take to guarantee to determine the outcome, assuming you could move the probe every hour?

Suppose all a probe could tell was whether a tunnel ran under it or not, but could not tell the direction. In the engineering jargon, suppose we had point probes rather than directional probes.

3. If the tunnel is at most eight blocks long and begins at Start and ends at End, then what is the minimum number of point probe devices you would need to place to guarantee to determine the precise route of the tunnel in one hour?

Hint: 

Remember that you can place probes at intersections or in the middle of streets.

Suppose you have two hours, but you are not allowed to reuse any probe?

4. How few point probes could you use over two hours to guarantee to find the tunnel?