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 is used for example in 2016-17 Set #1 Problem 4.