Ask Dr. Math

College Archive

Browse College Discrete Math

Stars indicate particularly interesting answers or good places to begin browsing.

---

Mobius Strips and the Six-Color Map Theorem [12/16/1998]

An extension of the four-color map theorem to the mobius strip, i.e. the six-color map theorem.

Average Age at a Party [10/27/1999]

How can I find b+g if the average age of b boys is g, and the average age of g girls is b, and the average age of everyone, including the 42-year- old teacher, is b+g?

Bell Numbers [08/29/2001]

I am looking for the formula for the number of different groups we can split a group of n different items into - order does not matter.

Binary Search Trees [02/06/2003]

Which of the following sequences represent(s) an order of insertion that will result in a binary search tree where each node in the tree has the same number of nodes in its left and right subtrees?...

Breadth-First Search and Girth [11/13/2000]

How can you use a breadth-first search to compute the girth (length of shortest cycle) of a graph?

Checkerboard Chase [12/13/2002]

Player A begins by placing a checker in the lower left-hand corner of a checkerboard (8 by 8 squares). Player B places a checker one square to the right or one square up or one square diagonally up and to the right of Player A's checker... Would you rather be Player A or Player B?

Circle Chords [11/4/1994]

Place n distinct points on the circumference of a circle and draw all possible chords through pairs of these points. Assume that no three of these chords pass through the same point. Find and solve the recurrence relation for the number of interior intersection points formed inside the circle.

Climbing 100 Steps [05/01/2003]

Find the number of ways in which you can climb 100 steps if you can go up 1 or 2 steps at a time.

Condorcet Criterion [02/13/2002]

Please explain the "Condorcet candidate" when using various ways to determine a winner in an election.

Covering a Checkerboard after Removing a Random Square [05/11/2008]

Use mathematical induction to prove that for any positive integer n, if any one square is removed from a 2^n x 2^n checkerboard, then the remaining squares can be completely (and exactly) covered with L-shaped pieces composed of three squares.

Creating a Payoff Matrix [06/04/2003]

Shoe Town and Fancy Foot are both vying for more share of the market.

DeBruijin Diagrams/Shift Register Graphs [10/30/2001]

My specific problem is how to graph D(3,3) and then come up with a shift register sequence from that graph.

Dinner Triplets [10/23/2000]

A woman has 15 friends. For 35 days she wants to have dinner with 3 friends a day, arranging it so that each pair of friends will come only once. Is this possible?

Elect a Spokesman [07/02/2002]

The 23 prisoners and the 'switch room.'

Equivalence Relations [02/10/2003]

For integers m and n, define m~n if n|m^k and m|n^k for some positive integers j and k.

Finding Formulas for Number Sequences [11/22/1997]

My question is about trying to find a formula between numbers.

Finding Pairs of Intersecting Chords [07/24/2000]

Consider n chords on a circle, each defined by its end points. Describe an O(n*ln(n)) algorithm for determining the number of pairs of chords that intersect inside the circle.

Finding the nth Term [03/28/2002]

My formula works with the exception of the first term.

Four-Color Map Theorem [4/3/1995]

I hear the Four-color map theorem was either proved or disproved and that extensive computer effort was required....

Four Colors, Eighths of a Circle [10/15/2001]

Divide a circle in eighths. Use 4 colors to color the segments. Colors may be repeated as long as you use all 4 colors at least once. What are the total combinations possible?

Generating Eight-Character Passwords [03/08/2002]

Given some restrictions, calculate the number of possible 8-character passwords.

Graphs - Proving the Infinite Ramsey Theory [11/10/1997]

In a graph with infinite "points," if we colour the lines with two colors we'll have either a red or a blue infinite chain of lines, an infinite number of points, all of them joined to each other with the same colour...

Graph Theory [02/25/1997]

Prove that the maximum number of edges in a graph of order n without an even cycle is [3/2(n-1)].

How Many Digits in Graham's Number? [11/11/2005]

I have heard that Graham's number is the largest number with mathematical use. I have seen it expressed in arrow notation but that does not give me a sense of how large it is. Is there a way to express the number of digits it contains?

How Many Distinct Patterns? [01/15/2001]

Given a large equilateral triangle divided into four smaller equilateral triangles, if two edges are painted white and the rest are painted black, how many distinct patterns are possible?

The Hungarian Job Assignment [03/10/2011]

A company owner writes in for help cost-efficiently assigning tasks to different employees when each one commands her own fee for every job. Invoking a little graph theory, Doctor Jacques introduces the Hungarian algorithm and walks through an application to an example assignment.

Induction Hypothesis [08/16/2003]

Every road in Sikinia is one way. Every pair of cities is connected by exactly one direct road. Show that there exists a city which can be reached from every other city either directly or via at most one other city.

Integer Solutions of ax + by = c [04/03/2001]

Given the equation 5y - 3x = 1, how can I find solution points where x and y are both integers? Also, how can I show that there will always be integer points (x,y) in ax + by = c if a, b and c are all integers?

Inverse, Product of Permutations [04/27/2002]

I don't understand how to calculate the inverse or the product of permutations.

Karnaugh Maps [05/07/2000]

What are Karnaugh maps? How are they used?

The Königsberg Bridge [5/20/1996]

Do you have information on Konigsberg's bridge?

Matching Invoices with Report Totals [10/31/2000]

I have 14 invoice values and 2 report totals. The sum of the invoices for each report should be the report total. Is there a fast way of finding which invoices go with each report, or determining if it is even possible?

Math Games Involving Forcing an Opponent into an Outcome [06/19/2004]

A very challenging math game provides the background for a discussion of how to find the winning strategy in 'reduced state' games, where players attempt to force a final outcome after a series of moves.

Maximizing the Number of Rectangles [10/26/2000]

How can I cut a rectangular sheet of paper into a maximum number of smaller rectangles of a given size? Is there an algorithm for this?

Maximum Area Given Enclosing Lengths [11/21/2001]

I am given the lengths of a set of N line segments and I am supposed to calculate the maximum area that can be enclosed using them. Is there an efficient method of finding the solution?

The N-Color Theorem? [07/27/2002]

What happens if we try to generalize the Four Color Theorem to other numbers of dimensions?

No Three Red Beads Together [09/16/2001]

Given 10 beads on a necklace, 6 white and 4 red, how many ways can the beads be arranged so that no three red beads are together?

Number/Color Cube [09/13/2001]

You want to make a number cube by putting the numbers 1,2,3,4,5,6 on the face. 1/5, 3/6, and 2/4 must be on opposite faces. Each face is a different color. How many ways can you make the cube?

Numbers Identical in Base 10 and Base 3 [02/14/2001]

Find all base-10 numbers that, when multiplied by eight, have exactly the same digits as their base-3 counterparts.

Numeric Combinations of Pi and Sqrt(2) [09/25/2005]

Say I am given a number X = A*[sqrt]2 + B*[pi], where A and B are integers. For a given X, how can you find A and B?

Page:  1  2 [next>]