Advanced book on Mathematics Olympiad

4 1 Methods of Proof

Solution.We prove this by induction on the numbernof lines. The base casen=1is
straightforward, color one half-plane black, the other white.
For the inductive step, assume that we know how to color any map defined byklines.
Add the(k+ 1 )st line to the picture; then keep the color of the regions on one side of this
line the same while changing the color of the regions on the other side. The inductive
step is illustrated in Figure 1.

Figure 1

Regions that were adjacent previously still have different colors. Regions that share

a segment of the(k+ 1 )st line, which were part of the same region previously, now lie

on opposite sides of the line. So they have different colors, too. This shows that the new

map satisfies the required property and the induction is complete. 

A classical proof by induction is that of Fermat’s so-called little theorem.

Fermat’s little theorem.Letpbe a prime number, andna positive integer. Thennp−n

is divisible byp.

Proof.We prove the theorem by induction onn. The base casen=1 is obvious. Let us

assume that the property is true forn=kand prove it forn=k+1. Using the induction

hypothesis, we obtain

(k+ 1 )p−(k+ 1 )≡kp+

p∑− 1

j= 1

(

p

j

)

kj+ 1 −k− 1 ≡

p∑− 1

j= 1

(

p

j

)

kj(modp).

The key observation is that for 1≤j≤p−1,

(p

j

)

is divisible byp. Indeed, examining

(

p

j

)

=

p(p− 1 )···(p−j+ 1 )

1 · 2 ···j

,

it is easy to see that when 1≤j ≤p−1, the numerator is divisible bypwhile the

denominator is not. Therefore,(k+ 1 )p−(k+ 1 )≡ 0 (modp), which completes the

induction.