See also the
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
- 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
- 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
- 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
- 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
- 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
- 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
- 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?