Discrete Mathematics

Ice Cream Stands

Goal:
¬ Introduce a graph to represent a map of a city.
¬ Encourage students to experiment a variety of ideas to solve the problem .
¬ Ability to use a chart to “map” out a route
Standards:

Materials:
¬ Map of Iceberg (several copies)

Activity:
Instructions

1. Pass out copies of the map of “Your Town” and present the following to the students:

What you have in your hands is a map of the town of Iceberg. It's a somewhat unusual way to
draw a map. The lines on this map represent streets and the dots are street corners. The map doesn't
have any houses on it, but we do know that there is at least one house at each corner.

Iceberg would be a nice place to live, except for one problem: you can't get ice cream
anywhere in town. So John and Mary have founded the The Icicle & Iceberg Ice Cream Company
in order to do something about that. John and Mary want to do something good for their town, so
they are going to build ice cream stands all over town where people can go to buy ice cream. They
want it to be easy for the people to get ice cream. They also want to make money.

At first, John and Mary had hoped to put an ice cream stand on every corner, knowing how,
in the summertime , they would just rake in the money. But ice cream stands are expensive to build:
you have to buy all that lumber, and nails, and windows, etc. Then you have to put big freezers
inside them, and pay people to work in them all day, and so forth. It didn't seem possible to sell
enough ice cream to pay for ice cream stands on every corner.

They figured, however, that people would still eat lots of ice cream if they only had to walk
down the street to get it. Their second plan was to build the ice cream stands so that people could
get ice cream either right there on the corner where they live, or at the very most, have to walk
down only one street to find a corner where there was an ice cream stand.

Now, all they have to do is figure out where to put the ice cream stands.
1. Where should they put ice cream stands and explain your reasoning.
2. How many do they have to build?
3. What strategies did you use? How did you decide where the stands should be located.
4. Did you check to make sure everyone can get to an ice cream stand?
5. Why would someone want to create a map like this ?

Extension:

1. Have the students experiment with their maps and decide where they think the ice cream stands
should go. As students find configurations of ice cream stands that will serve all the houses, remind
them that the ice cream stands are expensive to build, and that Mary and John want to build as few
as possible. Ask if there's any way to rearrange their configuration of ice creams stands so that one
or more can be eliminated.

2. You can tell students that it is possible to build only 6 ice creams stands and serve all of the
houses in this town, or you can let them try to discover that this is the minimum on their own.

Ice Cream Algorithms

Goal:
Define and Introduce Algorithm
This activity takes a closer look at two of algorithms that can be used to solve the Ice Cream
Stands problem. The Brute Force Algorithm and The Greedy Algorithm.
Standards:

Materials:
Students List of solutions/patterns/ideas from Ice Cream Stands activity

Activity:
Description
Students have a chance to think about ways to evaluate the effectiveness and the efficiently
of an algorithm.

Instructions

1. Explain to the students that the reason why finding a solution to the Ice Creams Stands
problem was so hard is that problems like this are very hard in general. A set of step-by-step
directions for finding a solution to a problem is called an algorithm . No one has found a
good (fast) algorithm for solving problems like the Ice Cream Stands problem.

2. Tell students that you are going to take a look at the best algorithm known for solving
this problem. It's pretty simple : check every single possible way to arrange the ice cream
stands. When you've done that, pick the best one. This is called a Brute Force Algorithm .

3. Ask students whether they think that this plan for solving the problem will work out
well. Of course the answer depends on how many possibilities there are to check. Have
students discuss how they could find that out. You will need a different algorithm -- a stepby-
step recipe -- for checking all of the possibilities and making sure that none are left out.

4. Have students design an algorithm for checking all the possibilities for locating ice
cream stands in the town of Iceberg. How many possibilities will have to be checked? (This
is not an easy question to answer, but one well worth spending time on!

Discussion

1. Why do you suppose the Brute Force Algorithm was given that name?

2. Students are likely to suggest that the Brute Force Algorithm is acceptable because all
the possibilities could be checked by a computer. It is true that finding an algorithm that will
solve a problem is the first step to enlisting the aid of a computer in your work. Have the
students imagine that they have a computer that can find and check one possibility in one
second. With what size of graph or map does checking all the possibilities become
impossible in a reasonable amount of time?

3. Another kind of algorithm that mathematicians often look for when trying to find one
that will work for a problem is called a greedy algorithm . A greedy algorithm for the Ice
Cream Stands Problem would be to first find the intersection or intersections that have the
most streets coming into them, and put ice cream stands there. Then put ice cream stands at
the intersections with the next highest number of streets coming in to them, and so forth.
How does this algorithm work for the Ice Cream Stands problem? Will this algorithm
produce a minimum dominating set for the map of Iceberg ?

4. Have students review the strategies that they used when solving the Ice Cream Stands
problem. Do their strategies suggest other algorithms that might work? For problems like
this one, where there is no reliable "best way" to solve it, mathematicians usually try several
kinds of algorithm just to see what kinds of solutions can be produced. Sometimes those
solutions will give them ideas for other things to try. Sometimes they have to be content with
the best solution they can find, never knowing if there is a better one.

5. If mathematicians know more than one algorithm that might work, another thing that
they try sometimes is to switch back and forth from one algorithm to the other. Would an
approach like that work for the Ice Cream Stands problem?

6. Using Brute Force to solve a problem involves checking all the possibilities. Is it
possible to draw a map for the Ice Cream Stands problem where the number of possibilities
you would have to check is infinite?

More Ice Cream

Goal:
Understanding of counting methods .
Ability to organize Information.
Choice of organization ( Tree diagram, Brute force,…etc.)
Standards:

Materials:

Activity:
There are 31 flavors of ice cream at the one of the new ice cream stores Mary and John have
built. How many triple scoop cones can you make?

Organize your result in a table.   #flavors   #scoops

Discussion:
What is considered the same triple scoop?
Does order matter?
Is two chocolate scoops on the bottom and one vanilla the same as two chocolate on the top and one
on the bottom?
Do you notice any patterns?
Can you create a formula?

Extension:
If Each of Mary and John’s Ice cream Parlors have a unique house flavor. So parlor A has
Blueberry Ruffle and this is there 31st flavor, and Parlor B has Raspberry parfait for it’s 31st flavor
…etc. etc. How many different triple scoop cones can be made in the town of Iceberg? (Note, if you
have not done the first two icecream activities you need to know that the total number of stores is 6.

More discussion and Extension:
You noticed that the pattern shows up on Pascal's Triangle. So we can use
that information to see exactly what the function should be.

Notice that the nth term in your sequence appears in the (n+2)nd row, and in
the (n-1)st place in that row. Note that the top row in the triangle is
called the zeroth row , and the leftmost entry is called the zeroth place in
the row. So since the entries in Pascal's triangle are given by "P choose
K", the nth term in your sequence is "(n+2) choose (n-1)." The way we find
its value is by the relation

Solution 2:

Let's think about the number of ways you can choose the flavors, and divide
it into cases. Then we'll add to get the total number of ways.

Case 1: all three scoops are the same
It looks like we'll be able to have as many different configurations as there
are different flavors, so this term is just n.

Case 2: all three scoops are different
The number of ways to choose three different flavors from a set of n flavors
is "n choose three", i.e. n!/(3!*(n-3)!) = (n)(n-1)(n-2)/6.

Case 3: two scoops the same, one scoop different
There will be n ways to choose the flavor that has two scoops in our cone,
and then (n-1) ways to choose the other flavor (we can't choose the one
we've already used for the other two scoops!). So this is (n)(n-1).

These are all the possibilities that we can get. So we add them up, and
find that the total number of ways to choose these scoops is

n + n(n-1) + n(n-1)(n-2)/6.