Index

Discrete Mathematics Project
Counting Techniques/Probability Activity

Title

"Getting There From Here" (Jim Arnow)

Goals

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.

Abstract

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.

Problem Statement

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?

Instructor Suggestions

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.

Materials

"Getting There From Here" handout, pencils, scratch paper

Time

Problem discussion (5 min.), small group work (25 min.), class discussion (20 min.)

Mathematics Concepts

Discrete Mathematics

recursion, counting techniques, combinations, binomial theorem

Related Mathematics

Pascal's triangle

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)

Curriculum Integration

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.

Further Investigation

This activity could be extendted to a situation where the distances between points are not all the same, as in the traveling salesperson problem.

Variations/Comments

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.

Send your variations and comments to this Web page's editor

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.

Discrete Mathematics Project Counting Techniques/Probability Activity