set problem

limitkiller

"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 doesnt seem to work.
Does anybody know of a proof?

haruspex

I agree, the proof is broken. The same pair can satisfy the 5 multiples of more than one k, e.g. (2, 4) is in both (1, 2, 3, 4, 5) and (2, 4, 6, 8, 10).
It isn't even clear whether the claim is that the pairs are disjoint. E.g. would 5-1=4 and 5-2=3 constitute 2 pairs? I guess so.
The attempted proof is only scratching the surface for the possible combinations, so I expect the claim is true. Doesn't look easy though.

who_

Hmm, I think the proof is salvageable. I will call the pairs with the property that the difference appears in its set a good pair. Basically, the only times you can have those "overlaps" is when 2k and 4k of {k,2k,...,5k} are in the same set. However, if we can guarantee that there must be another distinct good pair (by distinct, I mean BOTH numbers are different) among either {k,...,5k} or {2k,4k,...,10k}. From here on, I will let S_k = {k,2k,3k,4k,5k}.

So if S_k is split such that there is another good pair, then we are done.

Otherwise, (2k,4k) is the only good pair contributed by S_k, and so it must be split like: (2k,4k) and (k,3k,5k); (2k,3k,4k) and (1k,5k); or (2k,4k,5k) and (1k,3k).

Now let us try to place 6k, 8k, and 10k into those two sets. If 6k or 8k is placed with (2k,4k), we are done. Otherwise, 6k and 8k must go in the other set with 1k. If 5k is with 1k or 3k is with 1k, then we are done, since 6k - 5k = k and 6k - 3k = 3k. Thus, no matter what, there must be another good pair among S_k U S_{2k}.

Now we proceed by induction. The statement is clearly true for n = 1. Assume it is true for some n >= 1, and consider the case for n+1. If n+1 is odd, then we are done (S_{n+1} contributes at least one good pair, and it cannot overlap with any other previously found pair since n+1 is odd).
If n+1 is even, let m = (n+1)/2. If S_{n+1} contributes a good pair that is not (2m,4m) = (n+1,2(n+1)), then we are done. Otherwise, say that S_{n+1} can only contribute (2m,4m).
Then consider the good pair S_m contributes. By above, S_m must contribute another good pair that is not (2m,4m). If m is not even or that other good pair is not (m,2m), then we are done. Otherwise, we may repeat the subprocess again, and this process must terminate since m can be divisible by only a finite power of 2.

This completes the proof.

Sorry if the proof is a bit messy and full of bad notation. But I think this fixes the hole in the proof.

who_

Hmm, I think the proof is salvageable. I will call the pairs with the property that the difference appears in its set a good pair. Basically, the only times you can have those "overlaps" is when 2k and 4k of {k,2k,...,5k} are in the same set. However, if we can guarantee that there must be another distinct good pair (by distinct, I mean BOTH numbers are different) among either {k,...,5k} or {2k,4k,...,10k}, then we should be fine. From here on, I will let S_k = {k,2k,3k,4k,5k}.

So if S_k is split such that there is another good pair besides (2k,4k), then we are done.

Otherwise, (2k,4k) is the only good pair contributed by S_k, and so it must be split like: (2k,4k) and (k,3k,5k); (2k,3k,4k) and (1k,5k); or (2k,4k,5k) and (1k,3k).

Now let us try to place 6k, 8k, and 10k into those two sets. If 6k or 8k is placed with (2k,4k), we are done. Otherwise, 6k and 8k must go in the other set with 1k. If 5k is with 1k or 3k is with 1k, then we are done, since 6k - 5k = k and 6k - 3k = 3k. Thus, no matter what, there must be another good pair among S_k U S_{2k}.

Now we proceed by induction. The statement is clearly true for n = 1. Assume it is true for some n >= 1, and consider the case for n+1. If n+1 is odd, then we are done (S_{n+1} contributes at least one good pair, and it cannot overlap with any other previously found pair since n+1 is odd).
If n+1 is even, let m = (n+1)/2. If S_{n+1} contributes a good pair that is not (2m,4m) = (n+1,2(n+1)), then we are done. Otherwise, say that S_{n+1} can only contribute (2m,4m).
Then consider the good pair S_m contributes. By above, S_m must contribute another good pair that is not (2m,4m). If m is not even or that other good pair is not (m,2m), then we are done. Otherwise, we may repeat the subprocess again, and this process must terminate since m can be divisible by only a finite power of 2.

This completes the proof.

Sorry if the proof is a bit messy and full of bad notation. But I think this fixes the hole in the proof.

limitkiller

Thanks for the replies.

Yes,this is what I meant.

Why? lets say we had {k,2k,...,5k,6k,..nk}.Which numbers can overlap now?

it ignores that {2,4,6,8,10} and {4,8,12,16,20} have 4 and 8 in common,doesnt it? (it only investigates k = n and n+1 but we can have other instances)



I think you should investigate n and 2n rather than n and n+1.(I do not have a proof but overlappings seem to be only in n and 2n)

The proof seems to be correct but I cant understand why (2m,4m) is the only pair which can overlap.

who_

[EDIT] Now that I look at it more carefully, I think there is a BIG hole in my proof >< My mistake and apologies. I guess doing this at 3 in the morning is not the best way to go. I'll see if I can salvage this again.

Given S_k and S_{2k}, the only good pair those two can be possibly offered by both is (2k,4k), since S_k n S_{2k} = {2k,4k}. So (2k,4k) can be the only overlapping good pair between S_k and S_{2k}. If S_m and S_n are such that m =/= 2n and n =/=2m, then the two sets cannot have overlapping pairs.

limitkiller

Is it though?
I mean how do we know that s_k and s_2k are the only good pairs?

who_

Okay, I think I have a fix. Let my make my proof more rigorous.

Okay, oh man. The proof I have is really messy and involves a lot of case work. The proof is I have is 2 pages long, so I'm not going to bother to post it up, unless you are a masochist and would still like the proof. I'll see if I can find a better proof.

who_

What I mean is that if there were a good pair that came from both S_k and S_{2k}, then that pair would have to be (2k,4k). There could be other pairs contributed by S_k and S_{2k}, but those cannot appear both in S_k and S_{2k}.

Okay, I think I have a fix. Let my make my proof more rigorous.

Okay, oh man. The proof I have is really messy and involves a lot of case work. The proof is I have is 2 pages long, so I'm not going to bother to post it up, unless you are a masochist and would still like the proof. :) I'll see if I can find a better proof.

limitkiller

I most certainly am.
If the proof works I wont mind reading it.

does your proof use the fact that k and k+1 are coprimes and if a good pair is in the form s_k and s_k+1 ,k should be less than 5?and then extending it and checking some special cases?

if not please give a brief version of your proof.for example remove parts where you think are easy to understand and/or are obvious.

limitkiller

What if there is a good pair that is ,lets say,in form of s_k and s_k+4 and k is not 4?

who_

That is the basic concept of the proof. I am still working out a few details, but I am pretty sure that this trail of thought will give a correct proof.

[EDIT] Now I am becoming more doubtful it will work. Sigh - I am sorry for all this confusion.

I am not sure what you are asking. S_k is a set.

limitkiller

I am not sure what you are asking. S_k is a set.[/QUOTE]

isnt s_k={k,2k,3k,4k,5k}?

who_

Yes, it is.

limitkiller

so what I am saying is you already assumed that overlappings can only occur in s_k and s_2k.
It seems to be true ,but I cant understand why...

who_

Right. Let's say that S_k and S_m have overlapping pairs, and assume that k < m. Then if the pair is (a,b), with a < b, a = pk and b = qk for some 1 <= p < q <= 5.

Since (a,b) is also from S_m, we must have b >= 2m, so that m <= b/2 <= 5k/2, and must we have that there exists 1 <= p', q' <= 5 such that p'm = pk and q'm = qk.

If p = 2 and q = 4, then we can choose p' = 1, q' = 2, and m = 2k. Otherwise, p and q must be relatively prime, so that m cannot be greater than k (can you see why?).

Thus, an overlap only occurs only with sets S_k and S_{2k}, and that overlap must be (2k,4k).

who_

Another observation I am trying to use is the following: if a pair (a,b) with a > b is good and a =/= 2b, then (a,a-b) is also good. Might help : /