4
$\begingroup$

This is actually not a homework problem, but I'd like it to be treated as if it were one. I am not looking for a solution, I would just like to have some hints on how to start.

I am trying to solve the third problem here. I managed to solve the first two, so I think I understand what a probabilistic argument is. Let me rewrite the question here. I would like to prove that for any given set $S \subset \mathbb{Z}\setminus\{0\}$ of size $n$, there must be a pair of disjoint subsets $A$ and $B$, such that $|A| + |B| > 2 n / 3$ and both $A$ and $B$ are sum-free (each does not contain three elements where one is the sum of the other two).

I am really stuck in figuring out the "right" random variable to look at. Any (non-spoiler) hints are very much appreciated!

  • 0
    Sorry, you are right. Maybe, for showing ">" it is possible to consider $S \cup \{0\}$ instead of $S$ and choose subsets that don't include 0.2012-03-22

1 Answers 1

1

I repost my comment as an answer since the idea worked out.

Let $p$ be a large prime such that the elements of $S$ are distinct modulo $p$. Then $S$ can be considered as a subset of $\mathbb Z/p\mathbb Z$. Choose $x \in \{1,\ldots,p-1\}$ uniformly at random and consider the set $xS \subseteq \mathbb Z/p\mathbb Z$. Then find disjoint sum-free subsets $A$ and $B$ of $\mathbb Z/p\mathbb Z$ and show that for some choice of $x$ at least $2n/3$ elements of $xS$ fall into $A$ or $B$.