Discrete Mathematics Project
Counting Techniques/Probability Activity
"Getting There From Here" (Jim Arnow)
- Students will explore a situation which requires enumeration of a set of possibilities.
- Students will work in small groups to develop appropriate methods for counting possible routes.
This activity requires students to determine the number of different routes of shortest length that connect two points in a city with streets arranged in a square grid. The number of routes can easily be counted for two points which are close together. To extend the method to points which are not close together, the students must generalize a formula for any two points. The solution closely parallels the binomial theorem and Pascal's triangle.
A bicycle messenger has to get from one corner in a city to another. If the messenger takes the shortest route, and travels only along the streets, how many different routes can the messenger take from one location to the other?
- Spend very little time discussing the problem. The students should see quickly what is being asked. Divide them into small groups and allow them to start working on the problem.
- It may work well to allow the students to experiment individually with the problem before starting any small group discussions. The students may come up with different methods which they can compare and contrast.
- After the small groups have had time to explore the problem, return to the large group and share results.
- A possible solution if the messenger needs to go s intersections South and e intersections East:
The situation can be reformulated as the number of ways of creating a word with s + e letters in it, s of which are "S" and e of which are "E." This is C(s+e,s) (or C(s+e,e).) Each letter of these words represents the direction the messenger headed at each intersection. For instance, the word "SEES" can be interpreted as a trip which goes South one block, East two blocks and the finally South one block.
"Getting There From Here" handout, pencils, scratch paper
Problem discussion (5 min.), small group work (25 min.), class discussion (20 min.)
recursion, counting techniques, combinations, binomial theorem
NCTM Standards Addressed
Problem Solving, Communication, Reasoning, Connections (within Mathematics), Discrete Mathematics
Colorado Model Content Standards Addressed
Number Sense (1), Algebraic Methods (2), Data Collection and Analysis (3), Problem Solving Techniques (5), Linking Concepts and Procedures (6)
This activity could be integrated into:
- An algebra class where students are working with the binomial theorem.
- Any class which has previously included a discussion of Pascal's triangle.
- Any math class which includes an emphasis on problem solving.
This activity could be extendted to a situation where the distances between points are not all the same, as in the traveling salesperson problem.
- The city blocks can be modified in a number of ways to increase the challenge: for instance a four block park pond could be put in the middle, or some of the streets could be one way.
- The messenger could only be allowed to take right-hand turns.
- The route could be allowed to be slightly longer than the shortest possibles route.
References, Resources and and Related Web Links
Crisler, N., Fisher, P., & Froelich, G. (1994). Discrete Mathematics Through Applications. New York: W. H. Freeman and Company.
Dossey, J., Otto, A., Spence, E., & Vanden Eynden, C. (1993). Discrete Mathematics. Harper Collins College.
Tucker, A., (1984). Applied Combinatorics. New York: John Wiley & Sons.
Peressini, et al. (1992). Precalculus and Discrete Mathematics. Glenview, Illinois: Scott, Foresman and Company.
Last updated January 15, 1997