## Induction for Fields Circle

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

**1. Simple inductive constructions **

Exercise 1Consider a circle with 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 2Consider a race track of length . Suppose that 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 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 be a simple closed polygon in with all its vertices on lattice points. Let be the number of lattice points in the interior of , be the number of lattice points on the boundary of , and be the number of vertices of . Show that the area of is:

Exercise 5 (AM-GM รก la Gauss)Show that for positive numbers one has

with equality iff .

leave a comment