762 Combinatorics and Probability
885.We count the points of integer coordinates in the rectangle
1 ≤x≤p′, 1 ≤y≤q′.Their total number isp′q′. Now let us look at the expression in the first set of parentheses.
The terms count the number of points with integer coordinates that lie below the line
y=pqxand on the linesx= 1 ,x= 2 ,...,x=p′. Here it is important to remark that
sincepandqare coprime, none of these points lie on the liney=qpx. Similarly, the
expression in the second parentheses counts the number of points with integer coordinates
that lie above the liney=pqxand on the linesy= 1 ,y= 2 ,...,y=q′. These are all
the points of the rectangle. That there are no others follows from the inequalities
⌊
p′q
p
⌋
≤q′ and⌊
q′p
q⌋
≤p′.Indeed,
⌊
p′q
p⌋
=
⌊
p′( 2 q′+ 1 )
2 p′+ 1⌋
=
⌊
q′+^12
1 + 21 p′⌋
≤
⌊
q′+1
2
⌋
=q′,and the other inequality is similar.
Thus both sides of the identity in question count the same points, so they are equal.
(G. Eisenstein)
886.First solution: For each pair of students, consider the set of those problems not
solved by them. There are
( 200
2)
such sets, and we have to prove that at least one of them
is empty.
For each problem there are at most 80 students who did not solve it. From these
students at most
( 80
2)
=3160 pairs can be selected, so the problem can belong to at most
3160 sets. The 6 problems together can belong to at most 6·3160 sets.
Hence at least 19900− 18960 =940 sets must be empty, and the conclusion follows.
Second solution: Since each of the six problems was solved by at least 120 students, there
were at least 720 correct solutions in total. Since there are only 200 students, there is
some student who solved at least four problems. If a student solved five or six problems,
we are clearly done. Otherwise, there is a student who solved exactly four. Since the
two problems he missed were solved by at least 120 students, there must be a student (in
fact, at least 40) who solved both of them.
(9th International Mathematical Competition for University Students, 2002)
887.First solution: We prove the formula by induction onm. Form=1 it clearly is
true, since there is only one solution,x 1 =n. Assume that the formula is valid when
the number of unknowns isk≤m, and let us prove it form+1 unknowns. Write the
equation as