[math-fun] Largest sum-free subset of {0,1,2,...,2n}
Prove that if S is a subset of {0,1,2,...,2n} containing more than n elements, then there must exist x,y,z in S such that x+y=z. (This smells like an Olympiad problem to me. In fact, I may well have solved this very problem forty years ago, but I don't see how to solve it now. Some sort of pigeonhole argument, sure, but how to set it up?) The bound is tight; both 1,3,5,...,2n-1 and n+1,...,2n are sum-free. Jim Propp
To clarify, you permit x=y or y=z, correct? Otherwise, for n=1, {0,1} and {1,2} are counterexamples. On Thu, Oct 12, 2017 at 7:26 PM, James Propp <jamespropp@gmail.com> wrote:
Prove that if S is a subset of {0,1,2,...,2n} containing more than n elements, then there must exist x,y,z in S such that x+y=z.
(This smells like an Olympiad problem to me. In fact, I may well have solved this very problem forty years ago, but I don't see how to solve it now. Some sort of pigeonhole argument, sure, but how to set it up?)
The bound is tight; both 1,3,5,...,2n-1 and n+1,...,2n are sum-free.
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Yes, I permit any two (or even all three) of x,y,z to be equal when I consider solutions to x+y=z. (So in a way including 0 in {0,1,2,...,2n} was silly of me.) Jim On Thursday, October 12, 2017, Allan Wechsler <acwacw@gmail.com> wrote:
To clarify, you permit x=y or y=z, correct? Otherwise, for n=1, {0,1} and {1,2} are counterexamples.
On Thu, Oct 12, 2017 at 7:26 PM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
Prove that if S is a subset of {0,1,2,...,2n} containing more than n elements, then there must exist x,y,z in S such that x+y=z.
(This smells like an Olympiad problem to me. In fact, I may well have solved this very problem forty years ago, but I don't see how to solve it now. Some sort of pigeonhole argument, sure, but how to set it up?)
The bound is tight; both 1,3,5,...,2n-1 and n+1,...,2n are sum-free.
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Prove that if S is a subset of {0,1,2,...,2n} containing more than n elements, then there must exist x,y,z in S such that x+y=z.
(This smells like an Olympiad problem to me. In fact, I may well have solved this very problem forty years ago, but I don't see how to solve it now. Some sort of pigeonhole argument, sure, but how to set it up?)
... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... This is problem 36 in Bela Bollobas's "The Art of Mathematics: Coffee Time in Memphis", which gives the following solution: ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... (First, note that we may assume 0 isn't in S since 0+0=0; Bollobas's statement of the problem assumes that explicitly.) Let a = min(S) and let T = {s-a : s in S, s /= a}. S has more than n elements, T has n elements, so between them they have more than 2n, and all these elements have 1 <= x <= 2n. So they must have an element in common. That is, we have s = s'-a; which is to say, s' = s+a. Done. Note that this actually proves somewhat more than was asked for. -- g
Thanks! (I should have remembered the source of the problem; not only did I read the book, but I wrote a review of it...) Jim On Thu, Oct 12, 2017 at 10:17 PM, Gareth McCaughan < gareth.mccaughan@pobox.com> wrote:
Prove that if S is a subset of {0,1,2,...,2n} containing more than n
elements, then there must exist x,y,z in S such that x+y=z.
(This smells like an Olympiad problem to me. In fact, I may well have solved this very problem forty years ago, but I don't see how to solve it now. Some sort of pigeonhole argument, sure, but how to set it up?)
... spoiler space ...
... spoiler space ...
... spoiler space ...
... spoiler space ...
... spoiler space ...
... spoiler space ...
... spoiler space ...
This is problem 36 in Bela Bollobas's "The Art of Mathematics: Coffee Time in Memphis", which gives the following solution:
... spoiler space ...
... spoiler space ...
... spoiler space ...
... spoiler space ...
... spoiler space ...
... spoiler space ...
... spoiler space ...
(First, note that we may assume 0 isn't in S since 0+0=0; Bollobas's statement of the problem assumes that explicitly.)
Let a = min(S) and let T = {s-a : s in S, s /= a}. S has more than n elements, T has n elements, so between them they have more than 2n, and all these elements have 1 <= x <= 2n. So they must have an element in common. That is, we have s = s'-a; which is to say, s' = s+a. Done.
Note that this actually proves somewhat more than was asked for.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Allan Wechsler -
Gareth McCaughan -
James Propp