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?
• 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].

You can visualize proof by induction as the infinite chain [math]\displaystyle{ \text{the statement for 1}\to \text{the statement for 2} \to \cdots \to \text{the statement for }n \to \cdots }[/math] The base case shows that the first statement (the first link in the chain) is true, while the induction step shows that if a statement in the chain is true then the statement to its right is also true.

• Try to use induction to show the identity [math]\displaystyle{ (*) }[/math] above for all positive integer [math]\displaystyle{ n }[/math].