Ask Dr. Math

High School Archive

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.
    Tournament scheduling.
    Venn diagrams.

---

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 primes?

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 of x.

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 seatbelts?

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 relatively prime.

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 Player B?

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 by 6...?

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 generation n?

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.

Page:  1  2  3  4  5  6 [next>]