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. Our hope is that 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 prove.)

Modular arithmetic

When we have 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. This 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^{\text{th}} }[/math] 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.

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{ \ang 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 angel [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 angel [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.

A nice application of the Inscribed Angle Theorem is the following: suppose that [math]\displaystyle{ ABCD }[/math] is a cyclic quadrilateral (which means that we can draw a circle that passes through [math]\displaystyle{ A, B, C, D }[/math]). Then the sum of any two opposite angles is equal to [math]\displaystyle{ 360^{\text{o}} }[/math]. This means that [math]\displaystyle{ \angle ABC+\angle CDA= 360^{\text{o}}, \quad \text{and}\quad \angle BCD+\angle DAB= 360^{\text{o}}. }[/math]