The map of the town that is used in the activities is a collection of dots and lines that mathematicians call a graph . (Graphs are described, along with some of the terminology that is used for talking about them in Games on Graphs .) You may want to refer to that information if you are not already familiar with graphs such as these--they are made up of dots and lines, and unrelated to graphs that chart information with which you are undoubtedly familiar.
The technical term for an optimal solution to the Ice Cream Stands problem is a minimum dominating set . The problem itself is probably best understood in the form of the ice cream stands story itself. If the dots are houses and the lines are roads, then what is the smallest set of locations to put the ice cream stands so no one has to walk down more than one street to get to one? A set of dots or vertices where the ice cream stands go in a solution to this problem is called the dominating set.
A dominating set for a graph is easy enough to find. But ice cream stands are expensive to build--as are warehouses, "hub" airports, electrical switching stations, etc. So it is that many situations which involve planning the location of important facilities can be modeled by a graph for which we ask the question, "What is a minimum dominating set?" We want the one with the smallest possible number of members. It turns out that for an arbitrary graph or map, there is only one reliable step-by-step procedure that you can use to find a minimum dominating set, and that is to check every possible combination of vertices to see if it is a dominating set. When you find a dominating set that might be minimal, there is not always a way to be sure it is unless you check all the possibilities for a better solution.
Is checking all the possibilities so bad? Couldn't you get a computer to do it? A computer can certainly find one possibility extremely quickly. This does not mean, however, that the computer can find and check all the possibilities in a reasonable amount of time. To know if that can be done, you have to know how many possibilities there are. The number of possibilities will vary with the size of the graph: the more vertices it has, the more possibilities there will be. But how many more? This question belongs to a branch of mathematics concerned with computatonal complexity.
The best way to try and figure out how many possibilities there might be is to look at some examples, beginning with some very small ones, and try to find some kind of trend or pattern in the way the possibilities grow with the size of the graph.
A graph with only one vertex is trivial: there is one possibility. For a graph with two vertices, you could place ice cream stands on both vertices, or on one or the other, so there are three possibilities. For a graph with three vertices, you have to count the number of possibilities for each quantity of ice cream stands that is possible to use. There is only one way to arrange three ice cream stands, of course. How many ways to arrange two? One?
For a graph with four vertices, you continue in the same way, only there will be even more possibilities. It takes a lot of careful counting to begin to get a feel for how the numbers grow. Generally speaking, the number of possibilities to check grows at a much faster rate than the number of vertices in the graph. This kind of growth is called exponential . There are some problems that mathematicians and scientists would like to solve whose solutions are minimum dominating sets, but the graphs are large enough that it would take a fast computer years and years to produce a solution--longer, perhaps than the estimated age of the universe!
The fact that the Ice Cream Stands puzzle appears to be so difficult to solve allows us to use it to play with the idea of a one-way function . In the Ice Cream Stands Problem you can explore this idea by seeing how a person can create puzzles like these with the solution in mind first, but completely disguise the solution by the time the puzzle is finished. If you go from the solution to the puzzle, a good solution is always known to the maker of the puzzle. But you can't go the other way with such ease. (Another example of a one-way function is finding the prime factors of a large number. You can look up two large prime numbers from a table in a book, multiply them together and ask someone else to find the factors and they will most likely have a very hard time indeed!)
Of course this one-way trick isn't going to help someone who is trying to figure out where to locate the big and little computers in a large interconnected computing system, because no one created that problem with the solution already in mind! One-way functions are important, however, in cryptography , the mathematics of secret codes and secure passwords. If you had a clubhouse with a huge graph on the door, and only members knew what the minimum dominating set for the graph was, the minimum dominating set could be the password because the chances of someone else figuring it out would be slim.