Advanced book on Mathematics Olympiad

Combinatorics and Probability 763

x 1 +x 2 +···+xm=n−xm+ 1.

Asxm+ 1 ranges between 0 andn, the right-hand sides assumes all values between 0 and
n. Using the induction hypothesis for all these cases and summing up, we find that the
total number of solutions is
∑n

r= 0

(

m+r− 1

m− 1

)

.

As before, this sums up to

(m+n

m

)

, proving the formula form+1 unknowns. This completes

the solution.

Second solution: Letyi=xi+1. Theny 1 ,...,ymis a solution in positive integers to

the equationy 1 +y 2 +···+ym=n+m. These solutions were counted in one of the

examples discussed at the beginning of this section.

888.Since each tennis player playedn−1 games,xi+yi=n−1 for alli. Altogether

there are as many victories as losses; hencex 1 +x 2 +···+xn=y 1 +y 2 +···+yn.

We have

x 12 +x 22 +···+xn^2 −y 12 −y 22 −···−yn^2 =(x 12 −y 12 )+(x 22 −y^22 )+···+(x^2 n−yn^2 )

=(x 1 +y 1 )(x 1 −y 1 )+(x 2 +y 2 )(x 2 −y 2 )+···+(xn+yn)(xn−yn)

=(n− 1 )(x 1 −y 1 +x 2 −y 2 +···+xn−yn)

=(n− 1 )(x 1 +x 2 +···+xn−y 1 −y 2 −···−yn)= 0 ,

and we are done.

(L. Panaitopol, D. ̧Serbanescu, ̆ Probleme de Teoria Numerelor ̧si Combinatorica

pentru Juniori(Problems in Number Theory and Combinatorics for Juniors), GIL, 2003)

889.LetB={b 1 ,b 2 ,...,bp}be the union of the ranges of the two functions. Forbi∈B,

denote bynbithe number of elementsx∈Asuch thatf(x)=bi, and bykbithe number

of elementsx∈Asuch thatg(x)=bi. Then the number of pairs(x, y)∈A×Afor

whichf(x)=g(x)=biisnbikbi, the number of pairs for whichf(x)=f(y)=biis

n^2 bi, and the number of pairs for whichg(x)=g(y)=biisk^2 bi. Summing overi,we

obtain

m=nb 1 kb 1 +nb 2 kb 2 +···+nbpkbp,

n=n^2 b 1 +n^2 b 2 +···+n^2 bp,

k=k^2 b 1 +k^2 b 2 +···+kb^2 p.

The inequality from the statement is a consequence of the inequality 2ab≤a^2 +b^2.

(T.B. Soulami,Les Olympiades de Mathématiques: Réflexes et stratégies, Ellipses,

1999)