Posts Tagged ‘high school math’

2^n \geq n: The graph theory proof?

February 15, 2010

Theorem. For every positive integer n, 2^n \geq n.

Proof. Consider a tree on n vertices T = (V, E) with root v_0. Assign to each edge \{v, w\} an element of the vector space GF(2)^V, obtained by setting 1s in the the coordinates corresponding to v and w and 0s elsewhere. I claim that these vectors are linearly independent; for suppose otherwise, and letthe vectors corresponding to S \subset E sum to 0. There is a natural “distance” function on E w/r/t v_0; let e_0 = \{s, t\} have maximal distance in S, and suppose WLOG that t is farther than s from v_0. Then the coordinate corresponding to t is nonzero for exactly one element of S, and the sum over all elements of S must therefore be nonzero. This is a contradiction. So in particular these |E| = n-1 elements are distinct and nonzero, which means (by Pigeonhole) that there are at most 2^n-1 of them.



The extremal toolbox: A matrix problem

January 10, 2010

I’m starting a new series of posts this semester where I get “back to basics.” One of the few areas of mathematics in which I can claim anything even in the same connected component as “expertise” is extremal combinatorics. Unfortunately for me and my lazy, big-picture brain, though, extremal combinatorics is very much a “problem-solving” subject, with a relatively small number of tools that are used to solve all sorts of different problems. So without some practice solving these problems, or expositing the solutions, it’s easy to get rusty.

Hence, “The Extremal Toolbox.” In each post, I’ll take a (solved!) problem in extremal combinatorics — anything from Sperner’s theorem to Kakeya over finite fields, as long as there’s an extremal flavor — and try to break down a proof into its component parts.

Today I’m going to examine a problem which appeared on MathOverflow some time ago, which I didn’t quite solve (but came within epsilon of!) The relevant post is here; if you don’t care to click through, here’s the problem.

Let M be an n \times n matrix with non-negative integer entries. Suppose further that if m_{ij} is 0, then the sum of all the entries in the ith row or the jth column is at least n. Then the sum of all the entries in M is at least n^2/2.


The derivative of x^2

June 21, 2009

A commenter on Scott Aaronson’s blog, in a discussion of K-12 mathematics education in the U.S., brought up the following (I would imagine fairly common) Algebra I fallacy:

The slope of the line y = mx + b is equal to m. Consider the equation y = x*x + 0. Around x = c, this reduces to y = c*x, and so the slope of the parabola y = x^2 at the point (x, x^2) is x.

Of course, anyone who has taken freshman calculus knows that the slope of the parabola at that point is 2x, not x, and therefore the above reasoning is flawed in some way. But from the perspective of a beginning Algebra I student, there’s nothing at all obviously wrong with it!

So how would one go about deriving (no pun intended) the correct slope of a parabola using only basic Algebra I knowledge? You might imagine that you could just calculate the “rise over run,” and that’s a good start — ((x+h)^2 – x^2)/h = 2x + h. But (without the crucial “take the limit as h approaches 0”) this is ill-defined!

It’s clear that if you could prove the product rule for derivatives, then the correct expression for the slope would follow. Still, though, it seems impossible to do this with such a basic level of knowledge, without resorting to the concept of a limit or an infinitesimal.

The most promising path would likely be to show that y = x^2 actually looks locally like y = 2cx – c^2, rather than y = cx. Actually, it isn’t that difficult to show that y = cx is wrong; if you draw “tangent lines” to the parabola for large enough values of c, it’s clear that those lines don’t come anywhere near the origin. Still, 2cx – c^2 seems incredibly arbitrary without foreknowledge of the calculus.

So, here’s the challenge: How do you convince a reasonably bright Algebra I student, without getting into calculus, that the slope of the parabola is not x but is, in fact, 2x?