DM-Problems

From

Here is a list of simply-stated problems that fall under the rubric of discrete mathematics:

Contents 1 Vertex-edge graphs 2 Combinatorics 3 Iteration and recursion 4 Social choice 5 Information

Vertex-edge graphs

• Which way of connecting a number of sites into a network involves the least cable?
• What's the best route for a robot to pick up items stored in an automated warehouse, or for a courier to collect deposits from all ATM machines in some assigned region?
• What is the smallest number of colors needed to color the 48 states in the continental United States if states that share a border must be colored with different colors (so that all borders can be clearly distinguished)?

Combinatorics

• How many different pizzas can you have if each pizza must have at most three of the eight available toppings?
• How many tickets do you have to buy to make sure that you have a winning ticket in the contest that involves correctly selecting six numbers from 1 to 36?

Iteration and recursion

• What should be the daily dose of medication if, to function effectively, the medication must be at a specified concentration and if a given percentage of the medication in the body is eliminated each day?
• If the population of deer increases by 10% each year, how long will it take the population of deer to double?

Social choice

• What is the best system for reapportioning the 465 seats in the United States Congress among the states after each census? What system is actually used?
• What is a good strategy for dividing up a pie among three people so that each is satisfied with the portion he or she receives?

Information

• What is the quickest way of alphabetizing a list of 1000 names -- on index cards, or in a database?
• How are transmission errors detected and corrected when coded versions of pictures are sent from space?

(This list appears in "Discrete Math in 21st Century Education: An Opportunity to Retreat from the Rush to Calculus" by Joseph G. Rosenstein, which appears in Foundations for the Future in Mathematics Education, edited by Richard Lesh, Eric Hamilton, and James Kaput. Hillsdale, NJ: Lawrence Erlbaum, 2007.)