Problem Solver's Toolbox

The goal of this page is to collect simple problem solving strategies and tools. We hope that students interested in the Wisconsin Math Talent Search would find the described ideas useful. This page and the discussed topics can be used as a starting point for future exploration.

General ideas

There is no universal recipe for math problems that would work every time, that's what makes math fun! There are however a number of general strategies that could be useful in most cases, here is a short list of them. (Many of these ideas were popularized by the Hungarian born mathematician George Pólya in his book How to Solve It.)

• Make sure that you understand the problem.
• If possible, draw a figure.
• Can you connect the problem to a problem you have solved before?
• If you have to show something for all numbers (or a large number) then try to check the statement for small values first.
• Can you solve the problem in a special case first? Can you solve a modified version of the problem first?
• Is there some symmetry in the problem that you can exploit?
• Is it possible to work backward?
• Does it help to consider an extreme case of the problem?
• Is it possible to generalize the problem? (Sometimes the generalized is easier to solve.)

Modular arithmetic

When we have to divide two integers, they don't always divide evenly, and there is a quotient and a remainder. For example when we divide 10 by 3 we get a remainder of 1. It turns out that these remainders behave very well under addition, subtraction, and multiplication. We say two numbers are the same "modulo [math]\displaystyle{ m }[/math]" if they have the same remainder when divided by [math]\displaystyle{ m }[/math]. If [math]\displaystyle{ a }[/math] and [math]\displaystyle{ x }[/math] are the same modulo [math]\displaystyle{ m }[/math], and [math]\displaystyle{ b }[/math] and [math]\displaystyle{ y }[/math] are the same modulo [math]\displaystyle{ m }[/math], then [math]\displaystyle{ a+b }[/math] and [math]\displaystyle{ x+y }[/math] are the same modulo [math]\displaystyle{ m }[/math], and similarly for subtraction and multiplication.

For example, 5 is the same as 1 modulo 4, and hence [math]\displaystyle{ 5\cdot 5 \cdot 5 \cdot 5=5^4 }[/math] is the same as [math]\displaystyle{ 1\cdot 1\cdot 1\cdot 1=1 }[/math] modulo [math]\displaystyle{ 4 }[/math]. Same way you can show that [math]\displaystyle{ 5^{1000} }[/math] has a remainder of 1 when we divide it by 4.

Modular arithmetic often makes calculation much simpler. For example, see 2016-17 Set #2 Problem 3.

See Art of Problem Solving's introduction to modular arithmetic for more information.

Mathematical induction

Suppose that you want to prove a statement for all positive integers, for example that for each positive integer [math]\displaystyle{ n }[/math] the following is true: [math]\displaystyle{ 1\cdot 2+2\cdot 3+3\cdot 4+\cdots+n\cdot (n-1)=\frac{n(n+1)(n+2)}{3}.\qquad\qquad(*) }[/math] Mathematical induction provides a tool for doing this. You need to show the following two things:

1. (Base case) The statement is true for [math]\displaystyle{ n=1 }[/math].
2. (Induction step) If the statement is true for [math]\displaystyle{ n }[/math] then it must be true for [math]\displaystyle{ n+1 }[/math] as well.

If we can show both of these parts, then it follows that the statement is true for all positive integer [math]\displaystyle{ n }[/math]. Why? The first part (the base case) shows that the statement is true for [math]\displaystyle{ n=1 }[/math]. But then by the second part (the induction step) the statement must be true for [math]\displaystyle{ n=2 }[/math] as well. Using the second part again and again we see that the statement is true for [math]\displaystyle{ n=3, 4, 5, \cdots }[/math] and repeating this sufficiently times we can prove that the statement is true for any fixed value of [math]\displaystyle{ n }[/math].

Often the idea of induction is demonstrated as a version of `Domino effect'. Imagine that you have an infinite row of dominos numbered with the positive integers, where if [math]\displaystyle{ n }[/math]th domino falls then the next one will fall as well (this is the induction step). If we make the first domino fall (this is the base case) then eventually all other dominos will fall as well.

• Try to use induction to show the identity [math]\displaystyle{ (*) }[/math] above for all positive integer [math]\displaystyle{ n }[/math].
• You can also use induction to show a statement for all integers [math]\displaystyle{ n\ge 5 }[/math]. Then for your base case you have to show that the statement is true for [math]\displaystyle{ n=5 }[/math]. (The induction step is the same.)

See this page from Math Is Fun for some simple applications of induction.

Proof by contradiction

This is a commonly used problem solving method. Suppose that you have to prove a certain statement. Now pretend that the statement is not true and try to derive (as a consequence) a false statement. The found false statement shows that your assumption about the original statement was incorrect: thus the original statement must be true.

Here is a simple example: we will prove that the product of three consecutive positive integers cannot be a prime number. Assume the opposite: that means that there is a positive integer [math]\displaystyle{ n }[/math] so that [math]\displaystyle{ n(n+1)(n+2) }[/math] is a prime. But among three consecutive integers we will always have a multiple of 2, and also a multiple of 3. Thus the product of the three numbers must be divisible by both 2 and 3, and hence [math]\displaystyle{ n(n+1)(n+2) }[/math] cannot be a prime. This contradicts our assumption that [math]\displaystyle{ n(n+1)(n+2) }[/math] is a prime, which shows that our assumption had to be incorrect.

Proof by contradiction can be used for example in 2016-17 Set #1 Problem 4.

Pigeonhole Principle

The Pigeonhole Principle is one of the simplest tools in mathematics, but it can be very powerful. Suppose that [math]\displaystyle{ n\lt m }[/math] are positive integers, and we have [math]\displaystyle{ m }[/math] objects and [math]\displaystyle{ n }[/math] boxes. The Pigeonhole Principle states that If we place each of the [math]\displaystyle{ m }[/math] objects into one of the [math]\displaystyle{ n }[/math] boxes then there must be at least one box with at least two objects in it. The statement can be proved by contradiction: if we can find an arrangement of objects so that each box has less than two objects in it, then each box would contain at most one object, and hence we had at most [math]\displaystyle{ n }[/math] objects all together. This is a contradiction, which means that the original statement must be correct.

The Pigeonhole Principle is often used in the following, more general form. Suppose that [math]\displaystyle{ n, m, k }[/math] are positive integers with [math]\displaystyle{ n k\lt m }[/math]. If we place each of [math]\displaystyle{ m }[/math] objects into one of [math]\displaystyle{ n }[/math] boxes then there must be at least one box with at least [math]\displaystyle{ k+1 }[/math] objects in it. Try to prove this version by contradiction.

Here is a simple application: if we roll a die 13 times then there must be a number that appears at least three times. Here each die roll correspond to an object, each of the 6 possible outcomes correspond to a possible box. Since [math]\displaystyle{ 2\cdot 6\lt 13 }[/math], we must have a box with at least [math]\displaystyle{ 2+1=3 }[/math] objects. In other words: there will be number that appears at least three times.

Pigeonhole Principle can be used for example in 2014-15 Set #1 Problem 4.

Angles in the circle

The following theorems are often useful when working with geometry problems.

An illustration of Thales' Theorem. O is the center of the circle.

Thales' Theorem

Suppose that the distinct points [math]\displaystyle{ A, B, C }[/math] are all on a circle, and [math]\displaystyle{ AB }[/math] is a diameter of of the circle. Then the angle [math]\displaystyle{ ACB }[/math] is [math]\displaystyle{ 90^{\text{o}} }[/math]. In other words: the triangle [math]\displaystyle{ \triangle ABC }[/math] is a right triangle with hypotenuse [math]\displaystyle{ AB }[/math].

The theorem can be proved with a little bit of `angle-chasing'. Denote the center of the circle by [math]\displaystyle{ O }[/math]. Then [math]\displaystyle{ AO, BO, CO }[/math] are all radii of the circle, so they have the same length. Thus [math]\displaystyle{ \triangle AOC }[/math] and [math]\displaystyle{ \triangle BOC }[/math] are both isosceles triangles. Now try labeling the various angles in the picture and you should quickly arrive to a proof. (You can find the worked out proof at the wiki page of the theorem, but it is more fun if you figure it out on your own!)

The converse of Thales's theorem states that if [math]\displaystyle{ \triangle ABC }[/math] is a right triangle with hypotenuse [math]\displaystyle{ AB }[/math] then we can draw a circle with a center that is the midpoint of [math]\displaystyle{ AB }[/math] that passes through [math]\displaystyle{ A, B, C }[/math].

The Inscribed Angle Theorem below is a generalization of Thales' Theorem.

The Inscribed Angle Theorem

Suppose that the distinct points [math]\displaystyle{ A, B, C }[/math] are all on a circle and let [math]\displaystyle{ O }[/math] be the center of the circle. Then depending on the position of these points we have the following statements:

• If [math]\displaystyle{ O }[/math] is on the line [math]\displaystyle{ AB }[/math] then [math]\displaystyle{ \angle ACB=90^{\text{o}} }[/math]. (This is just Thales' theorem again.)
• If [math]\displaystyle{ O }[/math] and [math]\displaystyle{ C }[/math] are both on the same side of the line [math]\displaystyle{ AB }[/math] then the inscribed angle [math]\displaystyle{ \angle ACB }[/math] is half of [math]\displaystyle{ 360^{\text{o}} }[/math] minus the central angle [math]\displaystyle{ \angle AOB }[/math]:

[math]\displaystyle{ 2 \angle ACB= \angle AOB. }[/math]

• If [math]\displaystyle{ O }[/math] and [math]\displaystyle{ C }[/math] are on the opposite sides of the line [math]\displaystyle{ AB }[/math] then the inscribed angle [math]\displaystyle{ \angle ACB }[/math] is half of the central angle [math]\displaystyle{ \angle AOB }[/math]:

[math]\displaystyle{ 2 \angle ACB= 360^{\text{o}}-\angle AOB. }[/math]

If we measure the central angle [math]\displaystyle{ \angle AOB }[/math] the `right way' then we don't need to separate the three cases. In the first case the central angle is just [math]\displaystyle{ 180^{\text{o}} }[/math], and the inscribed angle is exactly the half of that. In the third case if we define the central angle to be [math]\displaystyle{ 360^{\text{o}}-\angle AOB }[/math] then again we get that the inscribed angle is half of the central angle.

The theorem can be proved with angle-chasing, using the same idea that was described for Thales' theorem. See the wiki page for the proof (but first try to do it on your own!).

Applications to cyclic quadrilaterals

The following statements (and their converses) are useful applications of the Inscribed Angle theorem.

1. Suppose that the points [math]\displaystyle{ A, B, C, D }[/math] form a cyclic quadrilateral, this means that we can draw a circle going through the four points. [math]\displaystyle{ AB }[/math] divides the circle into two arcs. If the points [math]\displaystyle{ C }[/math] and [math]\displaystyle{ D }[/math] are in the same arc (meaning that they are on the same side of [math]\displaystyle{ AB }[/math]) then [math]\displaystyle{ \angle ACB= \angle ADB. }[/math] The converse of this statement is also true: if [math]\displaystyle{ A, B, C, D }[/math] are distinct points, the points [math]\displaystyle{ C, D }[/math] are on the same side of the line [math]\displaystyle{ AB }[/math] and [math]\displaystyle{ \angle ACB= \angle ADB }[/math] then we can draw a circle around [math]\displaystyle{ A, B, C, D }[/math], in other words [math]\displaystyle{ ABCD }[/math] is a cyclic quadrilateral.

2. Suppose that [math]\displaystyle{ ABCD }[/math] is a cyclic quadrilateral. Then the sum of any two opposite angles is equal to [math]\displaystyle{ 180^{\text{o}} }[/math]. This means that [math]\displaystyle{ \angle ABC+\angle CDA= 180^{\text{o}}, \quad \text{and}\quad \angle BCD+\angle DAB= 180^{\text{o}}. \qquad\qquad (**) }[/math]

The converse of the previous statement is also true: suppose that [math]\displaystyle{ ABCD }[/math] is a quadrilateral with angles satisfying the equations [math]\displaystyle{ (**) }[/math]. Then [math]\displaystyle{ ABCD }[/math] is a cyclic quadrilateral: we can draw a circle that passes through the four points.

The Inscribed Angle Theorem and the statements about cyclic quadrilaterals can be used for example in 2015-16 Set #4 Problem 5.