Advanced book on Mathematics Olympiad

772 Combinatorics and Probability

We count these points using the inclusion–exclusion principle. The first coordinate

of the current pointP =(tw, tl, th),0<t≤1, on the diagonal is a positive integer

for exactlywvalues oft, namely,t=w^1 ,^22 ,...,ww. The second coordinate is an integer

forlvalues oft, and the third coordinate is an integer forhvalues oft. However, the

sumw+l+hdoubly counts the points with two integer coordinates, and triply counts

the points with three integer coordinates. The first two coordinates are integers precisely

whent=gcdk(w,l), for some integerk,1≤k≤gcd(w, l). Similarly, the second and third

coordinates are positive integers for gcd(l, h), respectively, gcd(h, w)values oft, and

all three coordinates are positive integers for gcd(w,l,h)values oft.

The inclusion–exclusion principle shows that the diagonal passes through the interi-

ors of

w+l+h−gcd(w, l)−gcd(l, h)−gcd(h, w)+gcd(w,l,h)

small cubes. Forw= 150 ,l= 324 ,h=375 this number is equal to 768.

(American Invitational Mathematics Examination, 1996)

906.Because the 1997 roots of the equation are symmetrically distributed in the complex

plane, there is no loss of generality to assume thatv=1. We are required to find the

probability that

| 1 +w|^2 =|( 1 +cosθ)+isinθ|^2 = 2 +2 cosθ≥ 2 +

√

3.

This is equivalent to cosθ≥^12

√

3, or|θ|≤π 6. Becausew  =1,θis of the form± 19972 kπk,

1 ≤k ≤^199712 . There are 2· 166 =332 such angles, and hence the probability is

332

1996 =

83
499 ≈^0 .166.
(American Invitational Mathematics Examination, 1997)
907.It is easier to compute the probability that no two people have the same birthday.
Arrange the people in some order. The first is free to be born on any of the 365 days. But
only 364 dates are available for the second, 363 for the third, and so on. The probability
that no two people have the same birthday is therefore

364

365

·

363

365

···

365 −n+ 1

365

=

365!

( 365 −n)! 365 n

.

And the probability that two people have the same birthday is

1 −

365!

( 365 −n)! 365 n

.

Remark.Starting withn =23 the probability becomes greater than^12 , while when

n>365 the probability is clearly 1 by the pigeonhole principle.