See also the
Browse College Discrete Math
Stars indicate particularly interesting answers or
good places to begin browsing.
- 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
- 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*
- Peg Solitaire [04/19/2003]
If have a particular board setup, how would I prove that a solution
exists or does not?
- Polya-Burnside Lemma [07/02/1999]
Given unlimited amounts of 2 types of beads, how many unique necklaces
can you make using exactly k beads?
- 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?
- 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 1 + 1 = 2 [06/10/1999]
Can you prove that 1 + 1 = 2?
- 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
- Proving a Graph is Connected [3/19/1996]
For any graph G which is not connected, how do I prove that its
complement must be connected?
- A Quick Overview of P vs. NP Problems [11/19/2007]
Can you explain what P and NP problems are at a level that a high
school student can understand?
- Searching for a Monkey in 17 Rooms [08/25/2004]
A monkey is in one of 17 rooms built side by side. Each night the
monkey moves one room right or left. Each day you can look in any two
rooms. What's the optimal search pattern to find the monkey?
- Seating Guests at a Table [9/5/1995]
Consider seating n dinner guests at k tables of l (lower case L) settings
each, therefore n = k l , for m courses so that no guest shares a table
more than once with any other guest. Equivalently, consider n players to
be divided into k teams of l players for m rounds of a contest. No player
may, more than once, be on the same team as any other player. 1. What is
the maximum value of m, as a function of k and l? 2. How could one
systematically specify the seating arrangement for the m courses?
- Solving a System of Modular Equations with Multiple Variables [12/15/2004]
Thoughts on solving a system of modular equations such as:
(1919ab) mod 5107 = 1
1919(a+1)(b-1) mod 5108 = 5047
1919(a+2)(b-2) mod 5109 = 1148
1919(a+3)(b-3) mod 5110 = 3631
1919(a+4)(b-4) mod 5111 = 2280
- Sum of Reciprocals [08/05/2008]
Find seven unique positive integers such that the sum of their
reciprocals is 1.
- System-Level Programming and Base 2 [05/03/2001]
In computer programming, I have a result that contains several values,
always a power of 2 (2^2, 2^3, 2^4). If my value is 2^3, 2^4, 2^6 304,
how can I tell if 2^3 exists in 304?
- Traveling Salesman Problem [05/24/2001]
Is there an easy solution to the "Traveling Salesman Problem"?
- Triangle in Randomly Colored Plane [10/28/2002]
Prove: Assume that all points in the real plane are colored white or
black at random. No matter how the plane is colored (even all white or
all black) there is always at least one triangle whose vertices and
center of gravity (all 4 points) are of the SAME color.
- Uncovering Squares with Odd Coordinates [12/24/2003]
Prove that on a chessboard with dimensions (2k+1) by (2k+1), covered
by dominoes except in some of the corners, we can uncover any square
with odd coordinates by sliding the dominoes around.
- Water, Gas, Electricity to Three Homes Puzzle [06/30/2002]
Connect three houses with each of three utilities without crossing any
lines. Is this possible?