12 1 Methods of Proof
The third example comes from the 67th W.L. Putnam Mathematical Competition,
2006.
Example.Prove that for every setX={x 1 ,x 2 ,...,xn}ofnreal numbers, there exists a
nonempty subsetSofXand an integermsuch that
∣∣
∣∣
∣
m+∑
s∈Ss∣∣
∣∣
∣
≤
1
n+ 1.
Solution.Recall that the fractional part of a real numberxisx−x. Let us look at the
fractional parts of the numbersx 1 ,x 1 +x 2 ,..., x 1 +x 2 +···+xn. If any of them is
either in the interval[ 0 ,n+^11 ]or[nn+ 1 , 1 ], then we are done. If not, we consider thesen
numbers as the “pigeons’’ and then−1 intervals[n+^11 ,n+^21 ],[n+^21 ,n+^31 ],...,[nn−+^11 ,n+n 1 ]
as the “holes.’’ By the pigeonhole principle, two of these sums, sayx 1 +x 2 +···+xkand
x 1 +x 2 +···+xk+m, belong to the same interval. But then their differencexk+ 1 +···+xk+m
lies within a distance ofn^1 + 1 of an integer, and we are done.
More problems are listed below.33.Given 50 distinct positive integers strictly less than 100, prove that some two of
them sum to 99.
34.A sequence ofmpositive integers contains exactlyndistinct terms. Prove that if
2 n≤mthen there exists a block of consecutive terms whose product is a perfect
square.
35.Letx 1 ,x 2 ,x 3 ,...be a sequence of integers such that1 =x 1 <x 2 <x 3 <··· and xn+ 1 ≤ 2 n forn= 1 , 2 , 3 ,....Show that every positive integerkis equal toxi−xjfor someiandj.
36.Letpbe a prime number anda, b, cintegers such thataandbare not divisible by
p. Prove that the equationax^2 +by^2 ≡c(modp)has integer solutions.
37.In each of the unit squares of a 10×10 checkerboard, a positive integer not exceeding
10 is written. Any two numbers that appear in adjacent or diagonally adjacent
squares of the board are relatively prime. Prove that some number appears at least
17 times.
38.Show that there is a positive term of the Fibonacci sequence that is divisible by 1000.
39.Letx 1 =x 2 =x 3 =1 andxn+ 3 =xn+xn+ 1 xn+ 2 for all positive integersn. Prove
that for any positive integermthere is an indexksuch thatmdividesxk.