Advanced book on Mathematics Olympiad

1.2 Mathematical Induction 7

18.Prove that for anyn≥1, a 2n× 2 ncheckerboard with 1×1 corner square removed

can be tiled by pieces of the form described in Figure 2.

19.Given a sequence of integersx 1 ,x 2 ,...,xnwhose sum is 1, prove that exactly one

of the cyclic shifts

x 1 ,x 2 ,...,xn; x 2 ,...,xn,x 1 ; ...; xn,x 1 ,...,xn− 1

has all of its partial sums positive. (By a partial sum we mean the sum of the first

kterms,k≤n.)

20.Letx 1 ,x 2 ,...,xn,y 1 ,y 2 ,...,ymbe positive integers,n, m > 1. Assume that

x 1 +x 2 +···+xn=y 1 +y 2 +···+ym<mn. Prove that in the equality

x 1 +x 2 +···+xn=y 1 +y 2 +···+ym

one can suppress some (but not all) terms in such a way that the equality is still

satisfied.

21.Prove that any function defined on the entire real axis can be written as the sum of

two functions whose graphs admit centers of symmetry.

22.Prove that for any positive integern≥2 there is a positive integermthat can be

written simultaneously as a sum of 2, 3 ,...,nsquares of nonzero integers.

1

1

Figure 2

Even more powerful is strong induction.

Induction principle (strong form).GivenP (n)a property that depends on an integern,

(i)ifP(n 0 ), P (n 0 + 1 ),...,P(n 0 +m)are true for some positive integern 0 and non-
negative integerm, and
(ii)if for everyk>n 0 +m,P(j)true for alln 0 ≤j<kimpliesP(k)true,

thenP (n)is true for alln≥n 0.

We use strong induction to solve a problem from the 24th W.L. Putnam Mathematical
Competition.