Consider the set $ S=\{1,\dots,65\}$ and the odd number subset of it $ A=\{1,3,\dots,63,65\}$. $ |A|=33$ and $ 4\sqrt {65}\approx 32.25$ From this post we know the maximum length of the sum free sequence. Hence $ (k+1)^2 \leq 16(2k+1)$ according to the problem statement. Clearly this does not hold as LHS is a higher degree polynomial.

Fang-jh wrote: Prove that for arbitary integer $ n > 16$, there exists the set $ S$ that contains $ n$ positive integers and has the following property:if the subset $ A$ of $ S$ satisfies for arbitary $ a,a'\in A, a\neq a', a + a'\notin S$ holds, then $ |A|\leq4\sqrt n.$ we want say that?: (it's what i understand) $ \forall n > 16,\exists set\ S: \ |S| = n:$ $ (\forall A\subset S): \ |A| > 4\sqrt {n}\Rightarrow \exists (a,a')\in A: \ a\neq a'\ and \ a + a'\in S$ but $ \exists N\in%Error. "mathh" is a bad command. {N}:$ such that $ N > 16$ and $ N\ge 2(4\sqrt {N} + 1)$ for $ S$ such that $ |S| = N$ let $ S=\{M,M-1,M-2,.......,M-N+1\}$ we take $ A = \{M,M - 1,M - 2,...,M - ([4\sqrt {N}])\}$ here we have $ |A| > 4\sqrt {N}$ and $ \forall a,a'\in A$ such that $ a\neq a'$ : $ a + a'\ge 2M - 2[4\sqrt {N}] + 1\ge (M + 1) + (N - 2[4\sqrt {N}])\ge M + 1$ (because $ M\ge N$) then $ a + a'\not\in S$ $ A\subset S$ cheks the property but $ |A| > 4\sqrt {N}$ so the probleme is fault or i don't understand

aviateurpilot wrote: $ A = \{M,M - 1,M - 2,...,M - ([4\sqrt {N}])\}$ here we have $ |A| > 4\sqrt {N}$ Hello,But I think $ A$ should be the subset of $ S$.

zhaobin wrote: aviateurpilot wrote: $ A = \{M,M - 1,M - 2,...,M - ([4\sqrt {N}])\}$ here we have $ |A| > 4\sqrt {N}$ Hello,But I think $ A$ should be the subset of $ S$. $ S=\{M,M-1,..,M-N+1\}$

aviateurpilot wrote: zhaobin wrote: aviateurpilot wrote: $ A = \{M,M - 1,M - 2,...,M - ([4\sqrt {N}])\}$ here we have $ |A| > 4\sqrt {N}$ Hello,But I think $ A$ should be the subset of $ S$. $ S = \{M,M - 1,..,M - N + 1\}$ But in the problem,we should prove there exist a set $ S$,not for all $ S$. You just prove that for some $ S$ the conclusion doesn't hold.

zhaobin wrote: aviateurpilot wrote: zhaobin wrote: aviateurpilot wrote: $ A = \{M,M - 1,M - 2,...,M - ([4\sqrt {N}])\}$ here we have $ |A| > 4\sqrt {N}$ Hello,But I think $ A$ should be the subset of $ S$. $ S = \{M,M - 1,..,M - N + 1\}$ zhaobin wrote: But in the problem,we should prove there exist a set $ S$,not for all $ S$. You just prove that for some $ S$ the conclusion doesn't hold. Zhaobin is right. The most difficult part in this problem is to construct a set $ S$ which satisfies the property mentioned in the question. So please stop searching for a certain $ S$ to negate the problem .

zhaobin wrote: aviateurpilot wrote: zhaobin wrote: aviateurpilot wrote: $ A = \{M,M - 1,M - 2,...,M - ([4\sqrt {N}])\}$ here we have $ |A| > 4\sqrt {N}$ Hello,But I think $ A$ should be the subset of $ S$. $ S = \{M,M - 1,..,M - N + 1\}$ zhaobin wrote: But in the problem,we should prove there exist a set $ S$,not for all $ S$. You just prove that for some $ S$ the conclusion doesn't hold. sorry

I have an idea of such a set S, i have not computed quantitatively Let K is set of integers such that its representation in base 4 contains only the digit 1,2. Arrange this set in increasing order and for each n, take the first n elements of K

Anybody solutions? I think this is a very famous problem but I don;t know solution.

Can someone please post the solution

I thought this is too hard for a 2008TSTP2. Here's a hint: We construct a graph with vtx set $S$ $a$~$b$ iff $a+b$ belongs to $S$ We need to ensure the independent set if the graph isn't too large Recall what we have learnt in Graph theory, how to ensure there isn't a large indep. set with little edges? That's Turan's theorem! Thus the graph roughly look like a combination of cliques and a indep set(the largest few numbers) The next question is how to add numbers to the vertices. Actually, between different cliques, the numbers on their vertices should have different order, To illustrate, we can let their power of 2 is different and their odd part is the same. Hope you can work out for the details! (It's not hard but it would be helpful if you work out yourselves)

Is there a way to do it without graph theory ?

Actually we don't need to use graph theory, turan's theorem is just a motivation lead to the construction!