- #1
limitkiller
- 80
- 0
"The numbers 1, 2, . . . , 5n are divided into two disjoint sets. Prove that these
sets contain at least n pairs (x, y), x > y, such that the number x -y is also an
element of the set which contains the pair."
proof:"Suppose, for the sake of contradiction, that there are two sets A and B such
that AU B = {I, 2, ... , 5n}, An B = 0 and the sets contain together less than n pairs (x, y), x > y, with the desired property.
Let k be a given number, k = 1, n. If k and 2k are in the same set - A or B -
the same can be said about the difference 2k - k = k. The same argument is applied
for 4k and 2k. Consider the case when k and 4k are elements of A and 2k is an
element of B. If 3k is an element of A, then 4k - 3k = k E A, so let 3k E B. Now if
5k E A, then 5k - 4k = k E A and if 5k E B, then 5k - 3k = 2k E B; so among the
numbers k, 2k, 3k, 4k, 5k there is at least a pair with the desired property. Because
k = 1 , 2, ... , n, it follows that there are at least n pairs with the desired property. (Dorin Andrica, Revista Matematica Timi§oara (RMT) , No. 2(1978), pp. 75,
Problem 3698)"(E means belongs to)
The proof given by the book doesn't seem to work.
Does anybody know of a proof?
sets contain at least n pairs (x, y), x > y, such that the number x -y is also an
element of the set which contains the pair."
proof:"Suppose, for the sake of contradiction, that there are two sets A and B such
that AU B = {I, 2, ... , 5n}, An B = 0 and the sets contain together less than n pairs (x, y), x > y, with the desired property.
Let k be a given number, k = 1, n. If k and 2k are in the same set - A or B -
the same can be said about the difference 2k - k = k. The same argument is applied
for 4k and 2k. Consider the case when k and 4k are elements of A and 2k is an
element of B. If 3k is an element of A, then 4k - 3k = k E A, so let 3k E B. Now if
5k E A, then 5k - 4k = k E A and if 5k E B, then 5k - 3k = 2k E B; so among the
numbers k, 2k, 3k, 4k, 5k there is at least a pair with the desired property. Because
k = 1 , 2, ... , n, it follows that there are at least n pairs with the desired property. (Dorin Andrica, Revista Matematica Timi§oara (RMT) , No. 2(1978), pp. 75,
Problem 3698)"(E means belongs to)
The proof given by the book doesn't seem to work.
Does anybody know of a proof?