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.
- Contrapositive, Converse, Inverse [06/10/1999]
How can I write the contrapositive, converse, and inverse of and prove or
disprove the statement, "If m + n is even, then m and n are even"?
- Counting Rationals and Integers [10/06/1999]
How can you prove that the set of rational numbers is the same size as
the set of integers?
- Determining the Winner of a Tennis Match [10/9/1995]
How many matches will it take to determine the champion in a tennis
tournament that started with 89 players?
- Finding and Factoring Large or Mersenne Primes [02/22/1998]
How do you find extremely large primes (Mersenne Primes) and how do you
tell if they are prime? What is the most efficient way of factoring
- Finding Primes: Sieve of Erastosthenes [4/1/1996]
Could you please elaborate on this subject a little more?
- Formula for Nim [02/22/2002]
Is there a formula for the game of Nim?
- Formula for Squares inside Rectangles [06/29/2003]
Is there an equation for how many squares there are in a rectangle
divided up into 1cm blocks?
- 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.
- Relations and Equivalence Classes [01/10/1999]
Can you help me prove the following relations are equivalence relations
and find the equivalence classes?
- Reversing a Number by Multiplying by 9 [08/23/99]
When some numbers are multiplied by 9, why is the result the reverse of
the original number?
- Taxicab Geometry; Dispatching the Closest Cab [09/06/1998]
Greta wants to dispatch a taxi from the garage closest to the caller.
Which garage would be closest if garage A is six blocks east of B...?
- Team's Final Score [7/10/1995]
The rules of a certain game allow a team to score either 3 points or 8
points. A team's final score will be any combination of these points.
Which numbers cannot be a team's final score?
- Truth Tables and Computer Circuits [01/17/2000]
Can you please explain how to read and draw computer circuit diagrams,
how to form truth tables from reading the diagrams, and the logical
arguments behind this?
- 15 Ball Players [12/07/2001]
15 softball players, each with one ball, stand so that players in each
pair has a different distance between them. Each player throws his ball
to the player who is the closest. Prove that no player receives more than
5 balls, and generalize.
- Algebra Paper-Folding Problem [02/10/1999]
Fold a paper x times in half, keeping the creases perpendicular to the
longest edge. Find an equation for the number of intersections in terms
- Are They Wearing Seatbelts? [3/26/1995]
80 percent of all California drivers wear seatbelts. If 4 drivers are
pulled over, what is the probability that all 4 will be wearing their
- 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?...
- Binomial Theorem by Induction [7/14/1996]
I'm trying to prove the Binomial Theorem by Induction, but I'm having
trouble going from the hypothesis step to the n+1 step.
- Boolean Algebra Proofs [09/25/1999]
Prove the Boolean expression ab + bc + ca' = ab + ca'; also, prove using
contraposition that 2(q^2) does not equal (p^2) when p and q are
- 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?
- Bulgarian Goats [05/17/2003]
How many goats are there in the herd? What are the sizes of the
feeding groups once they have stabilised? Find at least two possible
cyclic patterns of sizes.
- Buying Doughnuts [03/22/2002]
Janine wants to buy three doughnuts, and there are five varieties to
choose from. She wants each doughnut to be a different variety. How many
combinations are there?
- 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
- Choosing a Duet, Lead Singer/Backup [02/25/2002]
Twenty singers are trying out for a musical. In how many different ways
can the director choose a duet? In how many ways can the director choose
a lead singer and a backup?
- A Circular Massacre [09/25/1998]
Ten thousand sailors are arranged in a circle; starting with the first
one, every other sailor is pushed overboard ....
- Coin Tosses, Dealing Cards... [12/08/1998]
Several questions on discrete math - probability and combination;
deducing recurrence relations.
- Combinatorial Proof [6/13/1996]
Please prove this combinatorial proof.
- Condorcet Criterion [02/13/2002]
Please explain the "Condorcet candidate" when using various ways to
determine a winner in an election.
- Congruence of Integers [08/10/1998]
Can you help me find the remainder when 5 to the power of 1001 is divided
- Connect Four: Grids [02/03/2003]
I need to investigate different ways of putting 4 counters in a
straight line in different size grids (squares and rectangles).
- Connecting the Boxes [12/28/1998]
I have an arrangement of boxes and am trying to draw one continuous line
connecting them all. Can this be done?
- Converting Post-Fix (Reverse Polish) Notation [02/20/2000]
How do I convert ABCDE x F / + G - H / x + to in-fix notation?
- Coprimes in Fermat's Last Theorem [06/03/1999]
Why are (z-x)/2 and (z+x)/2 coprime in Fermat's Conjecture when n = 2?
- Cost of Phone Call [02/27/1997]
Use the greatest integer function to write a function describing the cost
of a telephone call with a flat rate for the first two minutes and a
lower charge for each following minute.
- Counting Bug Populations [12/03/1998]
In each generation, a happy bug splits into a sad bug and a blank bug,
.... How do you find a formula for the number of each kind of bug in
- Counting Digits [10/23/1998]
Using the Fundamental Principle of Counting, how many six-digit numbers
can you make with two zeros, two twos, and two fours?
- Counting Possible Arrangements for a Group Photo [10/21/2003]
Eight women of eight different heights are to pose for a photo in two
rows of four. Each woman in the second row must stand directly behind
a shorter woman in the first row. In addition, all of the women in
each row must be arranged in order of increasing height from left to
right. Assuming that these restrictions are fully adhered to, in how
many different ways can the women pose?
- 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.