Index

Discrete Mathematics Project
Counting Techniques/Probability Activity

Title

"Getting There From Here" (Jim Arnow)

Goals

  1. Students will explore a situation which requires enumeration of a set of possibilities.
  2. 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

  1. 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.
  2. 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.
  3. After the small groups have had time to explore the problem, return to the large group and share results.

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:
  1. An algebra class where students are working with the binomial theorem.
  2. Any class which has previously included a discussion of Pascal's triangle.
  3. 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

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.


Last updated January 15, 1997