See also the
Dr. Math FAQ:
Browse High School Discrete Math
Stars indicate particularly interesting answers or
good places to begin browsing.
Selected answers to common questions:
Four-color map theorem.
How many handshakes?
Squares in a checkerboard.
- Graph Theory [09/29/2001]
Why is a graph with five vertices, each having a degree of 3, impossible?
- Graph Without Crossing Lines [7/19/1996]
There are three houses and three utilities: how do you connect each of
the houses individually to the three utilities without crossing your
- Greatest Integer Functions [09/27/1998]
Can you help me solve for the graph of [y]=[x], where  is the greatest
- How Many are in the Group? [10/17/1996]
Everyone in the group had been to at least one of the parks...
- How Many Balls Would Be Used? [5/8/1995]
Consider a knock-out tournament, say tennis or ping-pong, with n
participants. The winner of any game goes on to the next round and the
loser retires...How many balls have been used in the tournament?
- 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?
- How Many Factors? [7/14/1996]
How do you find the number of factors for a number?
- How Many Games in the Tournament? [01/15/2002]
There are eight teams in a single-elimination tournament. Each team gets
to play until it loses. How many games will be played in the tournament?
- How Many Threes? [06/12/1999]
If all the numbers from 1 to 333,333 are written out, how many times will
the digit 3 be used?
- 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.
- Infinity Hotel Paradox [09/15/1999]
How can a hotel with an infinite number of rooms, all already occupied,
accommodate the passengers of an infinite number of buses without
doubling them up?
- 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
- Josephus Problem [04/18/2003]
Every other person at a table is eliminated until there is only one
person left. Who is the survivor?
- Karnaugh Maps [05/07/2000]
What are Karnaugh maps? How are they used?
- Knights of the Round Table [07/01/1998]
If x knights are sitting at a round table, and every other one is
removed, who is the last one left sitting at the table?
- The Königsberg Bridge [5/20/1996]
Do you have information on Konigsberg's bridge?
- Lattice Points and Boundary Lattice Points [08/30/1998]
What is an interior lattice point and a boundary lattice point of a given
shape (triangle, circle, rectangle, etc.)?
- Like Looking for a PIN in a Hamiltonian [10/27/2011]
If a door secured by a numeric keypad checks only the last four digits entered, what
would it take to bypass it? Doctor Vogler responds with an introduction to digraphs and
Hamiltonian paths, then suggests starting with a simpler version of the question,
looking for patterns that emerge from those simplified cases -- and studying the de
- Line Drawn through Lines Puzzle [10/18/2001]
Given a box made up of 16 lines, with two rectangles above and three
squares below, draw a line through each line without crossing any line
- Lines determined by 5 points [11/13/1994]
How many lines are determined by 5 points, no three of which are
- Locker Problem [11/21/1997]
There are 1,000 lockers numbered from 1 through 1,000. The first student
opens all the doors; the second student closes all the doors with even
- Making Heads or Tails of Binary Proofs [03/17/2011]
Can 5 tails-up coins become all heads-up by turning them over 2 at a time? If the total number of coins and turned coins changes, what patterns emerge? Doctor Tom introduces mathematical invariants and monovariants to confirm a student has understood that these questions seek proofs -- and that she has started down the right path of proving the possibility (or impossibility) of certain states.
- 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.
- Math Logic - Determining Truth [04/13/1999]
A number divisible by 2 is divisible by 4. Find a hypothesis, a
conclusion, and a converse statement, and determine whether the converse
statement is true.
- Matrix Multiplication [12/18/1998]
Why does matrix multiplication work? Why are the rows multiplied and
added with the columns?
- Meaning of '-ominoe' [11/07/2001]
We are drawing pictures of dominoes, triominoes, tetrominoes, and
pentominoes. What is the meaning of the root "ominoe"?
- Minimum Number of Cuts to Slay the Dragon? [01/14/2007]
A magic dragon has 3 heads and 3 tails. A knight with a magic sword
can make four types of cuts--one head, two heads, one tail, or two
tails. For each type of cut, the dragon regrows one head, nothing,
two tails, or one head respectively. The knight must remove all
heads and tails to slay the dragon. What's the fewest number of cuts
he can make?
- Moving Knights on a Chessboard [01/27/1999]
Given 4 knights at the 4 corners of a 3-by-3 chessboard, can the knights
exchange places if they can move only in the following way?
- Multi-Dimensional Four-color Theorem [08/08/1997]
Has any work been done on theorems like the four-color theorem for
- The N-Color Theorem? [07/27/2002]
What happens if we try to generalize the Four Color Theorem to other
numbers of dimensions?
- New School Lockers [01/28/2001]
Which locker was touched the most?
- Nim [09/26/2000]
What is the principle of Nim and what is its application?
- 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?
- Number of Unordered Partitions [08/18/1999]
Is there a formula for the number of unordered partitions of a positive
- Number of Ways to Move [1/30/1996]
I have a group of squares which together form a larger square. In how
many ways can you travel from the upper left corner of the large square
to the lower right corner by only going down or to the right?
- Number Systems: Two Points of View [06/30/1998]
What are the number systems?
- Number Theory Proofs [06/24/1999]
How can I prove that the equations (x,y) = g and xy = b can be solved
simultaneously if and only if g^2|b for integers g, b?
- Objects in a Pyramid [7/8/1996]
Objects are stacked in a triangular pyramid... how many objects are in
the nth layer from the top?