# 2 water jug puzzle

Here’s a cute proof of the well-known puzzle involving 2 water jugs.  The proof is worded very tersely, but it’s still pretty cool.

http://www.futilitycloset.com/2013/02/14/well-done/

# Math celebrities

Why Nate Silver Can Save Math Education in America

I heard somewhere that Nate Silver is thinking of analyzing teacher assessment at some point.  It’s a big problem, there’s no definitive answer, and there’s lots of data (though since most of it is standardized test scores, I find much of it questionable).  Sounds like a place he can have fun.

This article is about having math superstars being rolemodels for kids, to answer their questions of, “when am I ever going to use this?”  I feel this is treating the symptoms rather than the disease.  If math was taught as a way to solve problems and explore the world around us — as opposed to drilling computations — students’ curiosity will be a natural source of motivation.  “I want to understand” is a better driver than “I want to be a celebrity.”

The article’s secondary point, that the current curriculum sorely lacking in some departments (like statistics and finance), is something I agree with.

# Factor-y

I ran across a neat little trick today for factoring quadratics.

Let’s start simple: factor x^2 + 11x + 24.  To this, most people would start by finding factors of 24 because we need two numbers that multiply to +24 while adding to +11.  Well 1,24 would sum too high and 4,6 would sum just a little too low.  Nearby, 3,8 works out.  x^2 + 11x + 24 = (x + 3)(x + 8).

How about factoring 6x^2 – 11x + 10?  This is a bit more annoying because now we have to factor both 6 and 10, check pairwise combinations, and try both permutations of which factor of 6 multiplies which factor of 10.  There are a lot more combinations to check.

However let’s transform this problem into a similar problem: factor 6(6x^2 – 11x – 10) = (6x)^2 + 11(6x) – 60 = y^2 + 11y – 60, where y = 6x. This factors to (y – 4)(y + 15) or (6x – 4)(6x + 15). However, there is an extra factor of 6 in there, which we remove to get (3x – 2)(2x + 5).

In summary, we turn an annoying problem we’d solve by trial and error to one that can be solved by less trial and error. Okay, we’re replacing factoring two small numbers with factoring one large number, but we have a heuristic to guide the latter in that the sum/difference of the two factors behaves in a simple manner.

tl;dr taking the time to turn a hard problem into an easier problem may save you time in the long run.

# Newton’s Method and mental math square roots

(This is a post aimed more at high school students or young college students.)

This is a neat mental math trick I learned from television.  Let’s start easy and have one of your friends find a 4-digit perfect square (i.e. square any integer between 32 and 99, inclusive).  This trick will allow you to find the square root almost immediately.  For example, let’s use 3136.  Call it S.

1. Estimate the square root to the nearest ten.  50 squared is 2500 and 60 squared is 3600, so the square root is between 50 and 60.  I’m going to pick 50 because it’s easier to divide by.  Let X = 50.
2. Divide S by X, ignoring the remainder.  3136 / 50 = 62-point-something.  Let W = 62.
3. Average X and W.  That is the square root!  So for our example, the average of 50 and 62 is 56.  You can check that this is right.

However, your friends who are on the ball might not be that impressed since, because it is known that 3136 is a perfect square, we would have guessed that the units digits is either a 4 or a 6 since that is the only way to get a 6 in the units’ digit of 3136.  So let’s up the ante: we will now compute the square root of any 4-digit number to one decimal point.  For this, I asked a random number generator and got 5389.

1. 70 squared is 4900, 80 squared is 6400, so we’re somewhere between there.  Let X = 70, since 4900 is closer, and like most iterative algorithms, Newton’s Method works better when we start closer to the endpoint.
2. S / X is almost exactly 77.  Let W = 77.
3. The average of X and W is 73.5.  Because this method tends to overestimate, let’s call this 73.

Now let us repeat steps 2 and 3, but with X equal to the number found in step 3.

1. (again): S / X is a bit trickier with X = 73.  I have a mental math trick for this (which I’ll explain later): the answer is 73 + (5389 – 4900 – 420 – 9) / 73 = 73 + (489 – 420 – 9) / 73 = 73 + (69 – 9) / 73 = 73 + 60 / 73, or about 73.8.
2. (again): The average of 73 and 73.8 is 73.4.  To check this, the square root of 5389 is 73.4098086…

Before I explain how it works, I find the student learns more when they try it for themselves.  So here are some questions:

1. Show how this algorithm is derived from Newton’s method.  Hint: use y(x) = x^2 – S.  Why does this algorithm tend to overestimate?
2. Explain the mental math trick used in step 2 (again).  Hint: use algebra.

WARNING: Try the problems posted in part 1 before reading this post.  It took me some minutes, but mostly because I had to rederive Newton’s Method and tried the wrong y(x) first.  I find that students do not really learn when answers are just handed to them; you have do it for skills to sink in.  Do you think basketball stars got that good by listening or reading about how to play?  They go onto the court and practice their skills.  Math is the same.

1) I have a confession: I have a really bad memory for formulas.  However, this is not a problem in math if you know what you’re doing.  This is the formula for Newton’s Method that is easiest for me to remember:

y(x_i) = (x_i – x_{i+1}) [dy/dx evaluated at x_i]

where x_i is the current guess (i.e. the X in Step 1) and x_{i+1} is the next guess (i.e. the number found in Step 3).  This is easiest to see if I could include a diagram in this blog.  Since I can’t, I’ll just have to describe it to you: imagine the diagram of Newton’s Method.  We have a right triangle formed by the points (x,y) = (x_i,0), (x_i, y(x_i)), and the point where the tangent line meets the x-axis.  The right angle is at (x_i,0).  The slope of the tangent line is y(x_i) / (x_i – x_{i+1}), but calculus also tells us that the slope is dy/dx evaluated at x_i, hence the equation above.

dy/dx evaluated at x_i is 2x_i.  Solving for x_{i+1} (I’ll spare you the algebra) gives

x_{i+1} = x_i / 2 + S / 2x_i

which is the average of x_i and S / x_i.  Now why does this algorithm always overestimate?  Draw y(x) = x^2 – S.  With positive square roots, we’re always on the right half of the parabola.  Because y(x) is concave up, the next iteration of Newton’s method is always a little higher than the actual root no matter if x_i is too high or too low.  This is why we always round down.

2) If S = 5389 and X is 73, how do estimate S / X?  Well think about it this way: we’re looking for some number d such that (70 + 3)(70 + 3 + d) = 5389.  Expand these terms: 70^2 + 2*70*3 + 3^2 + 73d = 5389.  Therefore d = (5389 – 4900 – 420 – 9) / 73.  Easy peasy lemon squeezy.

If I may make a commentary, the ability to do square roots in your head will not get you a job.  There’s a reason why calculators were invented.  However, to many people, the fun of a magic show is trying to figure out how the magician did it.  And now you know why this trick works.  It’s not magic, it’s math, which is way more powerful.  This is a good way of understanding Newton’s Method, which is a powerful tool which is still used today.