A trivial inequality, and how to express its solution in the most cryptic way imaginable

February 19, 2012

Solutions to olympiad problems are seldom written with clarity in mind — just look at forum posts in the Art of Problem Solving. The author makes jumps and skips a bunch of steps, expecting the reader to fill in the gaps.

Usually this is not much of a problem — the missing steps become obvious when you sit down and think about what’s going on with a pencil and some paper. But sometimes, this is not the case.

The problem

One of the worst examples I’ve seen comes in the book Inequalities, A Mathematical Olympiad Approach. By all means, this is an excellent book. Anyways, here’s one of its easier problems — and you’re expected to solve it using the triangle inequality:

Prove that for all real numbers a and b,

||a|-|b|| \leq |a-b|

Attempt 1: Intuitive solution

It isn’t clear how the triangle inequality fits. If I weren’t required to use the triangle inequality, I might be tempted to do an intuitive, case-by-case argument.

Let’s visualize the absolute value of a-b as the difference between the two numbers on a number line. Now we compare this distance |a-b| with the distance after you take the absolute value of both of them, ||a|-|b||. If one of the numbers is positive and the other negative, we clearly have a smaller distance if we ‘reflect’ the negative one over. Of course, if they’re both positive, or they’re both negative, then nothing happens and the distances remain equal.

There, a simple, fairly clear argument. Now let’s see what the book says.

The book’s solution

Flip to the end of the book, and find

Consider |a|=|a-b+b| and |b|=|b-a+a|, and apply the triangle inequality.

Huh. Perhaps if you are better versed than I am in the art of solving inequalities, you’ll understand what this solution is saying. But I, of course, had no idea.

Maybe try the substitution they suggest. I only see one place to possibly substitute |a| for anything — and substituting gives ||a-b+b|-|b-a+a||. Now what? I don’t think I did it right — this doesn’t make any sense.

To be fair, I cheated a little bit in the first attempt: I didn’t use the triangle inequality. Fair enough — let’s solve it with the triangle inequality then and come back to see if the solution makes any sense now.

Attempt 2: Triangle inequality solution

A standard corollary to the triangle inequality of two variables is the following:

|a|-|b| \leq |a-b|

Combine this with the two variables switched around:

|b|-|a| \leq |b-a| = |a-b|

Combine the two inequalities and we get the desired

||a|-|b|| \leq |a-b|

Now let’s look at the solution again. Does it make sense? No, at no point here  did we do any |a-b+b| substitution. Clearly the authors were thinking of a different solution that happened to also use the triangle inequality. Whatever it was, I had no idea what the solution meant.

The book’s solution, decrypted

Out of ideas and hardly apt to let the issue rest, I consulted help online at a math forum. And look — it turns out that my solution was without a doubt the same solution as the book’s intended solution!

What the author meant was this: considering that |a| = |a-b+b|, we have |a| \leq |a-b|+|b| from the triangle inequality. Then, moving the |b| over we get |a|-|b| \leq |a-b|.

After that, the steps I took above are left to the reader.

Perhaps I’m a bit thick-headed, but your solution can’t possibly be very clear if a reader has the exact same solution yet can’t even recognize your solution as the same solution. Come to think of it, if I couldn’t even recognize the solution, what chance is there of anybody being able to follow the solution — especially if they’re new to inequalities?

Almost every one of the one-sentence phrasings of this solution I could think of would be clearer and less puzzling than the solution the book gives me.


Random Math Problems (1)

May 2, 2010

Probably any of these problems would be too small to include in a blog post on their own, so it might be more efficient (?) to put several of them together into one post.

The problems are not mine, and the solutions are not mine. They are just interesting problems I’ve come across when studying for math olympiads.

I hope to publish more collections of these random math problems in the future. That’s why I’m appending (1) to this post.

Problem 1

(From the 2010 Fermat contest)

Spheres can be stacked together into a tetrahedron (triangular pyramid). Here’s a visual (not created by me, from Wikipedia):

Each of the spheres in the tetrahedron has a number written on it. The top sphere is 1, and the number of any sphere is the sum of the numbers on the spheres in the layer above.

An internal sphere is defined as a sphere that is not on the outside, or in other words, touching exactly three spheres in the layer above.

In a tetrahedron with 13 layers, what is the sum of the numbers on all of the internal spheres?

Solution

Let’s draw out a few layers of the tetrahedron.
Hosted by imgur.com

Look for patterns.

There’s a few things that can be noticed-

  1. The numbers at the three corners of a layer are 1
  2. Any layer is highly symmetrical: in the last diagram the sequence (1 4 6 4 1) appears in the bottom row, as well as the left and right diagonals. We can rotate the tetrahedron and the numbers would still be the same.
  3. The numbers on the outside form Pascal’s triangle. The sequence (1 3 3 1) is the 4th row of Pascal’s triangle; (1 4 6 4 1) is the 5th, and so on.

The most important thing to look for is the fact that Pascal’s triangle appears in the tetrahedron.

Each row of Pascal’s triangle is one longer than the previous row. To calculate a row, overlap the previous row with the new row, like this:
Hosted by imgur.com

Here the number in a purple box is the number to the top-right of it plus the number to the top-left of it:
Hosted by imgur.com

Simple.

Notice that each number in the top gets added into exactly two boxes at the bottom.

Therefore the sum of the numbers in the bottom is twice the sum of the numbers in the top. 1 + 3 + 3 + 1 = 8, and 1 + 4 + 6 + 4 + 1 = 16.

This applies to any two rows. The sum of any row is twice the sum of the previous row.

Since the sum of the first row is 1, the sum of the second is 2, the sum of the third 4, and so on. We can even express this as a formula. The sum of the nth row is:

2^{n-1}

A similar idea applies to the layers of the tetrahedron.

In Pascal’s triangle, each number gets added to two places in the next row.

The tetrahedron is like Pascal’s triangle, in three dimensions. Each sphere in the tetrahedron sits on top of three spheres in the layer under it. So each number gets added to three different numbers in the next row.

Thus the sum of the numbers in any layer of the tetrahedron is 3 times the sum of numbers in the previous layer.

A formula for the sum of the nth layer of the tetrahedron:

3^{n-1}

What we really want is a formula for the middle numbers, or internal spheres. The internal spheres are the spheres that are not on the outer layer.

We know the formula for the sum of the whole layer, and we know the formula for any of the three ‘sides’ of a layer.

Hosted by imgur.com

The internal numbers would be the sum of the entire layer minus three times the sum of a side. To cover up for the three 1’s we’ve counted more than once, we add 3 to the result.

The formula for the sum of the internal numbers on the nth layer:

3^{n-1} - 3 \cdot 2^{n-1} + 3

The problem asks for the sum of the first to the thirteenth layer. Well, the first three layers don’t have any internal spheres so we start from the forth:

\begin{array}{l} \displaystyle\sum_{n=4}^{13} 3^{n-1} - 2^{n-1} + 3 \\ = (3^3 + 3^4 + \cdots + 3^{12}) \\ \quad - 3(2^3 + 2^4 + \cdots + 2^{12}) + 3 \cdot 10 \end{array}

We can use the sum of geometric series formula, or more easily calculate it by brute force. The answer would be 772626.

Problem 2

(From the 2008 Canadian Math Olympiad)
Hosted by imgur.com

In quadrilateral ABCD, CM splits the quadrilateral into two parts of equal area. AN also splits the quadrilateral into two parts of equal area. AB is the longest side of the quadrilateral.

Prove that MN bisects DB.

Solution

I’m going to use the equal sign to mean two figures with equal areas, not two figures that are congruent.

The triangles \triangle ANB and \triangle MCB are both half of ABCD, so their areas are equal. Then \triangle ANB = \triangle MCB.

\triangle ANB can be split into \triangle ANM + \triangle MNB, and similarly \triangle MCB can be split into \triangle MCN + \triangle MNB.

We know that \triangle ANB = \triangle MCB. By subtraction, \triangle AMN = \triangle MCN.

The triangles \triangle AMN and \triangle MCN share a common base, MN. Because their areas are equal, the perpendicular from A to MN is equal to the perpendicular from C to MN. Therefore AC || MN.

Now we draw a line through D, parallel to AC and MN. We extend AB and BC to meet this line (and we draw a couple of additional lines):
Hosted by imgur.com

Because XY || AC, \triangle ADC = \triangle AXC = \triangle AYC.

Here \triangle MCB = ADCM.

We can write ADCM as \triangle ADC + \triangle ACM. Since \triangle ADC = \triangle AXC, ADCN = \triangle XCM.

It follows that \triangle MCB = \triangle XCM, and XM = MB.

Similarly, ADCN = \triangle AYN. Then \triangle ANB = ADCN = \triangle AYN, and YN = NB.

Because XM = MB and YN = NB, the result follows that DK = KB.

Problem 3

(From the 2010 USAMO)

This problem actually appears in both the junior and senior USAMO taken about a week ago from time of writing. It’s problem 4 in the senior and problem 6 in the junior.

Hosted by imgur.com

\triangle ABC is a right triangle. BD bisects \angle ABC, and EC bisects \angle ACB.

Prove that the lines [AB, AC, BI, ID, CI, IE] cannot all have integer lengths.

Solution

I was really surprised at how short and simple the solution can be for this problem.

Because \angle BAC = 90, \angle ABC + \angle ACB = 90 and \angle IBC + \angle ICB = 45 because of the angle bisectors.

Then \angle BIC = 180-45 = 135.

First we apply the pythagorean theorem:

BC^2 = AB^2 + AC^2

We then apply the Law of Cosines:

BC^2 = IB^2 + IC^2 - 2 \cdot IB \cdot IC \cdot \cos 135

Combining the two, and substituting -\frac{1}{\sqrt{2}} for \cos 135:

\begin{array}{c} AB^2 + AC^2 = IB^2 + IC^2 + 2 \cdot IB \cdot IC \cdot \frac{1}{\sqrt{2}} \\ \frac{2 \cdot IB \cdot IC}{AB^2 + AC^2 - IB^2 - IC^2} = \sqrt{2} \end{array}

This is absurd, if AB, AC, IB, and IC are all integers and nonzero.


Follow

Get every new post delivered to your Inbox.

Join 69 other followers