Induction for Fields Circle

Posted in Math by pgadey on 2013/03/01

Below the cut are some induction related questions I collected together for a Math Circle at the Fields Institute.

1. Simple inductive constructions

Exercise 1 Consider a circle with ${n}$ chords (a chord is a line segment having its endpoints on the perimeter of the circle). Show that regions bounded by the chords can be coloured black and white such that no two adjacent regions (regions which share an edge) are the same colour.

Exercise 2 Consider a race track of length ${L}$. Suppose that ${n}$ cars are stranded on the track. Suppose each car moves one unit of distance per unit per unit of fuel and that when two cars meet they can exchange fuel losslessly. Show that if the sum total of fuel among all the cars is ${L}$ then the is a car that can make a complete lap around the track.

Exercise 3 (Towers of Hanoi) Show that one can move all the discs from the first peg to the third peg, moving one disc at a time, and in such a way that no disc ever rests on top of a disc smaller than it.

2. Layered inductive proofs

Exercise 4 (Pick’s Theorem) Let ${P}$ be a simple closed polygon in ${{\mathbb R}^2}$ with all its vertices on lattice points. Let ${I}$ be the number of lattice points in the interior of ${P}$, ${B}$ be the number of lattice points on the boundary of ${P}$, and ${V}$ be the number of vertices of ${P}$. Show that the area of ${P}$ is:

$\displaystyle A(P) = I + B/2 - 1$

Exercise 5 (AM-GM á la Gauss) Show that for positive numbers ${x_1, x_2, \dots, x_{2^n}}$ one has

$\displaystyle \sqrt[2^n]{x_1 \dots x_{2^n}} \leq \frac{x_1 + \dots + x_{2^n} }{ 2^n }$

with equality iff ${x_1 = \dots = x_{2^n}}$.

Tagged with: ,