Name Date Period

← CS Unplugged

CS Unplugged activity

Tourist Town

About 30 minutesSoloPencil

The map below shows the streets of Tourist Town. The lines are streets and the dots are street corners. Tourist Town is in a very hot country, and in summer, ice-cream vans park at street corners and sell ice-cream to visitors. You want to place vans so that everyone can reach one by walking to the end of their street, and then at most one block further. The question is: how many vans are needed, and which corners should they go on?

The one rule

A corner is covered if it has a van, or if a street connects it straight to a corner that does. Here’s a tiny four-corner loop, already solved:

Corners 1 and 3 (filled) have vans. Corner 2 connects straight to corner 1, and corner 4 connects straight to corner 1 as well, so both are covered. Every corner is covered using just 2 vans, and 1 van alone could never cover all four, since corner 3 doesn’t connect to corner 1 directly.

What to do

Work out how to place ice-cream vans on the street intersections below so that every other intersection is connected to one that has a van on it. Circle a corner to mark a van. Use as few vans as possible.

Ice Cream Vans

Number of vans you used:

Learn more: placing the fewest vans is called finding a minimum dominating set, and towns use the same idea to place the fewest mailboxes or fire stations.

What’s it all about?

Nobody knows a fast way to find the smallest set of van locations for a map like this one, and nobody has proved that a fast way is impossible either. The slow, sure way is to check every possible set of corners: with the 26 corners in Tourist Town, there are 2²⁶, or about 67 million, ways to place vans at all. Checking one setup a second, that’s around two years of checking, just for a town this size.

That’s the same shape of problem as the Poor Cartographer’s map coloring, and Muddy City’s harder cousin, the traveling salesperson: computer scientists call this whole family NP-complete. Nobody has found a fast method for any of them, and a fast method for one would give a fast method for all of them.

Solution

The minimum number of vans for Tourist Town is six, but it’s genuinely hard to find them. This solution shows how the puzzle above was built: start with the six small starred groups at the bottom, each of which obviously needs only one van (its open circle), then those get linked up with extra streets between the other corners to disguise where the vans belong.