November 23, 2009

A Small Subset of the Reals

Monet Let {qn} be an enumeration of the rationals, and for each n, let Un be an open interval of length 1/2n centered at qn. Denote the union of all Un by U. Then U is a dense open subset of the reals which has measure at most 1.

From a topological point of view, this certainly seems to be a reasonable observation. After all, the rationals are dense and have measure zero, so it isn't surprising that by making the measure positive one can add the condition of openness. But from a more direct perspective, the construction seems to yield a very strange set--a spattering of droplets across the real line which cover very little length but come arbitrarily close to any point. Like an Impressionist painting, one must add a little distance to make out the comprehensible form.

Image by Claude Monet.

A Dinner Party Problem

Figure 1This is a classic introductory result in combinatorics. Suppose that six people are gathered at a dinner party. Then there is a group of three people at the party who are either all mutual acquaintances or all mutual strangers.

To formalize this problem, consider the party as a complete graph on six vertices, as in the figure to the left. Each vertex represents a single guest, and each edge is colored by either blue, to represent that the connected vertices are acquaintances, or by yellow, to represent that the connected vertices are strangers. Then the result states that there exists a complete subgraph on three vertices with edges all the same color.

Figure 2To see this, pick a vertex of the graph. Then because there are five edges going from this vertex to other vertices, there must be at least three edges which have the same color. Assume without loss of generality that the three edges are blue, as in the figure to the right. Then if there is a blue edge between any of the three vertices connected to the chosen vertex (vertices 3, 4 and 6 in the figure), then there is a complete same-colored subgraph, and the result holds.

Figure 3So suppose instead that there are no blue edges between the three nodes. Then all three of the edges must be yellow, as in the figure to the left, and this forms a complete same-colored subgraph of the opposite color. Thus no matter the choice of coloring on the graph, we can find a same-colored complete subgraph on three vertices. As for the dinner party, we certainly can find a group of three people with the desired property, if we only care to look.

November 21, 2009

An Equation With Squares

Let k ≥ 0, and let n = k(2k + 1). Then we have:

n2 + (n+1)2 + ... + (n+k)2 = (n+k+1)2 + ... + (n+2k)2.

For example,
02 = 0,
32 + 42 = 52,
102 + 112 + 122 = 132 + 142,
212 + 222 + 232 + 242 = 252 + 262 + 272,
and so on.