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:
7  I. MATHEMATICAL REASONING 
Apply skills of mathematical representation ,
communication and four content strands. 

7  IV. DATA ANALYSIS, STATISTICS AND PROBABILITY 
A. Data and Statistics 
Represent data and use various measures associated with data to draw conclusions and identify trends. 
7  IV. DATA ANALYSIS, STATISTICS AND PROBABILITY 
B. Probability  Calculate and express probabilities numerically and apply probability concepts to solve real world and mathematical problems. 
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:
7  I. MATHEMATICAL REASONING 
Apply skills of mathematical representation,
communication and four content strands. 

7  IV. DATA ANALYSIS, STATISTICS AND PROBABILITY 
A. Data and Statistics 
Represent data and use various measures associated with data to draw conclusions and identify trends. 
7  IV. DATA ANALYSIS, STATISTICS AND PROBABILITY 
B. Probability  Calculate and express probabilities numerically and apply probability concepts to solve realworld and mathematical problems. 
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 stepbystep
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:
7  I. MATHEMATICAL REASONING 
Apply skills of mathematical representation,
communication and four content strands. 

7  IV. DATA ANALYSIS, STATISTICS AND PROBABILITY 
A. Data and Statistics 
Represent data and use various measures associated with data to draw conclusions and identify trends. 
7  IV. DATA ANALYSIS, STATISTICS AND PROBABILITY 
B. Probability  Calculate and express probabilities numerically and apply probability concepts to solve realworld and mathematical problems. 
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 (n1)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 (n1)." 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!*(n3)!) = (n)(n1)(n2)/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 (n1) 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)(n1).
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(n1) + n(n1)(n2)/6.
Prev  Next 