Recognizing Patterns

I’ve often told my students that the best problem solvers are those who recognize patterns from past problems in new situations.  So, the best way to become a better problem solver is to solve lots of problems, study the ways others have solved the problems you’ve already cracked (or at least attempted), and to keep pushing your boundaries because you never know what parts of what you learn may end up providing unexpected future insights.

I lay no claims to being a great problem solver, but I absolutely benefited from problem solving exposure when I encountered @jamestanton‘s latest “Playing with Numbers” puzzler from his May 2012 Cool Math Newsletter.  (Click here to access all of Jim’s newsletters).  (BTW, Jim’s Web page is chock full of amazing videos and insights both on the problem-solving front and for those interested in curriculum discussions.)  Here’s what Jim posed:

Write the numbers 1 though 10 on the board. Pick any two numbers, erase them, and replace them with the single number given by their sum plus their product. (So, if you choose to erase the numbers a and b, replace them with a + b + ab .) You now have nine numbers on the board.

Do this again: Pick any two numbers, erase them, and replace them with their sum plus product. You now have eight numbers on the board.

Do this seven more times until you have a single number on the board.

Why do all who play this game end up with the same single number at the end?  What is that final number?

SOLUTION ALERT:  Don’t read any further if you want to solve this yourself.

I started small and general.  If the first two numbers (a and b) produce a+b+ab, then adding c to the original list gives [(a+b+ab)+c]+ [(a+b+ab)\cdot c] which can be rewritten as a+b+c+ab+ac+bc+abc.  That’s when the intuition struck.  Notice that the rewritten form is the sum of every individual number in the list, AND every possible pair of those numbers, AND concludes with the product of the three numbers. I’ve seen that pattern before!

Given an nth degree polynomial with roots r_1, r_2, \ldots r_n, it’s factored form is (x-r_1)\cdot (x-r_2)\cdot\ldots\cdot (x-r_n) which can be expanded and rewritten as

x^n-(r_1+r_2+\ldots+r_n)\cdot x^{n-1}+
+(\text{every pair-wise product of } r_1 \ldots r_n)\cdot x^{n-2}-
-(\text{every three-way product of } r_1 \ldots r_n)\cdot x^{n-3}+\ldots
\ldots \pm (r_1\cdot r_2\cdot \ldots\cdot r_n)

Where the sign of the final term is positive for even n and negative for odd n.  I saw this in many algebra textbooks when I started teaching over 20 years ago, but haven’t encountered it lately.  Then again, I haven’t been looking for it.

Here’s the point … other than the alternating signs, the coefficients of the expanded polynomial are exactly identical to the sums I was getting from Jim’s problem.  That’s when I rewrote my original problem on my CAS to (x+a)\cdot (x+b)\cdot (x+c) and expanded it (see line 1 below).  The coefficients of x^2 are the individual numbers, the coefficients of x are all the pair-wise combinations, and the constant term drifting off the end of the line is a\cdot b\cdot c.  And I eliminated the \pm sign challenge by individually adding the numbers instead of subtracting them as I had in the polynomial root example that inspired my insight.  Let x=1 to clean up and make the pattern more obvious.

So, creating a polynomial with the given numbers and substituting x=1 will create a number one more than the sum I wanted (note the extra +1 resulting from the coefficient of x^n).  Using pi notation, substituting x=1, and subtracting 1 gives the answer.  In case you didn’t know, pi notation works exactly the same as sigma notation, but you multiply the terms instead of adding them.

The solution–39,916,799–is surprisingly large given the initial problem statement, and while my CAS use confirmed my intuition and effortlessly crunched the numbers, its tendency to multiply numbers whenever encountered has actually hidden something pretty. From the top line of the last image, substituting x=1 would have created the product 2\cdot 3\cdot 4\cdot\ldots \cdot 11 which the penultimate line computed to be 39916800.  But before the product, that number was 11!, making 11!-1 a far more revealing version of the solution.

MORAL:  Even after you have an answer, take some time to review what has happened to give yourself a chance to learn even more.

EXTENSION 1:  Instead of 1 to 10 as the initial numbers, what if the list went from 1 to any positive integer n?  Prove that the final number on the board is (n+1)!-1.

EXTENSION 2:  While a positive integer sequence starting at 1 (or 0) produces a nice factorial in the answer, this approach can be used with any number list.  For example, follow Jim’s rules with 37, 5, -2, and 7.9.  Use the polynomial approach below for a quick solution of -2030.2.  Confirm using the original rules if you need.

EXTENSION 3:  By now it should be obvious that any list of numbers can be used in this problem.  Prove that every list of numbers which includes -1 has the same solution.

EXTENSION 4:  Before explaining some lovely extensions of problems like this to generalized commutativity and associativity, Jim’s May 12 Cool Math Newsletter asks what would happen if instead of a+b+ab, the rule for combining a and b was \displaystyle\frac{a\cdot b}{a+b}.  You can show that with three terms, this would become \displaystyle\frac{abc}{ab+ac+bc}, and four terms would give \displaystyle\frac{abcd}{abc+abd+acd+bcd}. In other words, this rule would morph n original numbers into a fraction whose numerator is the product of the numbers and whose denominator is the sum of all possible products of any (n-1)-sized groups of those numbers.  For the original integers 1 to 10, I know the numerator and denominator terms are the last two coefficients in a polynomial expansion.

The final fraction simplifies, but I think \displaystyle\frac{3628800}{10628640} is slightly more informative.

Happy thoughts, problems, solutions, and connections to you all.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s