A short introduction to Graph Theory is needed for this one. If you already are familiar with Graph Theoretic constructs feel free to skip it.

A graph G, is a pair (V,E) where V is a set of vertices and E is a set of edges. Each edge is an unordered pair of the form (u, v) where u and v are vertices (i.e. they belong to V). The degree of a vertex t (denoted deg(t)) is the number of edges containing it:

deg(t) = #{ e | e = (s, t) ^ s belongs to V }

In this post I only consider finite and simple graphs. A finite graph is a graph whose vertex-set V is a finite set. A simple graph is a graph in which there are no loops (i.e. edges of the form (u, u)) and no multiple edges (i.e. E is a proper set so it cannot contain the same element twice).

The following is a trivial claim:

The sum of the degrees in a graph equals twice the number of edges.

It is trivial to prove this claim by induction on the number of edges (on a graph with no edges it is clear, and by adding an edge to the edge set of the graph the sum of degrees increases by two).

Use this claim to solve the following riddle:

A rectangle is called whole if at least one of its sides is an integer. For example, a rectangle of 2 by 3/5 is whole as well as a rectangle of sqrt(5) by 3. A rectangle of 1/2 by 1/2 is not whole. Examples:

A set T of rectangles constitues a tiling of a rectangle R if the rectangles in T are disjoint and for every point p in R there is a rectangle S in T such that p belongs to S. Example:

Prove that if R is a rectangle and T is a tiling of R consisting only of whole rectangles (i.e. every rectangle S in T is whole) then R is whole.

Pages: 1 2

This entry was posted on Friday, May 25th, 2007 at 9:16 pm and is filed under Math, Riddles. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.