348 Methods of Proof
62.Letbbe a boy dancing with the maximal number of girls. There is a girlg′he does
not dance with. Choose asb′a boy who dances withg′. Letgbe a girl who dances
withbbut not withb′. Such a girl exists because of the maximality ofb, sinceb′already
dances with a girl who does not dance withb. Then the pairs(b, g),(b′,g′)satisfy the
requirement.
(26th W.L. Putnam Mathematical Competition, 1965)
63.Let(aij)ij,1≤i≤m,1≤j≤n, be the matrix. Denote the sum of the elements
in theith row bysi,i= 1 , 2 ,...,m. We will show that among all matrices obtained by
permuting the elements of each column, the one for which the sum|s 1 |+|s 2 |+···+|sm|
is minimal has the desired property.
If this is not the case, then|sk|≥2 for somek. Without loss of generality, we can
assume thatsk≥2. Sinces 1 +s 2 +···+sm=0, there existsjsuch thatsj<0. Also,
there exists anisuch thataik>aij, for otherwisesj would be larger thansk. When
exchangingaikandaijthe sum|s 1 |+|s 2 |+···+|sm|decreases. Indeed,
|sk−aik+aij|+|sj+aik−aij|=sk−aik+aij+|sj+aik−aij|
<sk−aik+aij+|sj|+aik−aij,where the equality follows from the fact thatsk ≥ 2 ≥ aik−aij, while thestrict
inequality follows from the triangle inequality and the fact thatsjandaik−aij have
opposite signs. This shows that any minimal configuration must satisfy the condition
from the statement. Note that a minimal configuration always exists, since the number
of possible permutations is finite.
(Austrian–Polish Mathematics Competition, 1984)
64.We call a numbergoodif it satisfies the given condition. It is not difficult to see
that all powers of primes are good. Supposenis a good number that has at least two
distinct prime factors. Letn=prs, wherepis the smallest prime dividingnandsis not
divisible byp. Becausenis good,p+s−1 must dividen. For any primeqdividing
s,s<p+s− 1 <s+q,soqdoes not dividep+s−1. Therefore, the only prime
factor ofp+s−1isp. Thens=pc−p+1 for some integerc>1. Becausepcmust
also dividen,pc+s− 1 = 2 pc−pdividesn. Because 2pc−^1 −1 has no factors ofp,
it must divides. But
p− 1
2( 2 pc−^1 − 1 )=pc−pc−^1 −
p− 1
2<pc−p+ 1 <
p+ 1
2( 2 pc−^1 − 1 )=pc+pc−^1 −
p+ 1
2,
a contradiction. It follows that the only good integers are the powers of primes.
(Russian Mathematical Olympiad, 2001)
65.Let us assume that no infinite monochromatic sequence exists with the desired prop-
erty, and consider a maximal white sequence 2k 1 <k 1 +k 2 <···< 2 knand a maximal