Discrete Math

• Contrapositive, Converse, Inverse [Goode, 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 [Kelley, 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 [Campbell, 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 [Cypra, 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 [Schmidt, 4/1/1996]
  Could you please elaborate on this subject a little more?

• Formula for Nim [Kentaro, 02/22/2002]
  Is there a formula for the game of Nim?

• Mobius Strips and the Six-Color Map Theorem [Boomer, 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 [Warren, 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 [Chan, 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 [Nguyen, 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 [Arseneau, 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 [VanEtten, 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?

• Lines determined by 5 points [Fass, 11/13/1994]
  How many lines are determined by 5 points, no three of which are collinear?

• The Game of NIM [Chen, 1/31/1995]
  The game of NIM is played with a bunch of beans....

• Partitioning the Integers [Boehmk, 3/15/1995]
  One of my students chose the topic of partitions of the positive integers....

• Pascal's Triangle Tidbits [Thelma, Ana Maria, 4/5/1995]
  My friend and I are doing a math fair project on Pascal's Triangle...

• Partitions and Triangle Inequality [William Parker School, 5/26/1995]
  How is the number of different triangles with integer sides related to the perimeter of the triangle?

• Question on a Math Counts Test [Enzenberger, 8/13/1995]
  Find the integral solutions to 1/x + 1/y = 1/7.

• What is Discrete Math? [Lissie, 10/8/1995]
  I'm doing a project for school, and I need to know what discrete math is, an example of it, and what careers it is used in.

• An Explanation of Some Latin Math Terms [Cunningham, 12/11/1995]
  We are a small discrete math class of eight students studying logical arguments. Two arguments we have examined are "modus tollens" and "modus ponens." We understand the arguments but would like to know what the terms mean in English.

• Odd and Even Vertices [Taylor, 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?

• Number of Ways to Move [Seaman, 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?

• Word Problem Hints [Reichel, 3/12/1996]
  Two questions: 1) There are 1000 lockers numbered 1-1000. Suppose you open all of the lockers, then close every other locker. Then, for every third locker... 2) A certain substance doubles in volume every minute. At 9:00 a.m. a small amount is placed in a container...

• Finding Numbers with a Certain Number of Factors [Krause, 3/12/1996]
  Given that twelve is the least positive integer with six different positive factors (1,2,3,4,6,12), what is the least positive integer with exactly twenty-four positive factors?

• Fermat's Last Theorem and Chess [Kirbiyik, 3/25/1996]
  I'd like to know if Fermat's problem is solved, and when chess is likely to be solved.

• Proof by Induction [Sylvestr, 4/3/1996]
  I was given a proof by my math teacher: by mathemetical induction, prove that i(nCi) = n2^n-1.

• Sets and Integer Pairs [Gemilang, 6/10/1996]
  A) Prove that the sum of a specified element of one set is greater than or equal to a specific number (n + 1)/2; B) Find all the ordered pairs of integers (m, n) that satisfy the equation (n^3 + 1) / (mn - 1).

• Combinatorial Proof [Brasher, 6/13/1996]
  Please prove this combinatorial proof.

• Electoral math units [Cushman, 6/16/1996]
  Any suggestions for units on electoral math, for use with students in grades 7-9, with plenty of entry points for both beginning and advanced students?

• Proof by Induction [Turner, 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 Contradiction: e^n.... [Turner, 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...

• Objects in a Pyramid [Geldermann, 7/8/1996]
  Objects are stacked in a triangular pyramid... how many objects are in the nth layer from the top?

• How Many Factors? [Bundy, 7/14/1996]
  How do you find the number of factors for a number?

• Binomial Theorem by Induction [Turner, 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.

• Graph Without Crossing Lines [Tone, 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 lines?

• The Seven Bridges [Wnedokus, 8/28/1996]
  What is the problem from the 1700s about a town with seven bridges, where you want to cross each bridge exactly once?

• Divisibility and Remainders [Horrocks, 8/23/1996]
  Show that every odd square leaves a remainder 1 when divided by 8... Prove that n^5-n is divisible by 30... Suppose m is a positive integer divisible by 11...

• Using Trees [Gabanski, 10/18/1996]
  What are trees used for? What are some examples?

• Pieces on a Chess Board [Ho, 10/27/1996]
  Prove that with 9 seperate playing pieces, you cannot place the pieces on an 8 by 8 chess board such that the distance between any 2 pieces is always different.

• Formula for Factors of a Number [Daniel, 11/3/1996]
  How many triangles can you draw on a square grid of dots of size x*x?

• Programs to Find Prime Numbers [McNeil, 11/27/1996]
  Can a program be written in BASIC to compute the number of prime numbers smaller than n?

• Cost of Phone Call [Cailab, 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.

• Opening and Closing 1000 Lockers [Atsang, 03/16/1997]
  There are 1000 closed lockers and 1000 students. The first student opens every locker; the second student reverses every other locker...

• Integer Divisors [Mahroof, 04/11/1997]
  N has six distinct integer divisors including 1 and N. The product of five of these is 648; find another divisor of N.

• Winning at NIM [Wilson, 06/09/1997]
  How do you ensure that you win the game of NIM?

• Resources for NIM [Sanford, 07/03/1997]
  Where can I find information about the game of NIM?

• Patterns in Pascal's Triangle [Luong, 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.

• Graphs - Proving the Infinite Ramsey Theory [Madarasz, 11/10/1997]
  In a graph with infinite "points," if we colour the lines with two colors we'll have either a red or a blue infinite chain of lines, an infinite number of points, all of them joined to each other with the same colour...

• Diophantine Equations [Felgate, 11/17/1997]
  We have searched the web for information about diaphantine equations.

• Locker Problem [Boyer, 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 numbers...

• Finding Formulas for Number Sequences [Chu, 11/22/1997]
  My question is about trying to find a formula between numbers.

• Number Systems: Two Points of View [Liz, 06/30/1998]
  What are the number systems?

• Showing Divisibility [Mills, 07/12/1998]
  How do you show that 5^(2n) + 3(2^(2n+1)) is divisible by 7?

• Using Graph Theory to Count Routes [Blackman, 07/15/1998]
  How do you use a diagram to count the number of different direct routes that connect five cities?

• Congruence of Integers [Irene, 08/10/1998]
  Can you help me find the remainder when 5 to the power of 1001 is divided by 6...?

• Segmenting Paths [Amber, 08/20/1998]
  A path between opposite vertices of the square is made up of hundreds of horizontal and vertical segments. What is the best approximation to the length of the path - 24, 34, 44, or more than 44?

• Discrete versus Continuous [Jacobson, 08/24/1998]
  What is discrete math? How do you use it?

• Pick's Theorem, Lattice Points, and Area [Sen, 08/27/1998]
  What is a lattice point, and how does it relate to the area of a triangle, rectangle, and a circle?

• Lattice Points and Boundary Lattice Points [Doria, 08/30/1998]
  What is an interior lattice point and a boundary lattice point of a given shape (triangle, circle, rectangle, etc.)?

• Employee Scheduling [Lindsay, 09/22/1998]
  Can you help me make a schedule to staff an ice cream parlor?

• Greatest Integer Functions [Laura, 09/27/1998]
  Can you help me solve for the graph of [y]=[x], where [] is the greatest integer function?

• Equivalence Relations [Shawn, 10/02/1998]
  Let X = {people in the world} and R be a relation on the set X... find the equivalence classes.

• Set Equality [Lior, 10/12/1998]
  Can you help me show that (A-B)-C = (A-C)-(B-C), where A, B, and C are sets?

• Product of Disjoint Cycles [Pelayo, 10/16/1998]
  How to express (1 2 3 5 7)(2 4 7 6) as the product of disjoint cycles.

• Counting Digits [Erle, 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?

• Explaining the Euclidean Algorithm [Megan, 10/27/1998]
  In the Euclidean Algorithm (or the Division Algorithm), why is the last divisor the greatest common factor?

• A Phone Chain [Leah, 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?

• Factors and Multiples - Hamiltonian Path [Dawson, 11/02/1998]
  We have to make a sequence of numbers, all different, each of which is a factor or a multiple of the one preceding it.

• Symmetric, Transitive, and Reflexive Relations [Mike, 11/10/1998]
  Suppose R is a symmetric and transitive relation on A, and for each a in A there is b in A such that (a,b) and is in R. Show that R is an equivalence relation...

• System of Equations and Gauss-Jordan [Jones, 11/29/1998]
  Solve using the Gauss-Jordan method: a 5-percent solution of a drug is mixed with 15- and 10-percent solutions...

• Counting Bug Populations [Ahmed, 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?

• Coin Tosses, Dealing Cards... [Greg, 12/08/1998]
  Several questions on discrete math - probability and combination; deducing recurrence relations.

• Matrix Multiplication [Brossard, 12/18/1998]
  Why does matrix multiplication work? Why are the rows multiplied and added with the columns?

• Connecting the Boxes [Mainprize, 12/28/1998]
  I have an arrangement of boxes and am trying to draw one continuous line connecting them all. Can this be done?

• Types of Variables [Kane, 01/14/1999]
  Can you explain the different types of variables, such as free variables and bound variables?

• Recursive and Explicit Formulas [Ososke, 01/19/1999]
  Is there an easy way to convert recursive formulas into explicit ones and vice versa?

• Venn Diagrams [Remi, 01/24/1999]
  Members of a computer class choose at least one of three options. How many are taking just one? ... Use a Venn diagram.

• Moving Knights on a Chessboard [Gibson, 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?

• Factoring [Kevin, 02/09/1999]
  Find the smallest number (integer) that has 30 factors.

• Probability Transition Matrices [Skor, 02/10/1999]
  How do you use probability transition matrices to find probabilities after the first transition?

• Algebra Paper-Folding Problem [Lauren, 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.

• Equivalence Classes [Wayne, 02/19/1999]
  Is there an equivalence class containing exactly 271 elements?

• Pascal's Triangle and Powers of 11 [Chung, 02/21/1999]
  Finding the powers of 11 in the rows of Pascal's triangle.

• Graphs with Three Vertices [Edward, 03/31/1999]
  What are graphs with three vertices? Could you give me some examples?

• Quadrilaterals in a 3x3 Array of Dots [David, 03/10/1999]
  Counting them with combinatorics, then taking away degenerate cases.

• Finding Pathways [Gillen, 04/08/1999]
  How many ways are there to get from top left to bottom right on a square when there are three lines going across each way?

• Math Logic - Determining Truth [De Hamer, 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.

• Rat Population [Cook, 04/27/1999]
  Estimate the number of offsping produced from a pair of rats in one year...

• Pick's and Euler's Theorems [charlie, 05/06/1999]
  What is Pick's theorem and how can it be linked with Euler's theorem?

• Ramsey's Theorem and Infinite Sequence [Chan, 06/01/1999]
  Ramsey's Theorem applied to divisibility in infinite sequences.

• Proof that an Even Number Squared is Even [Jason, 06/02/1999]
  How do you prove that any even number squared is even and any odd number squared is odd?

• Coprimes in Fermat's Last Theorem [Oliver, 06/03/1999]
  Why are (z-x)/2 and (z+x)/2 coprime in Fermat's Conjecture when n = 2?

• Finding a Non-Recursive Formula [Alume, 06/10/1999]
  How can I find a non-recursive formula for the recurrence relation s_n = - [s_(n-1)] - n^2 with the initial condition s_0 = 3?

• Duotrigesimal (Base 32) Numbers [deBoer, 06/11/1999]
  A unique and interesting use for base 32 or "duotrigesimal" numbers.

• How Many Threes? [Logan, 06/12/1999]
  If all the numbers from 1 to 333,333 are written out, how many times will the digit 3 be used?

• Proof by Induction [Bergman, 06/15/1999]
  How can I show by induction that (4^n)-1 is divisible by 3 for all n >= 1?

• Primes that are Sums of Primes [Tikotekar, 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 17=2+3+5+7.

• Reversed Digits Theorem [Tikotekar, 06/24/1999]
  For a positive integer abc..., if (abc...)^n = xyz... and if (a+b+c+...)^n = x+y+z+..., how can I prove that (...cba)^n = ...zyx?

• Number Theory Proofs [Ki, 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?

• Applying Euler's Methods [Cunningham, 07/27/1999]
  Questions about prime divisors, triangle constructions, decomposing quartic polynomials, and rational roots.

• Number of Unordered Partitions [Bonciocat, 08/18/1999]
  Is there a formula for the number of unordered partitions of a positive integer p(n)?

• Total Membership [Foy, 08/20/1999]
  At a country club 35 people play golf, 28 swim, and 24 play tennis. Of these, 6 play golf and tennis only, 9 play golf and swim only, and 7 play tennis and swim only. 8 people do all three. How many members are there altogether?

• Simple Proof by Induction [Bourouba, 08/27/1999]
  How can I show by mathematical induction that the proposition "if n >= 1 then 3n >= 1 + 2n" is true?

• Infinity Hotel Paradox [Evening, 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?

• Primes That Are the Sum of 2 Squares [Jennelle, 09/17/1999]
  Hopw can I prove that every prime of the form 4m + 1 can be expressed as a sum of two squares?

• Venn Diagram of Natural Numbers [Coons, 09/22/1999]
  How can I construct a Venn diagram comparing the numbers 1 through 100 in these 4 areas: odd, even, composite and prime?

• Proof by Mathematical Induction [James, 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.

• Boolean Algebra Proofs [Perego, 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.

• Unions and Intersections: Proving Sets [Edgar, 10/17/1999]
  How can I verify a proof of the statement A - (B union C) = (A - B) intersect (A - C)?

• Finding Howlers [Nagpal, 10/25/1999]
  Howlers are fractions like 16/64; when you cross out the 6 on the top and the bottom, you are left with 1/4, which is the simplified fraction. How can I find all 2-digit, 3-digit and 4-digit howlers?

• Three Number Theory Questions [Christopher, 10/25/1999]
  Find the sum of the digits in 4444^4444; find how many times the digit 1 occurs from 1 up to 10,000,000,000; find 3 integers greater than 5^100 that are factors of (5^1985)-1.

• Sum of Squares of Two Odd Integers [Devanshi, 10/26/1999]
  How can I prove that the sum of the squares of two odd integers cannot be a perfect square?

• Average Age at a Party [Amure, 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?

• Product of Two Primes [Amure, 10/27/1999]
  How many positive integers less than 100 can be written as the product of the first power of two different primes?

• Factorials Can't Be Squares [Datta, 02/11/2000]
  Can you prove that the factorial of a number (greater than 1) can never be a perfect square?

• Converting Post-Fix (Reverse Polish) Notation [Francis, 02/20/2000]
  How do I convert ABCDE x F / + G - H / x + to in-fix notation?

• Karnaugh Maps [Goold, 05/07/2000]
  What are Karnaugh maps? How are they used?

• Even - Odd Handshake Problem [Cox, 05/11/2000]
  How can I prove that the number of persons who have shaken an odd number of hands is even?

• Floor and Ceiling [Veena, 05/28/2000]
  What do 'floor' and 'ceiling' mean in mathematics?

• Optimal Seating Arrangements [Schwartz, 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?

• Nim [Winarto, 09/26/2000]
  What is the principle of Nim and what is its application?

• Breadth-First Search and Girth [Donald, 11/13/2000]
  How can you use a breadth-first search to compute the girth (length of shortest cycle) of a graph?

• The Official Euclidean Algorithm [Julie, 11/16/2000]
  Can you state briefly the "official" Euclidean Algorithm?

• How Many Distinct Patterns? [Ralph, 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?

• New School Lockers [Lopez, 01/28/2001]
  Which locker was touched the most?

• What is Discrete Math? [Riddley, 02/12/2001]
  What is discrete mathematics, and why is it called "discrete"?

• Examples of the Fundamental Counting Principle [Diana, 02/17/2001]
  There are three ways to go from Town A to Town B, and four ways to go from Town B to Town C. How many different ways are there to go from Town A to Town C, passing through Town B?

• Tracing a Figure Without Lifting Your Pencil [Kerri, 03/09/2001]
  Is there a simple way to quickly tell whether a figure can be traced without lifting your pencil?

• One-to-One Correspondence of Infinite Sets [Anokye, 03/26/2001]
  How can I prove that any two infinite subsets of the natural numbers can be put in a 1-1 correspondence?

• Rock, Paper, Scissors [Baum, 03/29/2001]
  If three people are playing Rock-Paper-Scissors, how many different combinations can be made, assuming order doesn't matter?

• Integer Solutions of ax + by = c [Armentrout, 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?

• Rubik's Cube Combinations [Glapa, 04/11/2001]
  I read that a rubics cube has 4 quintillion different possible combinations. Is this number correct? How can I calculate this value on my own?

• System-Level Programming and Base 2 [Eric, 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 [Anderson, 05/24/2001]
  Is there an easy solution to the "Traveling Salesman Problem"?

• Proof of Ordered Partioning of Integers [Dina, 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.

• Subsets of Real Numbers and Infinity [Kevin, 08/22/2001]
  Am I correct in saying that both the whole number set and the integer set have an infinite number of numbers within them, and therefore are of the same size?

• Pascal's Triangle: Words instead of Numbers [Ryan, 08/28/2001]
  How many times can you read the word "triangles" in the figure?

• Fewest Number of Stops [John, 09/12/2001]
  At some stops, the SLU Express bus picks up 5 people. At other stops, it picks up 2 and lets off 5...

• Odd Number of Hands, Even Number of People [Telinda, 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.

• Graph Theory [Kate, 09/29/2001]
  Why is a graph with five vertices, each having a degree of 3, impossible?

• Line Drawn through Lines Puzzle [Lauren, 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 twice.

• Traveling Through a Square [Stephen, 11/25/2001]
  How do I get from the bottom left-hand corner of a 64-block square to the top right-hand corner, only going through each square once?

• 15 Ball Players [Gerrit, 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.

• Partitioning Elements [Rajshree, 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* Part(n,k)...

• How Many Games in the Tournament? [Crumpy, 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?

• Condorcet Criterion [Marge, 02/13/2002]
  Please explain the "Condorcet candidate" when using various ways to determine a winner in an election.

• Generating Eight-Character Passwords [Lohkee, 03/08/2002]
  Given some restrictions, calculate the number of possible 8-character passwords.

• Buying Doughnuts [Wendy, 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?

• Finding the nth Term [Kathy, 03/28/2002]
  My formula works with the exception of the first term.