/prog/ challenge

A set of integers is sum-free when addition always gets you out of the set (i.e. x + y = z has no solutions -- in other words S + S and S are disjoint). Formally, let S be a subset of N. S is sum-free if for all a,b in S, a+b is not in S.

Now, let S be any set of nonzero integers. Find a subset of size > |S|/3.

You may use your favorite lisp language.

I've got a really nice solution for this one.

>>17
Correct me if I'm wrong, but:

forall positive k < |S|, there exists k = |S'| where S' is a subset of S, and S and S' are sum-free.

The reasoning is removing any element from S is sum-free-preserving since it only removes opportunities to find sums on S.

So, if you have an existence proof of positive k>|S|/3, there's one for forall positive k' =< k by way of repeated application of the above.