Advanced book on Mathematics Olympiad

Combinatorics and Probability 767

We can obtain one hundred polygons with twenty sides by making 1699 cuts in the
following way. First, cut the square into 100 rectangles (99 cuts needed). Each rectangle
is then cut through 16 cuts into a polygon with twenty sides and some triangles. We have
performed a total of 99+ 100 · 16 =1699 cuts.
(Kvant(Quantum), proposed by I. Bershtein)

897.We give a proof by contradiction. Let us assume that the conclusion is false. We
can also assume that no problem was solved by at most one sex. Denote bybiandgi
the number of boys, respectively, girls, that solved problemi, and bypthe total number
of problems. Then sincebi,gi ≥1, it follows that(bi− 2 )(gi− 2 )≤ 1, which is
equivalent to

bigi≤ 2 (bi+gi)− 3.

Let us sum this over all problems. Note that condition (ii) implies that 441≤

∑

bigi.
We thus have

441 ≤

∑

bigi≤ 2 (bi+gi)− 3 ≤ 2 ( 6 · 21 + 6 · 21 )− 3 p= 504 − 3 p.

This implies thatp≤21, so 21 is an upper bound forp.
We now do a different count of the problems that will produce a lower bound forp.
Pairing a girl with each of the 21 boys, and using the fact that she solved at most six
problems, by the pigeonhole principle we conclude that some problem was solved by
that girl and 4 of the boys. By our assumption, there are at most two girls who solved
that problem. This argument works for any girl, which means that there are at least 11
problems that were solved by at least 4 boys and at most 2 girls. Symmetrically, 11 other
problems were solved by at least 4 girls and at most 2 boys. This shows thatp≥22, a
contradiction. The problem is solved.
(42nd International Mathematical Olympiad, 2001)

898.First, let us forget about the constraint and count the number of paths from( 0 , 0 )
and(m, n)such that at each step one of the coordinates increases by 1. There are a total
ofm+nsteps, out of whichngo up. Thesencan be chosen in

(m+n

n

)

ways from the total
ofm+n. Therefore, the number of paths is

(m+n

n

)

.

How many of these go through(p, q)? There are

(p+q

q

)

paths from( 0 , 0 )to(p, q)
and

(m+n−p−q

n−q

)

paths from(p, q)to(m, n). Hence

(

p+q

q

)

·

(

m+n−p−q

n−q

)

of all the paths pass through(p, q). And, of course,
(
r+s
s

)

·

(

m+n−r−s

n−s

)