Advanced book on Mathematics Olympiad

Combinatorics and Probability 761

ofC(this can be done in 2m−iways). Then choosek−iof then−mY’s (in

(n−m

k−i

)

ways) and replace each of them byA, and replace the remainingY’s byC. We have
constructed

(m

i

)(n−m

k−i

)

2 m−iwords satisfying the conditions. Summing overi, we obtain
the right-hand side of the identity.
(Mathematics Magazine, the casem=k−1 proposed by D. Callan, generalization
and solution by W. Moser)

883.For a counting argument to work, the identity should involve only integers. Thus it
is sensible to write it as

∑q

k= 0

2 q−k

(

p+k

k

)

+

∑p

k= 0

2 p−k

(

q+k

k

)

= 2 p+q+^1.

This looks like the count of the elements of a set partitioned into two subsets. The right-
hand side counts the number of subsets of a set withp+q+1 elements. It is better to
think of it as the number of elements of{ 0 , 1 }n. We partition this set into two disjoint sets
AandBsuch thatAis the set ofn-tuples with at leastp+1 entries equal to 1, andB, its
complement, is the set ofn-tuples with at leastq+1 entries equal to 0. If the position of
the(p+ 1 )st1isp+k+1, 0≤k≤q, then there are

(p+k

p

)

=

(p+k

k

)

ways of choosing
the positions of the firstpones. Several subsequent coordinates can also be set to 1, and
this can be done in 2q−kways. It follows that 2q−k

(p+k

k

)

elements inAhave the(p+ 1 )st
1 in positionp+k+1. Therefore, the first sum counts the elements ofA. Similarly, the
second sum counts the elements ofB, and the conclusion follows.
(French contest, 1985, solution from T.B. Soulami,Les olympiades de mathéma-
tiques: Réflexes et stratégies, Ellipses, 1999)

884.A group of 2n+1 people, consisting ofnmale/female couples and one extra male,
wish to split into two teams. Team 1 should havenpeople, consisting ofn 2 women and
n+ 21 men, while Team 2 should haven+1 people, consisting ofn 2 women andn+ 21 
men, wherexdenotes the least integer greater than or equal tox. The number of ways
to do this is counted by the first team, and iscncn+ 1.
There is a different way to count this, namely by the numberkof couples that are
split between the two teams. The single man joins Team 1 if and only ifkandnhave
opposite parity. The split couples can be chosen in

(n

k

)

ways. From the remainingn−k
couples, the number to join Team 1 isn− 2 k, which can be chosen incn−kways. Since
these couples contributen− 2 kwomen to Team 1, the number of women from theksplit
couples that join Team 1 must ben 2 −n− 2 k, which equals eitherk 2 fornodd ork 2 
forneven. Since

( k

k/ 2 

)

=

( k

k/ 2 

)

, these women can be chosen inckways. Thus the left
side also counts the choices.
(American Mathematical Monthly, proposed by D.M. Bloom, solution by Ch.N.
Swanson)