Let $n$ be a positive integer. Determine the size of the largest subset of $\{ -n, -n+1, \dots, n-1, n\}$ which does not contain three elements $a$, $b$, $c$ (not necessarily distinct) satisfying $a+b+c=0$.
Problem
Source: 2009 USAMO problem 2
Tags: pigeonhole principle, induction, ceiling function, symmetry, inequalities, combinatorics, Hi
azsxder
30.04.2009 22:32
I am so afraid that this solution has a hole, because I solved it in the last 45 min and wrote it up hurriedly. So yeah, this is so I know ahead of time if I'm out of the running for MOP already.
The answer is n for all even n and n+1 for all odd n.
To prove that a subset of the claimed maximal size exists, we take the set of all integers from -n to n inclusive that are odd. Then the sum of any three numbers is odd, which is not zero, since zero is even.
Now, we will prove that if n is even, then there can not be a set of n+1 elements that satisfies the given condition. Let S be a subset of the integers from -n to n.
Since 0+0+0=0, 0 cannot be in the set. Now, we split the set into positive and negative numbers. Let P be the set of positive integers in S and N be the absolute values of the negative numbers in S.
Without loss of generality, let P have at least as many elements as N.
Now, we want to show that give that P has at least n/2+1 elements, N cannot have at least n/2 elements.
Case 1: If x is the largest number in either set, P or N, x is in N.
If p_1, p_2,...,p_k are the elements in P, we see that x-p_1, x-p_2,...,x-p_k cannot be in P. So there are k integers from 0 to n that are not in P. Which means there are at most n-k+1 elements that are in P. Since k>=n/2+1, we know that there is at most n/2 elements in P.
But since there is at least n/2+1 elements in P, we have a contradiction.
Case 2: If x is the largest number in either set, P or N, x is in P and not N.
If n_1, n_2,...,n_i are the elements in N, we see that x-n_1, x-n_2,...,x-n_i cannot be in N. So there are i integers from 1 to n-1 that are not in P (n is not in N). Which means there are at most n-i-1 elements that are in N. Since i>=i/2, we know that there is at most n/2-1 elements in P.
But since there is at least n/2 elements in N, we have a contradiction.
If N is odd, we note that the maximal subset of -n+1 to n-1 with the given condition has n-1 elements (as n is even). Then, we can only add two more elements to that subset (-n and n) so that there are n+1 elements.
Since we have proven that there is at most n elements if n is even and n+1 elements if n is odd and the maximal size is acheiveable, we are done with the proof.
Zhero
30.04.2009 22:36
That's essentially how I did it (except I chose the set {-(n + 1)/2, ..., -n, (n + 1)/2, ..., n)} instead for the odds.) I think I'll lose credit because I just said "by Pigeonhole, there must be some a and b such that a + b = n + 1, without justification (due to time pressure.) Sigh.
aznlord1337
30.04.2009 22:50
Let $ A_n$ = $ ( - n, - n + 1... - 1,n)$ excluding $ 0$. Claim: for $ A_n$ when $ n$ is even, the largest good subset has size $ n$. When n is odd the largest good subset of $ A_n$ has $ n + 1$ elements. Furthermore, any good subset of $ A_n$ (n is odd) with $ n + 1$ elements is one of two configurations: i) contains only odd elements from $ A_n$ or ii) contains the elements $ \pm (n,n - 1...[n/2] + 1)$. Proceed with induction: the claim is clear for $ n = 1$ and $ n = 2$. Now suppose the claim is proven up to $ n - 1$. Suppose $ n$ is odd. To find all possible configurations for a good subset of size $ n + 1$ from $ A_n$, note that from the subset $ A_{n - 2}$ we have at most $ n - 1$ elements, so we have at lest two elements from $ B = ( - n, - n + 1, n - 1, n)$ Suppose we have two elements from $ B$ and $ n - 1$ elements from $ A_{n - 2}$. Based on the elements taken from $ A_{n - 2}$ (note n-2 is odd), we cannot have $ \pm (n - 1)$. So we take $ - n,n$ from $ B$. This implies that we take just all odd elements from $ A_{n - 2}$. So for this case, our claim holds (the good $ n + 1$ size subset from $ A_n$ consists of just the odd elements from $ A_n$. Suppose we take four elements from $ B$. Partition the elements of $ A_{n - 2}$ into disjoint pairs $ \pm (x,n - 1 - x)$ from which we make only take one element each and each has two distinct elements (so we rule out $ (n - 1)/2,(n - 1)/2$. Then we have $ n - 3$ such pairs and we need to take $ n - 3$ elements. However, notice that we cannot take $ \pm 1$ or two numbers would sum to $ \pm n$. then we must take $ \pm (n - 2)$. But then we cannot take $ \pm 2$ or two numbers would sum to $ \pm n$ so we have to take $ \pm (n - 3)$... continuing this way constructs the goodsubset of size $ n + 1$ that fits the description of our claim. Now suppose we take three elements from $ B$. WLOG take $ - n + 1, n - 1, n$. But this leads to a contradiction by pigeonhole because we can only have $ n - 1$ elements from $ A_n$. So suppose we take $ - n, n - 1, n$. We need $ n - 2$ elements from $ - n + 2...n - 2$. Note we cannot have $ 1$ or $ (n - 1)/2$. Partition those disjoint subsets again into those that either sum to $ n$ or $ - (n - 1)$. We now have $ n - 3$ pairs of elements from which we can only take one each. But we needed $ n - 2$. Contradiction. Now that we have established the only possible configurations of good subsets of size $ n + 1$ from $ A_n$ when $ n$ is odd, it is easy to see that adding no other element is possible (if we take all odd configuration we cant take any remaining evens, if we take the $ \geq |[n]/2 + 1|$ configuration we cant take any numbers lower). So $ n + 1$ is the maximum size for odd $ n$. Now consider $ A_n$ when $ n$ is even. If we take neither $ - n,n$ we cannot achieve $ n + 1$ by taking elements from just $ A_{n - 1}$. If we take both of $ - n,n$, a partition of $ A_{n - 1}$ (done just like in earlier cases) shows $ n + 1$ is impossible. If we take just $ n$, we need $ n$ elements from $ A_{n - 1}$ This restricts it to only two possible configurations, both of which have two numbers that add to $ - n$. So $ n + 1$ is unachievable for even $ n$. To see that $ n$ is achievable, just take all the negative numbers. This completes the induction. Unfortunately I didn't realize you could take all odds for a good $ n+1$ element subset for odd $ n$ until a few minutes left...
timwu
30.04.2009 22:53
Outline (very inelegant)
Construction: take all the odd numbers.
Induction for evens (odd follows trivially). Assume the claim for $ n = 2(k - 1)$. Suppose for $ 2k$ we can have $ 2k + 1$ elements. Then we need to add at least 3 "new" elements from the set $ \{ - 2k, - 2k + 1, 2k - 1, 2k\}$.
Case 1: we add $ - 2k, - 2k + 1, 2k - 1$ but not $ 2k$ (or $ 2k$ but not $ 2k - 1$, but this is equivalent). Then we need at least $ 2k - 2$ "old" elements. Notice for $ x + y = 2k - 1$ we can have at most one of $ x, y$, so from the set $ 1, 2, .., 2k - 2$ we have at most $ k - 1$ elements. Similarly, from the set $ - 1, - 2, ..., - (2k - 2)$ we have at most $ k - 1$ elements. Thus we must have equality which means we must pick one from each pair that sums to $ 2k - 1$. On the other hand, notice for any $ x + y = 2k$ we can have at most one of $ x, y$. Now, since $ 2k - 1$ is in the set, $ 1$ is not. Then $ 2k - 2$ must be in the set, else we have fewer than $ k - 1$ elements from $ 1, 2, .., 2k - 2$. Continuing this argument, we see that $ 1, 2, ..., k$ are not in the set, leaving $ k - 2$ elements from $ 1, 2, .., 2k - 2$. Contradiction.
Case 2 and 3: similar arguments.
5 pages.
CatalystOfNostalgia
30.04.2009 23:20
The answer is $ 2\lceil\dfrac{n}{2}\rceil$. That is, when $ n$ is even, $ n$, and when $ n$ is odd, $ n+1$. This is achievable by taking all of the odd elements in the set, then $ a+b+c$ is odd, which is obviously not zero.
We first prove that the size of the set is at most $ n+1$ regardless of parity. Let the desired set be $ S$, and observe that 0 is not in $ S$, or else we have 0+0+0=0. Now, let $ k$ be in $ S$ such that $ |k|$ is minimal, and without loss of generality let $ k>0$ (by symmetry, we can just flip all the signs if $ k<0$, preserving the required property of $ S$). Assume for sake of contradiction that $ |S|>n+1$. Note that if $ k>\dfrac{n}{2}$, we will have at most $ n+1$ elements, contradiction. Thus, $ k\le\dfrac{n}{2}$. Consider the following $ n-2k$ pairs of integers: $ \{-n+j,n-j-k\}$ for $ 0\le j\le n-2k-1$. Notice that the terms in each pair sum to $ -k$, so at most one term in each pair can be in $ S$ (or else we can sum these two with $ k$ to get 0). Furthermore, it's easy to check that these pairs are all disjoint.
Now, the only terms that can be in $ S$ but are not counted in these pairs are $ -2k,-2k+1,-2k+2,\ldots,-k$, and $ n-k+1,n-k+2,\ldots,n$, by the minimality of $ k$. But note that $ -2k$ cannot be in $ S$, since we have $ k$ in $ S$ and this will give us $ -2k+k+k=0$. After eliminating $ -2k$, we have at most $ 2k$ terms here, then at most $ n-2k$ in the pairs (one from each), plus $ k$. This gives us a total of at most $ n+1$ terms. This immediately proves the odd case.
Now, we prove that in fact we can only have $ n$ terms when $ n$ is even. Assume we can have $ n+1$. We can again get that $ k\le\dfrac{n}{2}$, because the only terms we can have when $ k>\dfrac{n}{2}$ are $ \pm\dfrac{n+2}{2}$ up to $ \pm{n}$. Now, note that to have $ n+1$ terms, we need to have exactly one term from each pair in the $ S$, and all of $ -2k+1,-2k+2,\ldots,-k$ and $ n-k+1,n-k+2,\ldots,n$ in $ S$ as well. We now consider three cases.
Case 1: $ 2k\le n\le 5k-3$. We claim that we will be able to find a term $ a$ among $ -2k+1,-2k+2,\ldots,-k$ and a term $ b$ among $ n-k+1,n-k+2,\ldots,n$ such that $ 2a+b=0$. Consider a term among $ -2k+1,-2k+2,\ldots,-k$, of the form $ a=-2k+i$ where $ 1\le i\le k$. Then, we can find a corresponding $ b$ if and only if $ n-k+1\le 4k-2i\le n$. Rearranging this, we want $ 4k-2i\le n\le 5k-2i$. But we see as we run this over $ 1\le i\le k$, every $ n$ within $ 2k\le n\le5k-3$ will be in one of these intervals. since the size of the interval is $ k-1\ge1$ when $ k>1$, and we 'shift' it over by 2 each time we increase $ i$ by 1 (I know this sounds like handwaving, but just think about it). The only other case is when $ k=1$, in which we have $ n=2$, and the only interval we have to consider is $ 2\le n\le2$, in which $ n=2$ clearly falls. Therefore, if we take all of these elements in $ S$, we will be able to find $ a+b+c=0$, contradiction.
Case 2: $ n=5k-2$. Note that since $ n$ is even, we need $ k$ to be even. Now, note that since $ k\ge2$, we have $ n-k+\dfrac{k+2}{2}$ and $ -2k+\dfrac{k+2}{2}$ in $ S$ (recall that $ n-k+i$ and $ -2k+i$ are in $ s$ as long as $ 1\le i\le k$). Now, the sum of these two terms is $ n-3k+k+2=n-2k+2$. Thus, we cannot have $ -n+2k-2$ in $ S$. But since $ 0\le 2k-2\le n-2k-1=3k-3$, this means that $ n-3k+2=2k$ is in $ S$. But we have $ -k$ in $ S$, so now $ (-k)+(-k)+2k=0$, contradiction.
Case 3: $ n\ge5k-1$. Consider the pairs of terms $ \{-2k+i,n-k+i\}$ for $ 1\le i\le k$, which we know we have to have in $ S$. Their sum is $ n-3k+2i$. Thus, we cannot have $ -n+3k-2i$ in $ S$. But note that $ 0\le 3k-2i\le n-2k-1$, which follows from the assumption that $ n\ge5k-1$ and $ 1\le i\le k$. This means that $ n-4k+2i$ is in $ S$ for $ 1\le i\le k$. That is, $ n-2k,n-2k-2,\ldots,n-4k+2$ are all in $ S$. Note that $ n-2k>2k$. We will now show that $ 2k\in S$, in which we would be done as in Case 2. Note that since $ n$ is odd, this is a decreasing arithmetic sequence of even positive integers, with common difference 2. We claim that we will eventually hit $ 2k$.
To prove this, we will prove by induction that if $ n-2i,n-2i-2,\ldots,n-2i-2k+2$ are all in $ S$ such that $ n-2i-2k+2>2k$, then we can get that $ n-2i-2k\in S$. That is, we can keep getting the next term in the arithmetic sequence in $ S$ until we reach $ 2k$. We have $ n-2i\in S$ and additionally $ -k\in S$. Thus, we cannot have $ -n+2i+k\in S$. But we can get that $ 0\le 2i+k\le n-2k-1$, so $ n-2i-2k\in S$. This, finally, completes the proof.
azjps
30.04.2009 23:51
Let $ Z_n$ be the set of subsets satisfying the $ a + b + c \neq 0$ condition for $ n$, and let $ s_n$ be the largest size of a set in $ Z_n$. Let $ n = 2k$ if $ n$ is even, and $ n = 2k - 1$ if $ n$ is odd. We note that $ s_n \ge 2k$ due to the following constuction:
\[ \{ - 2k + 1, - 2k + 3, \ldots, 2k - 3, 2k - 1\}
\]
or all of the odd numbers in the set. Then the sum of any three will be odd and thus nonzero.
Lemma 1: $ s_{n + 1} \le s_{n} + 2$. If $ M_{n + 1} \in Z_{n + 1}, |M_{n + 1}| = s_{n + 1}$, then we note that $ M_{n + 1} \setminus \{ - 2n + 1, 2n - 1\} \in Z_n$, so $ |M_{n + 1}| - 2 \le s_n$. $ \square$
Lemma 2: $ s_{2k} = s_{2k - 1}$. Suppose, for sake of contradiction, that $ M_{2k} \in Z_{n + 1}$ and $ M_{2k} > s_{2k - 1}$. Remove $ 2k, - 2k$ from $ M_{2k}$, and partition the rest of the elements into two sets $ P_{2k - 1}, Q_{2k - 1}$, where $ P$ and $ Q$ contain all of the positive and negative elements of $ M_{2k}$, respectively. (obviously $ 0 \not \in M_{2k}$, because $ 0 + 0 + 0 = 0$). WLOG, suppose $ |P_{2k - 1}| \ge |Q_{2k - 1}|$. Then $ |P_{2k - 1}| + |Q_{2k - 1}| \ge s_{2k - 1} - 1 \ge 2k - 1$. We now show the following two sub-results:
Sub-lemma (A): if $ |P_{2k - 1}| \ge k$, $ - 2k \not \in M_{2k}$ [and similar for $ Q$]; and
Sub-lemma (B): we cannot have both $ |P_{2k - 1}| + |Q_{2k - 1}| \ge 2k$ and $ |Q_{2k - 1}| < k$ simultaneously hold.
This is sufficient, because the only two elements that may be in $ M_{2k}$ that are not in $ P_{2k - 1}, Q_{2k - 1}$ are $ 2k$ and $ - 2k$; for $ M_{2k} > s_{2k - 1}$, we must either have $ |P_{2k - 1}| + |Q_{2k - 1}| = s_{2k - 1} - 1 \ge 2k - 1$ and both $ 2k, - 2k \in M_{2k}$ [but by pigeonhole $ |P_{2k - 1}| \ge k$, see sub-lemma (A)], or $ |P_{2k - 1}| + |Q_{2k - 1}| = s_{2k - 1} \ge 2k$, and $ 2k \in M_{2k}$, in which case by (A) we must have $ |Q_{2k - 1}| < k$, violating (B).
(A): Partition $ \{1,2,\ldots,2k - 1\}$ into the $ k$ sets $ \{k\}, \{1,2k - 1\}, \{2, 2k - 2\}, \cdots, \{k - 1, k + 1\}$. Because $ (k + \delta) + (k - \delta) - 2k = 0$, then if any of those sets are within $ P_{2k - 1}$, $ - 2k \not \in M_{2k}$. But by Pigeonhole at most $ k - 1$ elements may be in $ P_{2k - 1}$, contradiction.
(B): We prove this statement with another induction. We see that the statement easily holds true for $ k = 1$ or $ 2$, so suppose it is true for $ k - 1$, but [for sake of contradiction] false for $ k$. Let $ P_{2k - 3} = P_{2k - 1} \setminus \{2k - 2, 2k - 1\}$, and similarly for $ Q_{2k - 3}$. Again WLOG $ |P_{2k - 3}| \ge |Q_{2k - 3}|$. Then we have $ |P_{2k - 1}| + |Q_{2k - 1}| \le |P_{2k - 3}| + |Q_{2k - 3}| + 4$.
*If $ |P_{2k - 3}| + |Q_{2k - 3}| \ge 2k - 2$, then by inductive hypothesis, we must have $ |P_{2k - 3}| = |Q_{2k - 3}| = k - 1$. But (A) implies that we cannot add $ 2k - 2$ or $ - 2k + 2$. So to satisfy $ |P_{2k - 1}| = |Q_{2k - 1}| \ge 2k$ we must have $ 2k - 1, - 2k + 1$ added, but then $ |P_{2k - 1}| = |Q_{2k - 1}| = k$ contradiction.
*If $ |P_{2k - 3}| + |Q_{2k - 3}| = 2k - 3$, then at least three of $ \{2k - 2, 2k - 1, - 2k + 2, - 2k + 1\}$ added. But $ |P_{2k - 3}| \ge k - 1$, and by (A) we have that $ - 2k + 2$ cannot be added. If $ |P_{2k - 3}| \ge k$, then another grouping similar to (A) shows that $ - 2k + 1$ canno be added, contradiction. So $ |P_{2k - 3}| = k - 1$, $ |Q_{2k - 3}| = k - 2$, and adding the three remaining elements gives $ |P_{2k - 1}| = |Q_{2k - 1}| = k$ contradiction.
*If $ |P_{2k - 3}| + |Q_{2k - 3}| = 2k - 4$, then all four of $ \{2k - 2, 2k - 1, - 2k + 2, - 2k + 1\}$ must be added, and furthermore $ |P_{2k - 3}| > |Q_{2k - 3}|$. Then $ |P_{2k - 3}| \ge k - 1$, and by previous paragraph we cannot add $ - 2k + 2$. $ \square$
So we have $ \begin{cases} s_1 & = 2 \\
s_{2k} & = s_{2k - 1} \\
s_{2k - 1} & \le s_{2k - 2} + 2 \\
\end{cases}$ and by induction, that $ s_n \le \boxed{2\left\lceil \frac n2 \right \rceil} = 2k$, which we showed is achievable above.
jvenezuela716
01.05.2009 00:19
=====
Let $ S_n=\{-n,\dots ,n\}$. Call a subset $ X$ of $ S_n$ pretty if we can't find three (not necessarily distinct) elements in $ S_n$ that sum to zero. The size of the largest pretty subset of $ S_n$ is $ 2\left\lceil \frac{n}{2} \right\rceil$. This is attainable by taking all the odd numbers in $ S_n$, since the sum of any three odd numbers is necessarily odd and so necessarily non-zero. It suffices to show that we can't do any better than this for all $ n$, which we do by induction.
For $ n=1$, we can't do better than $ 2$, or else we would have to choose $ S_1$ itself for $ X$, which includes $ 0$, which obviously doesn't work since $ 0+0+0=0$. For $ n=2$, we can't do better than $ 2$, which we can show by just writing out all of the subsets of greater size (there aren't a lot) and showing they aren't pretty.
Now suppose the claim is true for all $ n\leq 2k$. For $ n=2k+1$, we can only choose $ 2k$ elements from $ S_{2k}$ by assumption and then choose at most $ 2$ of $ \{-(2k+1),2k+1\}$, for a maximum of $ 2k+2$, so we can't do better. For $ n=2k+2$, suppose we could find a subset $ X$ of $ S_{2k+2}$ with cardinality greater than $ 2k+2$. We consider $ S_{2k+2}$ and note that we can again choose at most $ 2k$ elements from $ S_{2k}$, so that if we were to do better than $ 2k+2$, we must choose at least three from $ \{-(2k+2),-(2k+1),2k+1,2k+2\}$. This leads to five cases.
CASE ONE: $ -(2k+2), -(2k+1), 2k+1$ are in $ X$, $ 2k+2$ is not.
Here we must choose $ 2k$ elements from $ S_{2k}$. Note that if any of $ 0,1,k+1$ are in $ X$, we'd have $ 0+0+0=0$, $ -(2k+2)+1+2k+1=0$, or $ (k+1)+(k+1)-(2k+2)=0$, so suppose none of these three are chosen from $ S_{2k}$. Partition the remaining elements of $ S_{2k}$ as follows:
$ \{\{-2k,-1\},\{-(2k-1),-2\},\dots ,\{-(k+1),-k\},\{2,2k\},\{3,2k-1\},\dots ,\{k,k+2\}\}$
There are $ 2k-1$ subsets in the partition but we choose $ 2k$ elements so by Pigeonhole one of these subsets is contained in $ X$. Note that all of the subsets in the partition have a sum of either $ -(2k+1)$ or $ 2k+2$, which we can pair with $ 2k+1$ and $ -(2k+2)$, respectively, so $ X$ isn't pretty, contradiction.
The other four cases are very similar, just with slightly different partitions.
=====
sdkudrgn88
01.05.2009 00:30
You guys are too pro for my taste... What I did is provide an algorithm (three, actually) and proved that with this algorithm, you could not add any more numbers on for any $ n$. While I did get the right answer of 2*ceil(n/2), the way I got it was very crude.
CatalystOfNostalgia
01.05.2009 00:31
sdkudrgn88 wrote: You guys are too pro for my taste... What I did is provide an algorithm (three, actually) and proved that with this algorithm, you could not add any more numbers on for any $ n$. While I did get the right answer of 2*ceil(n/2), the way I got it was very crude. Uh what if you use a different algorithm
jvenezuela716
01.05.2009 00:31
sdkudrgn88 wrote: What I did is provide an algorithm (three, actually) and proved that with this algorithm, you could not add any more numbers on for any $ n$. Can you elucidate please? I don't see how this works without assuming that you have a specific subset to work with.
Yongyi781
01.05.2009 00:32
Do you think greedy algorithm works? Basically you take $ \{ -n, \dots, n \}$ and find all the offending triples. Then use greedy algorithm to remove the least amount of numbers as possible while getting rid of all the offending triples.
CatalystOfNostalgia
01.05.2009 00:33
"Greedy algorithm" isn't a solution at all. Why is the greedy algorithm optimal in this case?
Yongyi781
01.05.2009 00:34
The "why" is the second sentence I wrote above. (Of course I can't just write "greedy algorithm qed"). I described the algorithm in detail.
azjps
01.05.2009 00:38
I suppose it would be possible, but how did you characterize all of the triples (and pairs)? Especially since it doesn't have to be symmetric, etc.
Yongyi781
01.05.2009 00:43
Well actually, in the case $ n = 2k$, given the set $ \{ - 2k,\dots,k\} \backslash \{0\}$ (since 0 is automatically rejected because 0 + 0 + 0 = 0), start with $ - 2k$, then we have $ (2k - 1,1),(2k - 2,2),\dots,(k,k)$. Then next, we start with $ - 2k + 1$, with one fewer possibilities than the $ - 2k$ case, etc. Then mirror it for $ 2k, 2k - 1,\dots$. Basically, I got it down to (something like, I can't remember) $ \text{something}(k - 1)^2$ offending triples, apply it once, we have $ \text{something}(k - 2)^2$ offending triples, do it until we have $ \text{something}(k - k)^2 = 0$ offending triples left, and we have used the algorithm $ k$ times to remove $ k$ numbers. Then I proceeded to start the case $ 2k + 1$, which is basically the same thing but I ran out of time before I could finish.
Ubemaya
01.05.2009 01:01
It looks like you are repeatedly choosing a variable to eliminate the maximum number triples possible, for that turn. Did you prove that you cannot have an algorithm that, say, eliminates 1 triple, then 1 triple, then all of them. In other words, you don't eliminate the maximum amount at first, but it enables you to eliminate a lot more later.
Yongyi781
01.05.2009 01:08
Think about it this way: You have a fixed number of offending triples for each $ n$ before you do anything, and for any integer $ a$ in $ S$, you have a some number of triples which contain $ a$. Any methods of efficiently removing these triples just lead to permutations of the greedy algorithm. I just chose the greedy algorithm because that was the simplest way to explain it. * By "permutations" I meant permutations by number of triples removed in each step, not by the number actually removed.
azjps
01.05.2009 01:12
Yongyi781 wrote: Any methods of efficiently removing these triples just lead to permutations of the greedy algorithm. Wait, why?
Yongyi781
01.05.2009 01:13
I cannot remember how I explained it; the best way to see why is to try it for something like $ n=6$ and list them out on paper.
shankarmath
24.02.2019 01:06
I thought that this was a really nice problem, but it took me quite a long time (like 2.5-3 hours in total)
Note that $0$ cannot be in the subset for obvious reasons ($0+0+0=0$).
We claim that the answer is $n$ for even $n$ and $n+1$ for odd $n$. It suffices to show that the result holds for even $n$.
We take cases:
Case 1: Our subset has some number between $1$ and $\frac{n}{2}$ and some number between $-1$ and $-\frac{n}{2}$.
Let the positive number be $k$.
Then, because there are at least $\frac{n}{2}$ pairs of negative numbers that differ by $k$, and we can only take one number per pair, we can have at most $\frac{n}{2}$ negative numbers. Similarly, we can have at most $\frac{n}{2}$ positive numbers, so the result holds in this case. $\square$
Case 2: Our subset has some number between $1$ and $\frac{n}{2}$ and no numbers between $-1$ and $-\frac{n}{2}$. This is identical to the case where our subset has some number between $-1$ and $-\frac{n}{2}$ and no number between $1$ and $\frac{n}{2}$.
Suppose that the largest negative number in the subset has magnitude $m$. Then, there are exactly $n-m$ disjoint pairs of numbers that differ by $m$ in the positive side; therefore, there can be at most $n-m$ positive numbers. On the other hand, there can be at most $n-m+1$ negative numbers (all numbers from $-n$ to $m$); therefore, the maximum number of numbers in this case is $2n-2m+1$. Because $m>\frac{n}{2}$, the conclusion follows in this case. $\square$.
Case 3: Our subset has no numbers between $1$ and $\frac{n}{2}$ and no numbers between $-1$ and $-\frac{n}{2}$.
This case is trivial; there can be at most $\frac{n}{2}$ negative numbers and $\frac{n}{2}$ positive numbers, so the conclusion follows. $\square$
To show that these maxima can occur, for $n$ is odd, we may take ${-n,-n+2,...-1,1,...n}$ and for $n$ is even we may take ${1,2,...n}$. Thus, we are done. $\blacksquare$
sa2001
20.02.2020 16:00
Oh wow this is actually pretty easy. We claim the answer is $n$ for even $n$ and $n+1$ for odd $n$, and any subset achieving the maximum for odd $n$ must contain $n$ and $-n$. To see this can be achieved, choose the subset containing all the odd elements. We now prove that the bounds are indeed the maximums. Call the answer for $n$ $a_n$. Note that $0$ can't be chosen. We'll prove our claim by induction on $n$. Base case $n = 1$ is trival to see. Assuming our hypothesis holds for $l, l \ge 1$, we'll prove it for $n = l+1$. Case: $n$ is odd: Note $a_n \le a_{n-1} + 2$, so we're done by the induction hypothesis. In particular, $n$ and $-n$ must both be part of the maximal subset. Case: $n = 2k$ is even: If both $n$ and $-n$ are members of the subset, then the number of positive integers $< n$ which are in the subset is $\le k-1$, and the number of negative integers $> -n$ which are in the subset is $\le k - 1$ (as $k/2, -k/2$ can't be chosen and of any two numbers summing to $n$ or $-n$ at most one can be chosen), so $a_n \le 2k$. If neither of $n, -n$ is chosen then $a_n \le a_{n-1} = n$. Now suppose exactly one of $n, -n$ is chosen. WLOG $n$ is chosen. Note that then $a_n \le a_{n-1} + 1$. Suppose $a_n = a_{n-1}+1$. Then note that deleting $n$ from the subset gives a maximal subset for $n-1$, so both $n-1$ and $-(n-1)$ are in the subset. Note that the number of negative integers $> -n$ which are chosen is $\le k-1$ (as before), and the number of positive integers $< n-1$ which are chosen is $\le k-1$ (as at most one of two numbers summing to $n-1$ can be chosen). So $a_n \le (k-1)+(k-1)+2 = 2k$, and we're done.
pad
21.03.2020 03:19
Let $f(n)$ be the answer. We claim \[ f(n) = \begin{cases} n\qquad \qquad \text{if } n \text{ even} \\ n+1\qquad \ \text{if } n \text{ odd}. \end{cases}\]This is achieveable by taking all the odds in the set $\{-n,\ldots,n\}$. We will prove $f(n)=f(n-2)+2$, by induction on $n$, the base cases trivial. Assume $n$ is even; the analysis for odd $n$ is the same, barring base cases. Call $S_n$ the maximal subset for $\{-n,\ldots,n\}$. Assume for the sake of contradiction $|S_n| > n$. If $S_n\cap \{-n,-n+1, n-1, n\} \le 2$, then we can only get at most $(n-2)+2=n$ elements in $S_n$ by induction. Hence we need at least 3 of $\{-n,-n+1,n-1,n\}$. Let $C = S_n\cap \{-n,-n+1,n-1,n\} = \{-n,n\}$. If $C \supseteq \{-n,n\}$, then there can be at most one elements from each of the following $n-2$ pairs: $(-n+2,-2),(-n+3,-3),\ldots, (-n/2, -n/2)$ and $(n-2,2),(n-3,3),\ldots,(n/2,n/2)$. So $|S_n| \le (n-2)+2=n$, contradiction. A similar pairing argument shows we cannot have $C \supseteq \{-n+1,n-1\}$ or $C \supseteq \{-n+1,n\}$ or $C \supseteq \{-n,n+1\}$. This completes the induction, and proves that $|S_n| \le n$.
Archimedes15
06.11.2020 20:53
Before we start just note that we'll always be ignoring the number $0$ because if you repeat $0$ three times it sums to $0$. Claim: If $n$ is even, the answer is $n$ and if $n$ is odd, $n+1$ is the answer. Proof: Note that the even and odd cases are equivalent except for the base cases being different. Note that the base cases for both case are correct so we can just proceed by only dealing with the even case. Now, let's split this into a few different cases. Let $M$ denote the maximally sized subset: Case 1: Assume that $M$ contains at most $1$ of each of the pairs $(-n, n)$ and $(-n+1, n-1)$. Note that in this case we can just proceed by induction to prove the desired. Case 2: Assume that $M$ contains both $(-n,n)$. In this case, note that you can make $n-2$ pairs that sum to $n$ and you can only take at most $1$ from each pair. So, you have a maximum of $n$ in this case as well. You can create a parallel argument for $(-n+1, n-1)$. So, in each case, the maximum is $n$ for evens. You can adjust the same argument for odds to prove the claim for odds as well. So, we're done. Note that we have a correct construction when all of the odd numbers in the set are taken which leads to the numbers desired. This construction obviously works because the sum of an odd number of odd numbers must be odd and $0$ is an even number.
jeteagle
26.11.2020 22:28
We will prove the answer is $n+1$ for odd $n$ and $n$ for even $n.$ Construction: Pick the numbers in the range $[-n, -\left \lceil{\frac{n}{2}}\right \rceil-1] $ and $[\left \lfloor{\frac{n}{2}}\right \rfloor+1, n]$ as the numbers in this subset. For every $x$ in this subset, we have $|x| > \frac{n}{2}$ so the sum of any $2$ would have absolute value of more than $n$ or less than or equal to $\frac{n}{2},$ which means any $3$ can't sum together to equal $0.$ We will now prove by strong induction, that this is the maximum. For the base cases of n = 1 and n = 2, we see that we cannot have $0$ in the subset, or else $0+0 = 0$, which means we can only have $-1$ and $1$, which gives a total of $n+1 = 2$ elements. For $n = 2$, if we have $2$, we cannot have $-1$ and vice versa. This is the same with $-2$ and $1$. This means we again can only have $n = 2$ elements. Let $S$ be the subset of $\{-n, -n+1, -n+2, \cdots, n-2, n-1, n\}$ that has the maximum number of elements and satisfies the problem statement. For the inductive step, we first prove for all odd numbers $n$. Let's assume for all positive integers less than $n$ that it is true, which means for $n-1$, the maximum number of elements in the subset of $\{-n+1, -n+2, \cdots, n-2, n-1\}$ that are also in $S$ is $n-1$. If there are more than $n+1$ elements, then there is at least $n$ elements that are in $\{-n+1, -n+2, \cdots, n-2, n-1\}$, a contradiction. Now, we need to prove for all even numbers $n$. We will prove by contradction that there exists $S$ that has more than $n$ elements, so assume for all positive integers less than $n$ that it is true. This means, for $n-1$, the maximum number of elements in the subset of $\{-n+1, -n+2, \cdots, n-2, n-1\}$ is $n+1.$ If $S$ does not include $n$ or $-n$, then this simplifies to the previous case of $n-1$, which we already proved is $n+1$. This means there has to be at least one of $n$ or $-n$ included in the subset. WLOG let $-n$ be included in $S$. Consider the ordered pairs $$(0, n), (1, n-1), \cdots, (\frac{n}{2}, \frac{n}{2}).$$We cannot have both terms of an ordered pair to be included in $S$, as we then have the sum of them and $-n$ to be $0$. This also means we cannot have $\frac{n}{2}$ because $\frac{n}{2}+\frac{n}{2}-n = 0.$ Therefore, there is a maximum of $\frac{n}{2}$ numbers we can include among these numbers, which happen to be the nonnegative integers. Now, suppose the greatest integer in $S$ is less than $n-1.$ This means we can split $S$ into two groups. One group contains the numbers in the subset $\{-n+2, -n+3, \cdots, n-3, n-2\}$, and the other group contains the numbers $-n$ and $-n+1.$ For the first group, we can only have a maximum of $n-2$ elements, and if we include both $-n$ and $-n+1$, then we get $n$ elements. Therefore, to have more than $n$ elements, we need to include at least one of $n-1$ and $n$. Let's say $n$ is not in $S$, so we must have $n-1$. We can again make ordered pairs $$(0, -n+1), (-1, -n+2), (-2, -n+3)\cdots (-\frac{n}{2}+1, -\frac{n}{2}),$$and we see that if we include both numbers of a pair in $S$, then the sum of them and $n-1$ will be $0$, so we can only have $1$. There are total of $\frac{n}{2}$ of these pairs, so we get a total of $\frac{n}{2}$ of these numbers. We can now take a look at the positive numbers. Because we assumed $-n$ is in $S$, we created $\frac{n}{2}+1$ pairs also, and said that we can have at most $\frac{n}{2}$ nonnegative numbers. But if we look at $(0, n)$, we can't have $0$ or else $0+0 = 0$, and we said that $n$ was not in $S$, which means we have to also subtract this pair and we end up with $\frac{n}{2}-1$ pairs, which gives us a maximum of $\frac{n}{2}-1$ numbers. Finally, if we include $-n$, we get a total of $n$ elements in $S$. Finally, we look at the case if $n$ is in $S$. By symmetry there must also only be a maximum $\frac{n}{2}$ negative numbers, so the total number of elements is at most $\frac{n}{2}+\frac{n}{2} = n$. Therefore, we have finished the even case, and the induction is complete.
IAmTheHazard
07.07.2021 22:33
The answer is $2\lceil n/2\rceil$, achievable by taking every odd. Clearly $0$ can't be in the subset. We establish this by induction on $n \geq 2$, with the base case of $n=2$ being true by manual checking. Of course, $n=1$ is trivial. Let $A$ be the subset of $\{-n,\ldots,n\}$ with maximal size. If $n$ is odd, the bound is obvious because we can only add at most two elements from the maximal subset of $\{-n+1,\ldots,n-1\}$, in particular $n$ and $-n$. Now suppose $n$ is even, and consider which elements of $\{-n,n\}$ are in $A$. If none are in $A$, then we immediately get the bound of $2\lceil (n-1)/2\rceil=2\lceil n/2\rceil$, as desired. Suppose one element is in $A$, WLOG let it be $n$. Then if $|A|>2\lceil n/2 \rceil$, we must have that $A \setminus \{n\}$ is a maximal subset of $\{-n+1,\ldots,n-1\}$. For this to happen, we would need both $n-1$ and $-n+1$ to be in $A \setminus \{n\}$, otherwise $|A\setminus \{n\}|<2\lceil (n-1)/2\rceil$. Now partition $\{-n+1,\ldots,-1\}$ into the pairs $$(-n+1,-1),(-n+2,-2),\ldots,(-\tfrac{n}{2},-\tfrac{n}{2}),$$of which there are clearly $\tfrac{n}{2}$. It is clear that among each pair, at most one element can be in $A$. Since we can't chose exactly one element of the last pair, it follows that there are at most $\tfrac{n}{2}-1$ negative numbers in $A$. We can similarly split $\{1,2,\ldots,n-2\}$ into the $\tfrac{n}{2}-1$ pairs $(1,n-2),(2,n-3),\ldots,(\tfrac{n}{2}-1,\tfrac{n}{2})$, where at most one element of each pair may be in $A$. Adding back $n-1$ and $n$, it follows that there are at most $$\tfrac{n}{2}-1+\tfrac{n}{2}-1+1+1=n=2\lceil n/2\rceil$$elements in $A$, which is the desired bound. Finally suppose two elements are in $A$, i.e. both $n$ and $-n$. Then we can split $\{-n+1,\ldots,-1,1,\ldots,n-1\}$ into the pairs $$(-n+1,-1),(-n+2,-2),\ldots,(-\tfrac{n}{2},-\tfrac{n}{2}),(1,n-1),(2,n-2),\ldots,(\tfrac{n}{2},\tfrac{n}{2}),$$where we have $n$ pairs total and among each pair at most one element can be in $A$. However, since neither $\tfrac{n}{2}$ or $-\tfrac{n}{2}$ may be in $A$, this leaves a total of $n-2$ elements of $A$ in $\{-n+1,\ldots,-1,1,\ldots,n-1\}$, which gives the desired bound of $n=2\lceil n/2\rceil$. These cases complete the induction, so we're done. $\blacksquare$
bever209
15.07.2021 19:58
Let $S=\{-n,-n+1,...,-1,1,...,n\}$. We leave out $0$ because it obviously cannot be in the subset. The answer is $n$ if $n$ is even and $n+1$ if $n$ is odd. For a construction for both, just take all odd values in $S$, which works because of parity.
Now let the maximum size subset (of $S$) that we choose be $A$. Let the element with the minimal absolute value in $A$ be $x$. Now if $x \geq \lfloor \frac{n}{2} \rfloor +1$, the claim has already been proven, so we assume $x \leq \lfloor \frac{n}{2} \rfloor$.
Now we will effectively pair some of the numbers up to find an upper bound. We will pair numbers so that their sum is $-x$, and thus we can only take at maximum one number from each pair, but there will also be other numbers remaining. First, we can take $x,-x$, and then we can pair $-x-1$ and $1$ together, $-x-2$ and $2$ together, and so on. We then get $x,-x$ aren't paired and can be in $A$, and the pairs that are formed are $(-x-1,1),(-x-2,2)...(-n,n-x)$. But there are still the numbers $n-x+1,n-x+2...n$ which aren't paired, and they needn't be as they don't have a counterpart to sum to $-x$, so we don't pair them like for $x$ and $-x$. Thus, we have \[x,-x,(-x-1,1),(-x-2,2)...,(-n,n-x),n-x+1,...,n\]where if two numbers are paired, then we can select at most one of them.
But note that $(-2x,x)$ is a pair, and since we have already selected $x$, we must select $-2x$, but $-2x+x+x=0$ so we cannot select any number form this pair. Thus, we can leave it out. In addition, there exist pairs that have a value that has absolute value less than $x$, and so we must select the other value in that pair. Making all these adjustments, we now get \[\{x,-x,-x-1,-x-2...,-2x+1,(-2x-1,x+1),...,(-n,n-x),n-x+1,n-x+2,...,n\}\]Let this set be B.
Now note that there are $n+1$ values (either single elements or pairs) in the list above, so we have proved the answer for odd $n$ (in fact, set $x=1$ and there exists a way to choose all the odd numbers in the pairs which will work). Now we show that if we choose one element from each pair and keep the rest of the single elements, there exists no way to solve the problem for even $n$ (essentially $n+1$ for even $n$ doesn't work).
Assume $n$ is even. We now show that if there exists a solution with $n+1$ elements, then $x$ must be $1$. We prove it by contradiction, so assume $x \geq 2$. Now if $2x$ is not in a pair, we are done, so assume it is in a pair. Then it must be in a pair with $-3x$, and we must take this number in the pair. In addition, because of out assumption on $x$, we have that $-x-1 \leq -2x+1$, and because $(-x-1)+(-2x+1)=-3x$, if $3x$ is not in a pair, we are done. Otherwise, it must be in a pair with $-4x$, and we have to take this number. Now the key thing to realize is that since we take $-3x$, we cannot take $4x$, which means we take $-5x$, and so on so we take all $-(2k+1)x$ for all $k\geq 1$ if it exists in B (either in a pair or by itself). Similarly, we get that we take all $-(2k+2)x$ for $k \geq 1$. In other words, we take any multiple $-kx$ for $k \geq 3$.
Now the key thing is to realize that in $n-x+1,n-x+2,...,n$ there exists at least one multiple of $x$. Let the maximal one be $ax$. If $a=2$, we are done as $(-x)+(-x)+2x=0$, if $a=3$ we are done as $(-x-1)+(-2x+1)+3x=0$ (just repeating from the previous paragraph) but from the previous paragraph, we know that we have taken $-kx$ for $k\geq 3$, so we know that we have $-(a-1)x$ and because $-(a-1)x+(-x)+ax=0$, we cannot have $x \geq 2$ so we have proven the claim.
Finally, we have that the set $B$ we are dealing with is actually \[\{1,-1,(-3,2),(-4,3)...(-n,-n+1),n \}\]Now we show no even $n$ works. First it is obvious that we need to take $1$ and $-1$. This means $n=2$ doesn't work. Now since $2+(-1)+(-1)=0$ we need to take $-3$, so $n=4$ doesn't work.
We now show that we must take all values in the form $-(2k+1)$ for $k \geq 1$. We proceed with induction, with the base case $-3$ having been proven. Now if we want to show that $-(2k+1)$ has to be chosen and we know $-(2k-1)$ is chosen, note that $-(2k+1)$ is paired with $2k$, and $2k+(-1)+(-(2k-1))=0$, so we must take $-(2k+1)$, and so this completes the induction. From here, it is trivial to show even $n \geq 6$ doesn't work: $-1+(1-n)+n=0$, so for even $n$, the answer must be less than $n+1$, so we are done.
AwesomeYRY
05.01.2022 22:38
Old Solution that I copy and pasted. My proof writing used to be so terrible We claim that for positive integers $n$, if $n$ is even, the max size is $n$; and if $n$ is odd, the max size is $n+1$. We proceed with induction. Additionally, let $S_n$ be the set $\{-n,-n+1, \ldots,n-1,n\}$ The base cases are trivial for n=1,2 with sets $\{-1,1\}$ and $\{-2,-1,1,2\}$. Note if 0 is included, then we have at most $n+1$ elements in the subset. We can thus assume that 0 is never included. Now for the inductive step. It is clear that for n=2k, any subset of $S_n$ will be the sum of a subset of $S_{n-1}$ and $\{-n,n\}$. By the inductive hypothesis this has size at most n+2. Thus, we have an additional condition that the for even n in order to have size $n+2$, $\{n,-n\}$ must be included For $n=2k+1$, we have a combination of a subset of $S_{2k}$ and $\{-(2k+1),2k+1\}$. Assume for the sake of contradiction that there is a subset with size greater than $n+1 = 2k+2$. By the inductive hypothesis there are at most $2k+2$ elements in $S_{2k}$. We now do casework on the number of elements from $\{-(2k+1),2k+1\}$. Case 1: 2 from $\{-(2k+1),2k+1\}$ In this case, we can pair up $(1,2k),(2,2k-1),\ldots,(k,k+1)$ and $(-1,-2k),(-2,-2k+1),\ldots,(-k,-k-1)$. We can have at most one from each pair, for a total of $2k+2=n+1$ elements. Case 2: 1 from $\{-(2k+1),2k+1\}$ WLOG we include 2k+1. Now, in order to have a size of more than 2k+2, we must have 2k+2 from $S_{2k}$. Since this is the equality case, $\{-2k,2k\}$ are also included in the subset. We can now pair up $(-1,-2k),(-2,-2k+1),\ldots,(-k,-k-1)$ and $(1,2k-1),(2,2k-2),\ldots (k-1,k+1)$. Thus, we have at most $k+ (k-1)+1+2 = 2k+2= n+1$ numbers in the subset. Our induction is now complete and even n have at most n+2, odd n have at most n+1. We have equality cases when we take element in $S_n$ if $|element| \geq n/2$.
vsamc
25.02.2023 03:47
If $n$ is even, the answer is $n$; if $n$ is odd, the answer is $n+1$.
Construction: For $n$ even, just take $\{1, 2, \cdots, n\}$, which clearly works. For $n$ odd, take $\{-n, -n+2, \cdots, -3, -1, 1, 3, \cdots, n-2, n\}$ -- this works since all elements are odd, so the sum of any three of them is odd as well (and therefore is nonzero).
Bound: Let $f(n)$ be the answer for $n$. We will prove that $f(n)\leq n$ if $n$ is even and $f(n) \leq n+1$ if $n$ is odd, using strong induction. Our base cases are $n=1$ and $n=2$, the former of which for clearly the largest subset of $\{-1, 0, 1\}$ containing no three elements summing to zero is $\{-1, 1\}$, which has size $2 = 1+1$, and the latter of which for also somewhat clearly the largest subset of $\{-2, -1, 0, 1, 2\}$ containing no three elements has size $2$, since in the pairs $(1, -2)$, $(-1, 2)$, at most one element from each is in such a subset (and of course zero cannot be in the subset).
Now, let $n\geq 3$ be an integer, and suppose the result is true for all $1\leq k\leq n-1$.
If $n$ is odd, then the largest subset of $\{-(n-1), -(n-2), \cdots, (n-1), n\}$ with no three elements summing to zero is at most $f(n-1) \leq n-1$ by the inductive hypothesis, so $f(n)\leq f(n-1) + 2 \leq (n-1) + 2 = n+1$, since there can only be two added extra elements -- $n$ and $-n$.
If $n$ is even, let $L$ be one of subsets with maximal size satisfying the conditions. If neither $-n$ or $n$ is in $L$, then $|L| \leq f(n-1) \leq n$ by the inductive hypothesis.
If both $n$ and $-n$ is in $L$, then in the pairs $(1, n-1), (2, n-2), \cdots, (n/2-1, n/2+1)$ and $(-1, -n+1), (-2, -n+2), \cdots, (-n/2+1, -n/2-1)$, at most one element in each pair is in $L$, else, we have $k + (n-k) + (-n) = 0$, which is not allowed, or $k + (-n-k) + n = 0$, which is also not allowed. Also, neither $n/2$ or $-n/2$ is in the set, since $n/2 + n/2 - n = -n/2 - n/2 + n = 0$. Thus, in this case, $|L| \leq 2 + \left(\frac{n}{2} - 1\right) + \left(\frac{n}{2} - 1\right) = n$ as well.
Else, exactly one of the elements in $\{-n, n\}$ is in $L$. WLOG suppose $n\in L$ and $-n\notin L$. Then, if the element with the largest magnitude in $L\setminus \{n\}$ has magnitude at most $n-2$, then by the inductive hypothesis, $f(n)\leq 1 + f(n-2) = 1 + (n-2) < n$. Else, either $-n+1$ is in $L$ and/or $n-1$ is in $L$. If $-n+1$ is in $L$, then in the pairs $(1, n-2), (2, n-3), \cdots, \left(n/2-1, n/2\right)$, and $(-1, -n+1), (-2, -n+2), \cdots, (-n/2+1, -n/2-1)$, at most one element in each pair is in $L$ from similar arguments to above -- $k + (n-1-k) + (-n+1) = 0$ and $-k + (-n+k) + n = 0$. Also $-n/2\notin L$, since $-n/2 - n/2 + n = 0$. Thus, $|L| \leq 2 + \left(\frac{n}{2} - 1\right) + \left(\frac{n}{2} - 1\right) = n$, where the $2$ is because of the fact that $n-1$ and $n$ do not belong to any of the pairs. Else, $-n+1$ is not in $L$, so $n-1$ must be in $L$, and every element in $L\setminus \{n-1, n\}$ has magnitude at most $n-2$, so by the inductive hypothess, $f(n)\leq 2 + f(n-2) = 2 + (n-2) = n$. Thus, in all cases, $f(n)\leq n$, so our inductive step is complete and we are done. $\blacksquare$
peppapig_
18.06.2023 05:32
There's also a smarter way to do this; you can skip out on the odd case apparently and just skip straight to the even $n$'s? I claim that the answer is $n+1$ for all odd $n$ and $n$ for even $n$. The desired lower bound can be achieved by choosing all odd integers in the range $[-n,n]$ to be in the subset. This must satisfy problem conditions (meaning that there do not exist not necessarily distinct $a$, $b$, $c$ in the set such that $a+b+c=0$) since it is impossible for three odd numbers to sum to $0$. For terminology, we will use $Q$ to denote the chosen subset that is a subset of the integers ranging from $n$ to $-n$, inclusive, which must satisfy problem conditions. A few things to note before we begin; 1. $0$ can never be in $Q$. This is because by setting $a=b=c=0$, we get $a+b+c=0+0+0=0$, a contradiction. 2. The set $P=Q-(Q\cap\{-n,-n+1,n-1,n\})$ is a subset of the integers in the range $[-n+2,n-2]$, and since $Q$ satisfies problem conditions, all subsets of $Q$ must satisfy problem conditions (FTSOC, assume not, then the triple in the subset that sum to $0$ also appears in $Q$ and sums to $0$ there, a contradiction), meaning that $P$ must satisfy problem conditions. We will now prove our original statement with induction, and we will take this in cases. From here on out, $P$ is a subset of $Q$ and a subset of the set of integers ranging from $-n+2$ to $n-2$, inclusive. (a) $n$ is odd. We assume that for all odd integers $k<n$, where $n$ is odd, the maximum value of the size of any subset of the integers in the range $-k$ to $k$ such that no $a$, $b$, $c$, exist in this set such that $a+b+c=0$ is $k+1$. We will now induct upwards to prove that for $n$, the maximum value of the size of any subset of the integers in the range $-n$ to $n$ such that no $a$, $b$, $c$, exist in this set such that $a+b+c=0$ is $n+1$. By the inductive assumption, we have that $|P|\leq n-1$, where $P\subseteq Q$ satisfies problem conditions and is a subset of the integers in the range $[-n+2,n-2]$. Additionally, $Q$ is a subset of the integers in $[-n,n]$ satisfying problem conditions. We wish to prove that $|Q|\leq n+1$. First I claim that if $|P|=n-1$, then $\{-n+1,n-1\}$ is not a subset of $Q$. FTSOC, suppose that $\{-n+1,n-1\}\subseteq Q$. Then this implies that there do not exist $a$, $b$ in $P$ (not necessarily distinct) such that $a+b=-n+1$ or $n-1$. However, note that in the range $[-n+2,n-2]$, there are exactly $n-3$ unordered pairs of distinct numbers $(a,b)$, such that $a+b$ is $-n+1$ or $n-1$. They are \[(1, n-2), (2, n-3), \dots, \left(\frac{n-3}{2},\frac{n+1}{2}\right), (-1,-n+2), (-2, -n+3), \dots, \left(\frac{-n+3}{2},\frac{-n-1}{2}\right), \]and the only other numbers in the set $\{-n+2,\dots,n-2\}$ not in these pairs are $0$, $\frac{-n+1}{2}$, and $\frac{n-1}{2}$, none of which can be in $P$ due to the conditions. Therefore for the numbers in $P$, we can choose at most one number from each pair for a total of at most $n-3$, implying that $|P|\leq n-3$, a contradiction to our earlier assumption that $|P|=n-1$. Therefore, if $|P|=n-1$, then $\{-n+1,n-1\}$ is not a subset of $Q$. I now claim that if $|P|=n-1$, then $\{n,-n,-n+1\}$ is also not a subset of $Q$. We use similar logic. This time, note that there are $n-3$ total unordered pairs of distinct numbers $(a,b)$ summing to $\pm n$. They are \[(2,n-2), (3,n-3), \dots, \left(\frac{n-1}{2},\frac{n+1}{2}\right), (-2,-n+2), (-3,-n+3), \dots, \left(\frac{-n+1}{2},\frac{-n-1}{2}\right),\]with the only numbers in $\{-n+2,\dots,n-2\}$ not in these pairs being $1$, $-1$, and $0$. As shown before, $0$ cannot appear in $P$. Additionally, since we assumed that $-n$ and $n-1$ are in $Q$, we cannot have $1$ in $P\subseteq Q$, otherwise we'd have \[(-n)+1+(n-1)=0,\]a contradiction to our assumption that $Q$ satisfies problem conditions. Therefore $1$ cannot appear in $P\subseteq Q$. Tying it all together, since there do not exist $a$, $b$ such that $a+b=\pm n$, we note that out of each of the $n-3$ pairs, we can choose at most one to be in $P$. Adding on the possibility of having $\{-1\}$ in $P$, we get that $|P|\leq (n-3)+1=n-2$ elements, a contradiction to our assumption that $|P|=n-1$. Therefore $\{n,-n,-n+1\}$ cannot be a subset of $Q$. Similarly, we can prove that if $|P|=n-1$, then $\{n,-n,n-1\}$ cannot be a subset of $Q$. Combining the claims above gives that if $|P|=n-1$, then for $R=Q\cap\{-n,-n+1,n-1,n\}$, we have that $|R|\leq 2$. Therefore, \[|Q|=|P\cup R|\leq |P|+|R| \leq (n-1)+2=n+1,\]as desired. Now I claim that for $|P|=n-2$, $\{-n,-n+1,n-1,n\}$ cannot be a subset of $Q$. As shown before, $n-1$ and $-n+1$ have $n-1$ total unordered pairs that are such that $a+b$ is not $-n+1$ or $n-1$. Additionally, we must also leave out $0$, $\frac{n-1}{2}$, and $\frac{-1+n}{2}$, which would result in $0$ sums. This leaves us with $n-2$ "valid" pairs to consider, each of which we can choose at most one number from. However, in order to have exactly $n-2$ numbers in $P$, we must choose one from each pair. However, neither of $1$ or $-1$ can be in $P$. Therefore, $n-2$ and $-n+2$ must both be in $P$, as we must choose at least one number from each pair. Additionally, since \[(-2)+(-n+2)+n=0,\]and \[2+(n-2)+(-n)=0,\]we also have that $2$ and $-2$ cannot be in $P$, implying that $-n+3$ and $n-3$ are in $P$. Continuing similarly, we keep going until we are left with the numbers \[-n+2, -n+3, \dots, \frac{-n-1}{2},\]and \[n-2, n-3, \dots, \frac{n+1}{2},\]in $P$, which has a total of $n-3$ numbers, a contradiction, since we assumed that $|P|=n-2$. Therefore, $\{-n,-n+1,n-1,n\}$ cannot be a subset of $Q$. This gives that $|R|\leq 3$, meaning that \[|Q|=|P\cup R|\leq |P|+|R| \leq (n-2)+3=n+1,\]as desired. Finally, if $|P|<n-2$, we have that \[|Q|=|P\cup R|\leq |P|+|R| \leq (n-3)+4=n+1,\]proving the claim for our odd case. (b) $n$ is even. For induction, we assume that for all even integers $k<n$, where $n$ is even, the maximum value of the size of any subset of the integers in the range $-k$ to $k$ such that no $a$, $b$, $c$, exist in this set such that $a+b+c=0$ is $k$. We will now induct upwards to prove that for $n$, the maximum value of the size of any subset of the integers in the range $-n$ to $n$ such that no $a$, $b$, $c$, exist in this set such that $a+b+c=0$ is $n$. From the inductive assumption, we have that the maximum value of $|P|$ over all $P$ is $n-2$. Similar to the odd case, we can prove that for $|P|=n-2$, the following claims hold 1. The set $\{-n,n\}$ is not a subset of $Q$. Assume FTSOC that it is a subset of $Q$. Since there are $n-2$ pairs and $-\frac{n}{2}$, $\frac{n}{2}$, and $0$ cannot be in $Q$, in order to achieve $n-2$ numbers in $P$, we must have $1$, $-1$ and one number chosen from each pair. However, there is an even number of pairs, therefore two of the chosen numbers from the pairs are bound to be $\pm 1$ apart or either one of $-2$ and $2$ will be chosen, which would yield \[(-2)+1+1=0,\]or \[2+(-1)+(-1)=0,\]both of which are contradictions. 2. The set $\{-n,-n+1,n-1\}$ is not a subset of $Q$, and similarly, neither is $\{-n+1,n-1,n\}$. We will only prove the first one, as the second set can be proved similarly. FTSOC, assume that it is a subset of $Q$. Note that since \[(-n)+1+(n-1)=0,\], $1$ cannot appear in $Q$. Since we cannot have $1$, since we have exactly $n-2$ pairs that sum to $n-2$ we need one number from each pair to reach our desired $n-2$. This implies that if $1$ is not in $Q$, then $n-2$ must be. Using this , we get that since \[2+(n-2)+(-n)=0,\]$2$ also cannot appear in $Q$, meaning that $n-3$ must appear in $Q$. Continuing this chain, we get that \[\{n-2, n-3, \dots, \frac{n}{2}\}\subseteq Q,\]which is a contradiction, since \[\frac{n}{2}+\frac{n}{2}+(-n)=0.\]Similarly as before, using these two claims, we have that $|R|\leq 2$, which yields that $|Q|\leq n$, as desired. Now if $|P|=n-3$, we can similarly prove as before that $\{-n,-n+1,n-1,n\}$ cannot be a subset of $Q$ by using the fact that neither $1$ or $-1$ can appear in $P$, a contradiction. Therefore, we get that $|R|\leq 3$, giving that $|Q|\leq n$, as desired. Finally, if $|P|\leq n-4$, we have that \[|Q|=|P\cup R|\leq |P|+|R| \leq (n-4)+4=n,\]as desired. Therefore, we have proved our inductive step for both cases. The base cases can be checked at $n=1$ and $n=2$ through trial and error easily, finishing the problem.
signifance
19.12.2023 05:45
wait im lazy to check but how come all the sols are longer than this trivial by induction from n to n+2, inductive hypothesis all odds: if u could add 3 numbers from inductive step (say n even,odd follows) -n-1,n+1,n+2 then contradiction with 1 AND 3, if u exclude 1 and 3 then u must add -n-1, but u must exclude -1 and -3 then so still so increase.
Pyramix
13.02.2024 13:42
\item[Problem 3] (USAMO 2009/2) We claim that answer is $n$ for $n$ being even and $n+1$ for $n$ being odd. For $n=1$, the set is $\{-1,1\}$ For $n=2$, the set is again $\{-1,1\}$. The base cases are therefore true. Let $f(n)$ denote the answer. We perform induction. It is known that $f(n)\leq f(n-1)+2$. We prove that if $n$ is even, $f(n)=f(n-1)$ and if $n$ is odd, $f(n)=f(n-1)+2$. Suppose $n$ is even $f(n)>f(n-1)$. Let $n=2k$. Case 1. $n,-n$ belong to the subset. Let $S$ be the subset. In this case, $n,-n\in S$. Then, $0\notin S$. Moreover, $k,-k\notin S$ and from the pairs $(1,2k-1),(2,2k-2),\ldots,(k-1,k+1)$ and $(-1,1-2k),(-2,2-2k),\dots,(1-k,1+k)$ only one element is in $S$ at most. So, excluding $n,-n$, set $S$ has at most $2(k-1)$ elements. So, the subset has at most $2k$ elements, which is not more than our bound. Case 2. $-n$ belong to the subset but $n$ doesn't. Note that we are adding exactly one extra element. It means that we can have at most $n+1$ elements in our set, including $-n$. Moreover, consider the subset of $S$ containing elements $x$ with $|x|<n-1$. There are at most $n-2$ such elements by induction hypothesis. So, to get to $n+1$, we must add the elements $-n+1,n-1,-n$ to the set $S$. Moreover, $k\notin S$. Consider the elements: \[(1,n-2),(2,n-3),\ldots,(k-1,k);(-1,2-n),(-2,3-n),\ldots,(-k,1-k)\]We can choose at most $2k-2$ elements from these pairs as we cannot take a whole pair, as sum is either $n-1$ or $1-n$. Out of these elements, we will need exactly $2k-2$ elements, as they consist of all terms $x$ with $|x|\leq n-1$. The other 3 elements are just $-n,1-n,n-1$ to make up for the total $2k+1$ elements. So, we need to take EXACTLY one element from each pair. Suppose \[n-2\in S\Longrightarrow2\notin S\Longrightarrow n-3\in S\Longrightarrow3\notin S\Longrightarrow n-4\in S\Longrightarrow\cdots k\in S\]This means that if $n-2\in S$ then for each $k\leq x\leq n-2$, we have $x\in S$, and if $1\in S$, then for each $1\leq x\leq k-1$, we have $x\in S$. However, we know $k\notin S$ as $2k+(-n)=0$ and $1\notin S$ as $-n+1+(n-1)=0$. We have arrived at the required contradiction. Case 3. $n$ belongs to subset and $-n$ doesn't. This case is similar to case 2. So, we have shown that $f(n)=f(n-1)$, as claimed. We now provide a construction. - Choose all the odd numbers in the set! For $n$ being odd, we choose $n+1$ terms and for $n$ being even we choose $n$ terms. This works because the sum of three odd numbers cannot be even! (0 is even)
ihatemath123
08.08.2024 07:30
The answer is $n+1$ for odds and $n$ for evens, obtained from selecting all the odd integers. To prove a bound of $n+1$: let $b$ be the largest negative integer in the subset (if all integers are positive, we are done already). WLOG, assume that $|b|$ is no more than the smallest positive integer in the subset. Let $P$ be the number of positive integers in the subset. For each positive integer $a$, the nonpositive integer $-a-b$ must not be in the set. Thus, there are at most $n+1-P$ nonpositive integers, so there are at most $n+1$ integers in total.
I didn't realize this at first and was about to post this solution claiming the answer was $n+1$ for all integers
cannot be included in our subset. So, the smallest positive integer in our set and the largest negative integer in our set are equal in magnitude. This implies that $-1$ cannot be one of the $P$ integers ruled out from our subset, so it must be in the set, and so $1$ must also be in the set. Now, we cannot include any consecutive integers from the sequence \[-1, 2,-3,4,-5, \dots, n\]or \[1, -2,3,-4,5, \dots, -n,\]so we cannot select $n+1$ integers, contradiction.
EthanWYX2009
01.09.2024 10:40
Here is the generalized version: (原创组合-43) Given integer $p,q\ge 2.$ Determine the size of the largest subset of $\{ -p, -p+1, \dots, q-1, q\}$ which does not contain three distinct elements $a$, $b$, $c$ satisfying $a+b+c=0$.
$\begin{cases}\max\{p,q\}+2& 2\mid p,q\\\max\{p,q\}+1&\text{otherwise}\end{cases}.$
eg4334
15.12.2024 01:27
I claim the answer is $n+1$ for odd $n$ and $n$ for even $n$. This is achieved by taking all odds, proven by that $0$ is even. Call the $n-set$ the set $\{ -n, -n+1, \dots n-1, n\}$. We proceed using induction with the even $n$ case first. $n=2$ is obvious because we can only select one in each of the pairs $\{ -2, 1\}$ and $\{-1, 2 \}$. We assume that we can only pick $n$ numbers from the $n$-set and we need to prove that same result for the $n+2$-set (i.e. selecting $n+3$ numbers from the $n+2$-set is impossible). If FTSOC choosing $n+3$ numbers from the $n+2$-set worked, then we have the following two cases: Case 1: Three numbers from $\{ n+1, n+2, -n-2, -n-1\}$ and $n$ from the $n$-set By symmetry, we only need to consider the cases when we choose $n+1, n+2, -n-1$ and $n+1, n+2, -n-2$. In the first case, we cannot choose $-1$ from the $n$-set nor $-\frac{n+2}{2}$. Now just consider the pairs $\{ 1, n\}, \{2, n-1\}, \dots \{ \frac{n}{2}, \frac{n}{2}+1 \}$ and $\{ -2, -n\}, \{ -3, -n+1\}, \dots \{-\frac{n}{2}, -\frac{n}{2}-2\}$ of which there are $n-1$. We can only choose one from each pair from our restriction, so we can only choose at most $n-1$ numbers from the $n$-set, contradiction. In the second case, we also cannot have $1$ or $\frac{n}{2}+1$. Do the exact same pairing argument with $\{2, n\}, \{3, n-1\}, \dots \{ \frac{n}{2}, \frac{n}{2}+2 \}$ and $\{ -1, -n \}, \{-2, -n+1\}, \dots \{-\frac{n}{2}, -\frac{n}{2}-1 \}$ proving another contradiction. Thus this case is done. Case 2: All numbers from $\{ n+1, n+2, -n-2, -n-1\}$ and $n-1$ from the $n$-set. From the $n$-set, we cannot have $\pm 1$ or $\frac{n}{2}+1, -\frac{n}{2}-1$. Pair up again like $\{ 2, n \}, \{ 3, n-1 \}, \dots \{\frac{n}{2}, \frac{n}{2}+2 \}$ alongside the analogous negative pairs proving another contradiction. Therefore we have shown that if the maximum number from an $n$-set is $n$ (for $n$ even), we can have at most $n+2$ in the $n+2$-set, proving the conclusion by induction. The odd case is the same but I don't want to type it up.