340 Methods of Proof
| |≥
n(n− 1 )(n− 3 )
2.
To apply the pigeonhole principle, we let the “holes’’ be the ordered pairs of people
(a, b), and the “pigeons’’ be the triples(a,b,c)∈. Put the pigeon(a,b,c)in the
hole(a, b)ifcknows either both or neither ofaandb. There aren(n−^12 )(n−^3 )pigeons
distributed inn(n− 1 )holes. So there will be at least
⌈
n(n− 1 )(n− 3 )
2
/
n(n− 1 )⌉
=
⌊n
2⌋
− 1
pigeons in one hole, wherex denotes the least integer greater than or equal tox.To
the “hole’’ corresponds a pair of people satisfying the required condition.
(USA Mathematical Olympiad, 1985)
43.The beautiful observation is that if the sequencean=cos(nπ x 1 )+cos(nπ x 2 )+···+
cos(nπ xk),n≥1, assumes finitely many distinct values, then so does the sequence of
k-tuplesun=(an,a 2 n,...,akn),n≥1. By the pigeonhole principle there existm<n
such thatan=am,a 2 n=a 2 m,...,akn=akm. Let us take a closer look at these relations.
We know that cos(nx)is a polynomial of degreenwith integer coefficients in cos(x),
namely the Chebyshev polynomial. IfAi=cos(nπ xi)andBi=cos(mπ xi), then the
previous relations combined with this observation show thatAj 1 +Aj 2 + ··· +Ajk =
B 1 j+B 2 j+ ··· +Bjkfor allj = 1 , 2 ,...,k. Using Newton’s formulas, we deduce
that the polynomials having the zerosA 1 ,A 2 ,...,Ak, respectively,B 1 ,B 2 ,...,Bkare
equal (they have equal coefficients). Hence there is a permutationσof 1, 2 ,...,nsuch
thatAi =Bσ(i). Thus cos(nπ xi)=cos(mπ xσ(i)), which means thatnxi−mxσ(i)is a
rational numberrifor 1≤i≤k. We want to show that thexi’s are themselves rational.
Ifσ(i)=i, this is obvious. On the other hand, if we consider a cycle ofσ,(i 1 i 2 i 3 ...is),
we obtain the linear system
mxi 1 −nxi 2 =ri 1 ,
mxi 2 −nxi 3 =ri 2 ,
···
mxis−nxi 1 =ris.It is not hard to compute the determinant of the coefficient matrix, which isns−ms(for
example, by expanding by the first row, then by the first column, and then noting that
the new determinants are triangular). The determinant is nonzero; hence the system has
a unique solution. By applying Cramer’s rule we determine that this solution consists of
rational numbers. We conclude that thexi’s are all rational, and the problem is solved.
(V. Pop)
44.Place the circle at the origin of the coordinate plane and consider the rectangular
grid determined by points of integer coordinates, as shown in Figure 48. The circle is