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
    Since you aren't looking for a solution, I didn't solve it, but maybe an alteration argument would work. e.g., Pick $A_0$ by sampling element with probability $1/2$, so any bad triple goes into $A_0$ with probability $1/8$. At this point, try to argue that you can remove not too much of $A_0$ to get a sum free $A$, and do the same thing to the complement.2012-03-22
  • 2
    Another idea would be to look at the problem modulo $p$ where $p$ is a prime such that the numbers in $S$ are distinct mod $p$. Then $S$ can be considered as a subset of $(\mathbb Z/p\mathbb Z)^\times$. Choose $x \in \{1,\ldots,p-1\}$ uniformly at random and consider the set $xS \subseteq (\mathbb Z/p\mathbb Z)^\times$.2012-03-22
  • 2
    @marlu's idea works out. If you like, you can see it applied to prove that there's a single sum-free set $A$ with $|A|\ge n/3$ [here at Proposition 1, p. 32](http://math.stanford.edu/~ksound/Notes.pdf) (spoiler alert! :-). Then you need a judicious choice for the second subset.2012-03-22
  • 0
    @marlu Great tips! Thanks.. I solved it, I had to look at the spoiler :-( though. I still have a very minor problem in my proof, it proves that the sum of set sizes is $\geq$ not $> 2n / 3$. I think I would have to analyse the boundaries ($1/6$, $1/3$, $2/3$ and $5/6$) but I guess that essentially solves it. If any of you moves the comment to an answer, I'll accept it right away.2012-03-22
  • 0
    @joriki Same comment as above (only one @ is allowed).2012-03-22
  • 0
    I think it is not always possible to get $|A|+|B| > 2n/3$. Consider $S = \{1,2,3\}$.2012-03-22
  • 0
    @marlu $A = \{1, 3\}$ and $B = \{2\}$?2012-03-22
  • 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$.