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.
- Odd and Even Vertices [1/30/1996]
We are trying to trace networks without crossing a line or picking up our
pencils, but how can we know if a vertex is odd or even?
- Odd Number of Hands, Even Number of People [08/31/2001]
Every person on earth has shaken a certain number of hands. Prove that
the number of persons who have shaken an odd number of hands is even.
- The Official Euclidean Algorithm [11/16/2000]
Can you state briefly the "official" Euclidean Algorithm?
- One-to-One Correspondence of Infinite Sets [03/26/2001]
How can I prove that any two infinite subsets of the natural numbers can
be put in a 1-1 correspondence?
- Onto Functions and Stirling Numbers [09/22/2002]
How would I show for m greater than or equal to 3 that s(m, m-2) = (1/
24)m(m-1)(m-2)(3m-1), where s(m,n) are Stirling numbers of the first
- Opening and Closing 1000 Lockers [03/16/1997]
There are 1000 closed lockers and 1000 students. The first student opens
every locker; the second student reverses every other locker...
- Optimal Seating Arrangements [07/20/2000]
N people are invited to a party and asked to RSVP with the names of up to
k people they would like to sit with. Is there a formula that will yield
the "best" arrangement of people?
- P(2n,3) = 2P(n,4) [10/08/2002]
Solve: P(2n,3) = 2P(n,4)
- Partitioning Elements [12/08/2001]
If part(n,k) is the number of ways to partition a set of n elements into
k subsets, what is Part(5,2)? Prove Part(n+1,k) = Part(n,k-1)+k*
- Partitioning the Integers [3/15/1995]
One of my students chose the topic of partitions of the positive
- Partitions and Triangle Inequality [5/26/1995]
How is the number of different triangles with integer sides related to
the perimeter of the triangle?
- Pascal's Triangle and Powers of 11 [02/21/1999]
Finding the powers of 11 in the rows of Pascal's triangle.
- Pascal's Triangle Tidbits [4/5/1995]
My friend and I are doing a math fair project on Pascal's Triangle...
- Pascal's Triangle: Words instead of Numbers [08/28/2001]
How many times can you read the word "triangles" in the figure?
- Patterns in Pascal's Triangle [07/21/1997]
I am working on a project about Pascal's triangle trying to find as many
patterns as I can and prove them by induction.
- A Phone Chain [10/28/1998]
In a phone chain of people, the first person gets a call and calls two
people, and so on. How long does it take to call 55 people?
- Pick's and Euler's Theorems [05/06/1999]
What is Pick's theorem and how can it be linked with Euler's theorem?
- Pick's Theorem, Lattice Points, and Area [08/27/1998]
What is a lattice point, and how does it relate to the area of a
triangle, rectangle, and a circle?
- Pieces on a Chess Board [10/27/1996]
Prove that with 9 separate playing pieces, you cannot place the pieces on
an 8 by 8 chess board such that the distance between any 2 pieces is
- Primes that are Sums of Primes [06/22/1999]
Is there an nth prime number, p, (other than 5, 17 and 41) that is equal
to the sum of the prime numbers up to n? For example, the 7th prime is
- Primes That Are the Sum of 2 Squares [09/17/1999]
How can I prove that every prime of the form 4m + 1 can be expressed as
a sum of two squares?
- Probabilities and Expected Value in Seating Arrangements [05/12/1998]
Three couples are seated at random around a round table. Let M denote the
number of husbands seated next to their wives ...
- Probability Transition Matrices [02/10/1999]
How do you use probability transition matrices to find probabilities
after the first transition?
- Product of Disjoint Cycles [10/16/1998]
How to express (1 2 3 5 7)(2 4 7 6) as the product of disjoint cycles.
- Product of Two Primes [10/27/1999]
How many positive integers less than 100 can be written as the product of
the first power of two different primes?
- Programs to Find Prime Numbers [11/27/1996]
Can a program be written in BASIC to compute the number of prime numbers
smaller than n?
- Projects on Puzzles or Mazes [11/13/2002]
I would like to do a project that involves applying mathematics to
areas like puzzles or mazes.
- Proof by Contradiction: e^n.... [7/5/1996]
I'm trying to prove that e^n (n is a natural number) is not O(n^m) for
any power of m...
- Proof by Induction [4/3/1996]
I was given a proof by my math teacher: by mathemetical induction, prove
that i(nCi) = n2^n-1.
- Proof by Induction [7/3/1996]
How can I prove through induction that 1+1/4+1/9+ ... 1/n^2 < 2-
1/n for all n > 1?
- Proof by Induction [06/15/1999]
How can I show by induction that (4^n)-1 is divisible by 3 for all n >=
- Proof by Induction [05/07/2003]
If n is greater than or equal to 6, prove that n! is greater than or
equal to n(2^n).
- Proof by Mathematical Induction [09/24/1999]
Prove the following statement by mathematical induction: for any integer
n greater than or equal to 1, x^n - y^n is divisible by x-y where x and y
are any integers with x not equal to y.
- Proof Involving mod 5 [10/27/2002]
Prove n^2 mod 5 = 1 or 4 when n is an integer not divisible by 5.
- Proof of Ordered Partioning of Integers [07/31/2001]
I have found that there are 2^(n-1) ways to partition an integer (where
order matters and all positive integers are available), but need a proof
for this seemingly simple formula.
- Proofs of the Two-Color Map Theorem [03/19/2003]
Suppose a map is drawn using only lines that extend to infinity in
both directions; are two colors sufficient to color the countries so
that no pair of countries with a common border have the same color?
- Proof that an Even Number Squared is Even [06/02/1999]
How do you prove that any even number squared is even and any odd number
squared is odd?
- Proof That Brussels Sprouts Game Ends in 5n - 2 Moves [04/15/2005]
How can I prove that the game Brussels Sprouts always ends in 5n - 2
- Quadrilaterals in a 3x3 Array of Dots [03/10/1999]
Counting them with combinatorics, then taking away degenerate cases.
- Question on a Math Counts Test [8/13/1995]
Find the integral solutions to 1/x + 1/y = 1/7.