Tuesday, March 24, 2009

Triangle Inequality on R

A bug lives on a line. The bug starts at point A and crawls to point B. Then she crawls to point C. We know that she always crawls at least as far going from A to B to C as if she had just crawled straight from A to C. How can we prove this fact mathematically?

If the points are identified as real numbers along the real line, then we have the distance between A and B defined to be

  • d(A, B) = B-A if B ≥ A, and
  • d(A, B) = A-B otherwise.

So now restating what we want to prove, given A, B, C in R, prove that d(A, B) + d(B, C) ≥ d(A,C).

One way to prove this is by a case analysis. There are six possible orderings of A, B, C on the line:

  1. A ≤ B ≤ C
  2. A ≤ C < B
  3. B < A ≤ C
  4. B ≤ C < A
  5. C < A ≤ B
  6. C < B < A
Question: Did we cover all the possible orders? How do you know?

I'll do two cases:

  • Case 1 is easy. If A ≤ B ≤ C then d(A, B) + d(B, C) = B-A + C-B = C-A = d(A, C).
  • Case 5 is a little trickier.
    If C < A ≤ B, then d(A, B) + d(B, C) = B-A + B-C = 2B-A-C.
    How does that relate to d(A, C) = A-C?
    We can approach this problem by observing what we want. We want d(A, B) + d(B, C) ≥ d(A, C),
    so we want 2B-A-CA-C
    so we want 2B-2A ≥ 0 (by adding A-C to both sides)
    so we want B-A >=0 (by dividing both sides by two)
    which is true because A ≤ B. So it will work out. We just have to run it backwards:
    We know A ≤ B, therefore B-A ≥ 0 therefore 2B-2A ≥ 0 therefore 2B-A-CA-C therefore d(A,B) + d(B,C) ≥ d(A,C).
The fact that's being proved seems obvious, but it requires a little creativity to actually do the proof for all six cases.

Teaching discussion:

  • Sometimes you just have to do all the cases. Students, especially kids, are reluctant to do a case analysis. Six cases seems like too much. But sometimes it's just the right way to solve a problem: enumerate the cases and solve each one.
  • I've seen people teach by doing something like:
    "We know A ≤ B, therefore B-A ≥ 0 therefore 2B-2A ≥ 0 therefore 2B-A-CA-C therefore d(A,B) + d(B,C) ≥ d(A,C)."
    It's just magic. How did you come up with that? Better when teaching is to show how to figure out what the magic sequence is. The "magic" is especially prevalent on proofs in analysis: You have to show "for every ε there is a δ" and you write down some magic formula for δ as a function of ε, and the students wonder where in the world that came from.

No comments:

Post a Comment

About Me

I work in the Google cloud now. Previously I worked in the Oracle cloud and before that I was research faculty at MIT, and Chief Architect at Tokutek. Before that I worked at Akamai, was a Yale CS professor, and worked at Thinking Machines.