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.$
Problem
Source: Chinese TST
Tags: combinatorics proposed, combinatorics
05.04.2008 14:04
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.
05.04.2008 15:24
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
05.04.2008 17:15
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$.
05.04.2008 19:07
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\}$
06.04.2008 04:41
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.
06.04.2008 06:30
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 .
06.04.2008 16:06
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
02.05.2008 23:28
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
16.02.2015 13:24
Anybody solutions? I think this is a very famous problem but I don;t know solution.
23.04.2021 20:21
Can someone please post the solution
04.08.2022 06:16
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)
04.08.2022 06:27
Is there a way to do it without graph theory ?
04.08.2022 06:30
Actually we don't need to use graph theory, turan's theorem is just a motivation lead to the construction!