Sometimes it is possible to be certain that there is no better solution to
the Ice Cream Stands problem than the one you have can be found. This
activity explores some of the ways that students can find this out.
Have students look at the map of Twotown
. If
Ivan and Ivana Icicle were tyring to figure out where to put the ice cream
stands in Twotown, they would probably not have too much trouble.
Have students figure out where the ice cream stands should go. Make
sure the whole class agrees on a solution. (Students will see that
Twotown is aptly named!)
Have the students explain why they are sure there is no solution
to the Twotown puzzle that will only use one ice cream stand.
With contributions from all members of the class, write a
statement on the board that explains why the solution for Twotown must
have more than one ice cream stand. Be sure that all students understand
the statement and agree on the wording. Will this statement stand as proof that two ice cream stands is the best
possible (the minimal solution?
Have the students look at the map of Puzzzletown
and solve the Ice Cream Stands Puzzle for this map.
Tell the students that, just as with Twotown, there will come a
point when they are trying to reduce the number of Ice Cream Stands
that they use, where they will see it is impossible to use any
fewer Ice Cream Stands.
Have the class again collaborate to compose a clear explanation of
why the solution they have found for Puzzletown is the minimum. The
chain of reasoning to do this is more complicated than what was
required for Twotown. Some students are likely to grasp the reason
before others do. Remind students as they try to convince one another
that they are trying to base their explanations on logical, true
statements--even if they feel more inclined to impassioned
persuasion.
Invite the students to try other dominating set puzzles to see if
they can always be so sure their solution is the best one.
Discussion
What was it that made you realize that two ice cream stands would
be enough for the Twotown puzzle? Did you
find it difficult
to put your understanding into words? Did you need to invent any special
words to make everything more clear? Were there phrases that you used
that ended up being useful?
Most people find the Puzzletown problem harder than the Twotown
one. Was that your experience? What could be the reason for this?
What was necessary to make it clear that you had found the
Puzzletown
solution that was the best one? How was this different from what you
needed to show that your Twotown solution was the best?
To verify the Puzzletown solution, you have to hold a lot of
information in your head all at once. Do you find that hard to do? What
tricks did you use to help yourself do that?
Talk about how difficult it is to explain something to someone who
hasn't understood it in the same way as you do, and how difficult it
is to try to understand something that someone else is explaining to
you. Make a list of ideas that would be good advice for everyone who
is either struggling to explain or struggling to understand.
The original Ice Cream Stands Puzzle for the map of Iceberg can be solved using no more than 6 ice
cream stands. You can demonstrate that it is impossible to use less than
6. It takes some experimentation and careful thinking, but it can be done.
Discovering it will make you feel triumphant!
It would be nice if we could always be sure that our solutions to
these problems were the best, but this is not the case. Do you have
any ideas about what details in the problem will make it so that you
can verify that your solution is the best one? What details in the
map might make this difficult to do?
