The Right Tool for the Job

Back when I was still in middle school, I was sitting at my kitchen table during a family gathering, and my uncle posed the following puzzle for me to solve: A vendor is selling apples for 10 cents apiece, oranges for 5 cents apiece, and peanuts two for a penny. Someone comes along and buys exactly 100 items for exactly one dollar. How many apples, oranges and peanuts did that person buy?
I took out a sheet of paper and a pencil and came up with the answer in a couple of minutes. This astonished my uncle because, it turns out, he had posed this problem to two adults, including a geometry teacher, and they couldn't solve it in less than a half hour. I had a bit of a reputation for mathematical cleverness, and he had posed this problem to stump me and test the extent of my cleverness. Decades later I still remember exactly how I solved it, probably because it was a boost to my ego to learn that I was apparently smarter than a geometry teacher!
In this article I will explain exactly how I solved it, and then discuss why it was easier for me than for someone with more experience and education. If you don't already know the answer, spend a few minutes trying to solve it yourself before reading on. Pay special attention to the tools that you bring to bear on the problem.

Formulating the problem

There are six things that we don't know: how many apples, oranges and peanuts were purchased, and how much money was spent on each type of item. However, since we know the price for each type of item, we can express the last three variables in terms of the first three. In other words, if x is the number of apples, is the number of oranges, and z is the number of peanuts, then the buyer spent 10x cents on apples, 5y cents on oranges, and z/2 cents on peanuts. The two things we do know can be expressed in two equations:
1.    x + y + z = 100
2.   10x + 5y + z/2 = 100
Equation (1) says the buyer bought exactly 100 items, and equation (2) expresses that the buyer spent exactly 100 cents, or one dollar.
This is a system of linear equations in three variables. However, there are only two independent equations. This means that the system is underconstrained: there are infinitely many solutions in the real numbers. To solve the problem, we have to recognize that there are additional implicit constraints: first, that x, y and z are all non-negative  (you can't buy a negative number of items) and second, that they are all natural numbers (you can't buy half an apple or one third of an orange). Since we don't have ha'pennies, we also know that z must be an even number.
The equations enable us to establish bounds on the values of the variables. Clearly, from equation (1) each of the three variables is less than or equal to 100. From equation (2) we can establish upper bounds for x and  y by setting the other variables to zero:
3.    10x ≤ 100  ⇒ x ≤ 10
4.      5y ≤ 100 ⇒  y ≤ 20 
Since spending all the money on apples or oranges would result in far less than the requisite 100 items, these bounds are in fact strict. This means that the number of apples is one of the numbers {0,1,2,...,9}, and the number of oranges purchased is from the set {0,1,2,...,19}.
The number of peanuts is likely to be large. If we have to resort to trial and error, it would be best to focus on the smaller numbers of apples and oranges. So, the first thing we can do is to eliminate the z variable by multiplying equation (2) by 2, and subtracting equation (1) from it:
5.    20x + 10y + z  = 200
    -  (x  +   y  + z) = 100
      19x +  9y         = 100
We can then solve for y in terms of x:
6.    y = (100 - 19x)/9 = 11 1/9 - (2 1/9)x
It's at this point that can bring to bear the constraint that these numbers are all whole numbers. For y to be a whole number, the fractional part of the constant term, (1/9) must be cancelled by the fractional part of the term containing x. For this to happen, x must be congruent to 1 modulo 9. Among the possible values for x, only the number 1 itself is congruent to 1 modulo 9. Thus, x = 1, and from equation (6), y = 9. Substituting these values into equation (1) yields that z = 90.

Hammers and Nails

Why couldn't the adults arrive at this solution as quickly as I did? Was I really so much more clever? I think not. I believe that all three of us were victims of a peculiar human trait: we all have biases regarding what tools we bring to bear on a problem. There is a saying: "To a hammer, everything looks like a nail." We all have favorite tools in our toolbag, and we have specific ideas about when each tool is appropriate.
Having a favorite tool leads us to apply that tool to just about every problem we confront (every problem looks like a nail for our hammer). Understanding the limitations of our tools can lead us to avoid using a tool because we don't believe it will get us anywhere.
The fact that the system of linear equations is underconstrained likely lead the adults to abandon the use of algebra prematurely. They recognized that the problem involved the solution of diophantine equations (polynomial equations for which only integer solutions are acceptable), and so they likely sought to apply more sophisticated tools that are appropriate to the solution of diophantine equations (for example, computing the Smith Normal Form to determine two unimodular matrices). 
As a middle school student, I had just learned algebra, and knew nothing about diophantine equations, and so algebra was my shiny new hammer that I tried to apply to all problems. In fact, it could be argued that in choosing to eliminate the z variable, I had made a mistake. If I had continued my bounds analysis just a couple of steps further, I could have solved for z.
Consider expressing z in terms of the other variables using equation (1):
7.    z = 100 - (x + y)
Since  is at most 9, and y is at most 19, 
8.    (x + y) ≤ 28.
9.  z > 72
In fact, we know that x and y cannot both have their maximum values at the same time. If the buyer buys 19 oranges, this costs 95 cents, and so there isn't enough money left to buy any apples. If the buyer buys 18 oranges, this costs 90 cents, and so exactly one apple can be purchased, and the total number of items is again 19. Each additional apple purchased requires that two fewer oranges are purchased, so increasing the number of apples reduces the sum. Thus, 
10.    (x + y) < 19
11.    81 < z < 100
Now, from equation (2), 
12.   z/2 = 100 - (10x + 5 y)
13.   z = 200 - 20x - 10y = 10 (20 - 2x - y)
Equation (13) implies that z is an exact multiple of 10. Among the whole numbers between 81 and 100, 90 is the only multiple of 10. Thus, z = 90.
Substituting this value for z into equations (1) and (2) yields a system of two equations in two unknowns that can easily be solved for x and y.
By eliminating z, I had to resort to modular arithmetic to solve the problem. By focusing on z, I could have solved it just using bounds analysis and factoring. I was just lucky that my approach lead to a solution. The more educated mathematicians likely discounted it as a blind alley not worth going down.
The moral of the story? Consider all tools that might get you to a solution, and don't discount anything until you have spent a little time seeing what it can get you. Sometimes the prima facie wrong path gets you to a solution faster.

John Von Neumann

There is an old, likely apochryphal story that illustrates the penchant of even geniuses to inappropriately apply their favorite tools. A group of psychologists went around among mathematicians and physicists, posing the same problem to both: Two trains start out 100 miles apart heading towards one another on parallel tracks. One train travels at 40mph, the other at 60mph. Just as they begin to move (at the same time), a fly departs from the front of one train, flies at 100mph straight to the front of the other train, then immediately turns around and flies back to the first train. It keeps flying back and forth between the moving trains until the trains begin to pass one another. How far does the fly travel?
The physicists solved the problem by noting that the trains approach each other at a relative 100mph, and so close the 100 mile distance between them in 1 hour. In that amount of time, the fly will travel  100 miles. This way of formulating the problem solves it in just two multiplications, and so the physicists all answered the question  in less than a minute.
The mathematicians formulated the problem as the sum of a series: they expressed the distance the fly would travel during each leg of its flight, then computed the sum. This approach requires a more complicated formulation, and a more complicated way to compute the solution, so the mathematicians all took several minutes to arrive at an answer.
When the pyschologists posed the problem to John Von Neumann, a noted mathematician and one of
the founders of computer science, he solved it in under 30 seconds.
The psychologists were surprised. They told him "for a mathematician, you certainly think like a physicist." He replied, "No way! No physicist could have summed that series as quickly as did!"
if (isMyPost) { }