Given that $ \{a_n\}$ is a sequence in which all the terms are integers, and $ a_2$ is odd. For any natural number $ n$, $ n(a_{n \plus{} 1} \minus{} a_n \plus{} 3) \equal{} a_{n \plus{} 1} \plus{} a_n \plus{} 3$. Furthermore, $ a_{2009}$ is divisible by $ 2010$. Find the smallest integer $ n > 1$ such that $ a_n$ is divisible by $ 2010$.

P.S.: I saw EVEN instead of ODD. Got only half of the points.

This is not a proof!!!!!
$ a_1 \equal{} 0$, $ a_2 \equal{} 2k\plus{}1$
$ a_{n\plus{}1}\equal{}\frac{(n\plus{}1)}{n\minus{}1} a_n\minus{}3$
$ \therefore$
$ \begin{array}{c}
 a_3\equal{}6 k \\
 a_4\equal{}12 k\minus{}3 \\
 a_5\equal{}20 k\minus{}8 \\
 a_6\equal{}30 k\minus{}15
\end{array}$
$ \therefore$
$ a_n\equal{}k (n\minus{}1) n\minus{}(n\minus{}3) (n\minus{}1)$
$ a_{2009}\equal{}4034072 k\minus{}4028048$
$ (4034072 k\minus{}4028048\equiv 2 k\plus{}2002\equiv 0) \bmod 2010$
$ (2 k\equiv \minus{}2002\equiv 8) \bmod 2010$
$ k\equal{} 4 \plus{} 1005 m$
$ a_n\equiv 3 (n\minus{}1) (335 m n\plus{}n\plus{}1)$

?$ m\equal{}0$
$ \therefore$
$ \left(3 (n\minus{}1) (n\plus{}1)\equiv 3 n^2\plus{}2007\right) \bmod 2010$
$ \left(3 n^2\equiv 3\right) \bmod 2010$
?$ \left(n^2\equiv \right) \bmod 670$
$ \cdots$

[quote="EulerIntegral"]This is not a proof!!!!!
$ a_1 \equal{} 0$, $ a_2 \equal{} 2k \plus{} 1$
$ a_{n \plus{} 1} \equal{} \frac {(n \plus{} 1)}{n \minus{} 1} a_n \minus{} 3$
$ \therefore$
$ \begin{array}{c} a_3 \equal{} 6 k \\
a_4 \equal{} 12 k \minus{} 3 \\
a_5 \equal{} 20 k \minus{} 8 \\
a_6 \equal{} 30 k \minus{} 15 \end{array}$
$ \therefore$
$ a_n \equal{} k (n \minus{} 1) n \minus{} (n \minus{} 3) (n \minus{} 1)$
$ a_{2009} \equal{} 4034072 k \minus{} 4028048$
$ (4034072 k \minus{} 4028048\equiv 2 k \plus{} 2002\equiv 0) \bmod 2010$
$ (2 k\equiv \minus{} 2002\equiv 8) \bmod 2010$
$ k \equal{} 4 \plus{} 1005 m$
$ a_n\equiv 3 (n \minus{} 1) (335 m n \plus{} n \plus{} 1)$

?$ m \equal{} 0$
$ \therefore$
$ \left(3 (n \minus{} 1) (n \plus{} 1)\equiv 3 n^2 \plus{} 2007\right) \bmod 2010$
$ \left(3 n^2\equiv 3\right) \bmod 2010$
?$ \left(n^2\equiv \right) \bmod 670$
$ \cdots$[/quote]
i think $ n\equal{}669$

[quote="∫FaiLurE∮"][quote="EulerIntegral"]This is not a proof!!!!!
$ a_1 \equal{} 0$, $ a_2 \equal{} 2k \plus{} 1$
$ a_{n \plus{} 1} \equal{} \frac {(n \plus{} 1)}{n \minus{} 1} a_n \minus{} 3$
$ \therefore$
$ \begin{array}{c} a_3 \equal{} 6 k \\
a_4 \equal{} 12 k \minus{} 3 \\
a_5 \equal{} 20 k \minus{} 8 \\
a_6 \equal{} 30 k \minus{} 15 \end{array}$
$ \therefore$
$ a_n \equal{} k (n \minus{} 1) n \minus{} (n \minus{} 3) (n \minus{} 1)$
$ a_{2009} \equal{} 4034072 k \minus{} 4028048$
$ (4034072 k \minus{} 4028048\equiv 2 k \plus{} 2002\equiv 0) \bmod 2010$
$ (2 k\equiv \minus{} 2002\equiv 8) \bmod 2010$
$ k \equal{} 4 \plus{} 1005 m$
$ a_n\equiv 3 (n \minus{} 1) (335 m n \plus{} n \plus{} 1)$

?$ m \equal{} 0$
$ \therefore$
$ \left(3 (n \minus{} 1) (n \plus{} 1)\equiv 3 n^2 \plus{} 2007\right) \bmod 2010$
$ \left(3 n^2\equiv 3\right) \bmod 2010$
?$ \left(n^2\equiv \right) \bmod 670$
$ \cdots$[/quote]
i think $ n \equal{} 669$[/quote]

269 < 669
n=269 also satisfies n^2=1 ( mod 670 )

let $ a_n \equal{} b_n \plus{} 3n \minus{} 3$
we attain $ b_{n \plus{} 1} \equal{} \frac {n \plus{} 1}{n \minus{} 1}b_n$
so we determine : $ b_n \equal{} \frac {n(n \minus{} 1)}{2}a_2$
so $ a_n \equal{} \frac{n(n \minus{} 1)}{2}a_2 \plus{} 3n \minus{} 3$
now, it is esay !! :roll:

I hope there isn't any careless mistake
$ (n \minus{} 1)a_{n \plus{} 1} \equal{} (n \plus{} 1)a_n \plus{} 3 \minus{} 3n$
$ \frac {a_{n \plus{} 1}}{(n \plus{} 1)n} \equal{} \frac {a_n}{n(n \minus{} 1)} \minus{} \frac {3}{n(n \plus{} 1)}$
$ \frac {a_{n \plus{} 1}}{(n \plus{} 1)n} \minus{} \frac {3}{n \plus{} 1} \equal{} \frac {a_n}{n(n \minus{} 1)} \minus{} \frac {3}{n}$
Therefore,
$ \frac {a_n}{n(n \minus{} 1)} \minus{} \frac {3}{n} \equal{} \frac {a_2}{2} \minus{} \frac {3}{2}$
This implies
$ a_n \equal{} \frac {n(n \minus{} 1)}{2}a_2 \plus{} 3(n \minus{} 1) \minus{} \frac {3n(n \minus{} 1)}{2}$

Put n = 2009, and mod 2010
$ \minus{} 1004a_2 \minus{} 6 \plus{} 3 \times 1004 \equiv 0 (mod 2010)$
$ 1004(a_2 \minus{} 3) \equiv \minus{} 6 (mod 2010)$
$ 2008(a_2 \minus{} 3) \equiv \minus{} 12 (mod 2010)$
$ a_2 \minus{} 3 \equiv 6 (mod 1005)$
$ a_2 \equiv 9 (mod 1005)$
But $ a_2$ is odd, so $ a_2 \equiv 9 (mod 2010)$

Put this into the formula of $ a_n$,
$ a_n \equal{} \frac {n(n \minus{} 1)}{2}9 \plus{} 3(n \minus{} 1) \minus{} \frac {3n(n \minus{} 1)}{2} \equal{} 3n(n \minus{} 1) \plus{} 3(n \minus{} 1) \equal{} 3(n^2 \minus{} 1) (mod 2010)$
2010 = 2*3*5*67, so to have $ a_n \equiv 0 (mod 2010)$, we need $ n^2 \equiv 1 (mod 670)$
$ 670 | (n \minus{} 1)(n \plus{} 1)$
Divisible by 2 means $ n$ is odd.
Divisible by 5 means $ n \equiv 1 or \minus{} 1 (mod 5)$
Same for 67
Obviously, the smallest possible $ n$ would then be 66.

There is a mistake at the last part - everything up to n^2=1 (mod670) are alright, but your answer (66) doesn't satisfy it as it should be odd =.=
Anyway, the smallest answer should be 269 following your proof


search
geometry
3D geometry
sphere
ratio
trigonometry
symmetry

Can someone tell me any cool (simple) properties of circles that might be useful on AMC tests?

And speaking of, for me the AMC only comes in February. Why does it seem like we discuss it on AoPS all year round?

[quote="Hexaditidom"]Can someone tell me any cool (simple) properties of circles that might be useful on AMC tests?[/quote]

I would suggest that you look in a math book (maybe AoPS :D) or search the internet.  Generally, though, you won't need too many theorems/properties that aren't intuitive/obvious.  Only one that I can think of for now that is an exception to that is the Pythagorean Theorem :P.

[quote]And speaking of, for me the AMC only comes in February. Why does it seem like we discuss it on AoPS all year round?[/quote]

We are just [i]that[/i] into AMC--we all study 5 hours a day all year round.  Just kidding, but the forum stays all year round for anyone wanting information and for the people who actually do study when it's not AMC season.

You might want to research cyclic quadrilaterals and Ptolemy's Theorem.

2 more things:

This has bugged me for a long time. Is there a difference between cos2 :theta:  and (cos :theta:)2 ?

And related to the spheres problem but simpler:

3 circles each with radius r. Each one is tangent to the other 2. There's a fourth circle tangent to the other 3 with a radius r_2 less than r. What is the area of the circle?

Extra challenge: What is the ratio of the fourth circle's area, to that of an outer circle (tangent to the first 3)?

[quote="Hexaditidom"]
This has bugged me for a long time. Is there a difference between cos2 :theta:  and (cos :theta:)2 ?

[/quote]

No, they are exactly the same thing. Its very easy to get confused though - probably because $\cos^{-1}x \ne (\cos x)^{-1}$.

For circles, look up power of a point.  Learn about the angle relationships of inscribed angles and all that stuff.  The symmetry of a circle can also come in handy.  Usually you will have equal angles, equal lengths (think radii), similar triangles, etc... lying all everywhere in the problem.

Most important property of a circle is that the center is equidistant to every point on the circle. :D Seriously though, that's usually all you need.


For the inverse you switch every x with a y and then solve.  I don't know of any other way.  Well maybe you could look at the graph but that is a very inaccurate way.

Joint variation is were something changes with two or more variables. e.g. Y varies jointly as the product of z and w.  You represent this as y=zwk.  It can extend farther I believe but this is about all I can remember right now.

Yes, well joint variation can be a combination of diff types of variation, also.

For example, y varies jointly with the product of x and t, and inversely with the square root of w.

y = k* xt / sqrt(w)


According to the [url=http://www.cee.org/sites/default/files/RSI_09_brochure_appliction_online.pdf]RSI brochure[/url], notification of acceptance wasn't supposed to occur until "Mid-March." Oddly enough, I [url=http://talk.collegeconfidential.com/summer-programs/457031-research-science-institute-rsi-2009-a-51.html]and several others[/url] received confirmation of acceptance/alternate status today.

I'm anxious to meet all of those on AoPS who have been accepted -- congrats to everyone who made it, and good luck to those who are currently on the waitlist.

Hmm. I applied, but no word yet, although I'm fairly sure I will not make it: for one thing, I have a classmate who also applied who is pretty much better than me at every relevant aspect on paper (and perhaps beyond it), so there's not much hope for me. :P
But if by some miracle I make it, I will be sure to cheer very loudly with caps on this topic.

I have also made it to this year's RSI. Congrats to anyone else, and I'm excited to hear from anyone else on AoPS who might have made it!

Also, whatever happened to Mid-March... But I'm not complaining

Good luck, Brut3Forc3.

I am accepted as well =D =D

Congrats to whoever is in, and good luck to those who don't know yet (it's still pretty early).

[quote="hillarryous"]I'll be doing biology research. I put down cell biology for my first choice and biophysics for my second choice.

I wouldn't be able to do any math research worth writing a paper and presenting.[/quote]
what prior science stuff have you done?

Have any of you received any more information from CEE? I think they said they'd send a booklet in late April, but I haven't gotten anything.


pigeonhole principle
induction
ceiling function
symmetry
combinatorics
inequalities

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$.

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.

[hide]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.[/hide]

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.

Let $ A_n$ = $ ( \minus{} n, \minus{} n \plus{} 1... \minus{} 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 \plus{} 1$ elements. Furthermore, any good subset of $ A_n$ (n is odd) with $ n \plus{} 1$ elements is one of two configurations: i) contains only odd elements from $ A_n$ or ii) contains the elements $ \pm (n,n \minus{} 1...[n/2] \plus{} 1)$.

Proceed with induction: the claim is clear for $ n \equal{} 1$ and $ n \equal{} 2$. Now suppose the claim is proven up to $ n \minus{} 1$. Suppose $ n$ is odd. To find all possible configurations for a good subset of size $ n \plus{} 1$ from $ A_n$, note that from the subset $ A_{n \minus{} 2}$ we have at most $ n \minus{} 1$ elements, so we have at lest two elements from $ B \equal{} ( \minus{} n, \minus{} n \plus{} 1, n \minus{} 1, n)$

Suppose we have two elements from $ B$ and $ n \minus{} 1$ elements from $ A_{n \minus{} 2}$. Based on the elements taken from $ A_{n \minus{} 2}$ (note n-2 is odd), we cannot have $ \pm (n \minus{} 1)$. So we take $ \minus{} n,n$ from $ B$. This implies that we take just all odd elements from $ A_{n \minus{} 2}$. So for this case, our claim holds (the good $ n \plus{} 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 \minus{} 2}$ into disjoint pairs $ \pm (x,n \minus{} 1 \minus{} x)$ from which we make only take one element each and each has two distinct elements (so we rule out $ (n \minus{} 1)/2,(n \minus{} 1)/2$. Then we have $ n \minus{} 3$ such pairs and we need to take $ n \minus{} 3$ elements. However, notice that we cannot take $ \pm 1$ or two numbers would sum to $ \pm n$. then we must take $ \pm (n \minus{} 2)$. But then we cannot take $ \pm 2$ or two numbers would sum to $ \pm n$ so we have to take $ \pm (n \minus{} 3)$... continuing this way constructs the goodsubset of size $ n \plus{} 1$ that fits the description of our claim.

Now suppose we take three elements from $ B$. WLOG take $ \minus{} n \plus{} 1, n \minus{} 1, n$. But this leads to a contradiction by pigeonhole because we can only have $ n \minus{} 1$ elements from $ A_n$.

So suppose we take $ \minus{} n, n \minus{} 1, n$. We need $ n \minus{} 2$ elements from $ \minus{} n \plus{} 2...n \minus{} 2$. Note we cannot have $ 1$ or $ (n \minus{} 1)/2$. Partition those disjoint subsets again into those that either sum to $ n$ or $ \minus{} (n \minus{} 1)$. We now have $ n \minus{} 3$ pairs of elements from which we can only take one each. But we needed $ n \minus{} 2$. Contradiction.

Now that we have established the only possible configurations of good subsets of size $ n \plus{} 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 \plus{} 1|$ configuration we cant take any numbers lower). So $ n \plus{} 1$ is the maximum size for odd $ n$.

Now consider $ A_n$ when $ n$ is even. If we take neither $ \minus{} n,n$ we cannot achieve $ n \plus{} 1$ by taking elements from just $ A_{n \minus{} 1}$. If we take both of $ \minus{} n,n$, a partition of $ A_{n \minus{} 1}$ (done just like in earlier cases) shows $ n \plus{} 1$ is impossible. If we take just $ n$, we need $ n$ elements from $ A_{n \minus{} 1}$ This restricts it to only two possible configurations, both of which have two numbers that add to $ \minus{} n$. So $ n \plus{} 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\plus{}1$ element subset for odd $ n$ until a few minutes left...

Outline (very inelegant)
[hide]Construction: take all the odd numbers.
Induction for evens (odd follows trivially). Assume the claim for $ n \equal{} 2(k \minus{} 1)$. Suppose for $ 2k$ we can have $ 2k \plus{} 1$ elements. Then we need to add at least 3 "new" elements from the set $ \{ \minus{} 2k, \minus{} 2k \plus{} 1, 2k \minus{} 1, 2k\}$.
Case 1: we add $ \minus{} 2k, \minus{} 2k \plus{} 1, 2k \minus{} 1$ but not $ 2k$ (or $ 2k$ but not $ 2k \minus{} 1$, but this is equivalent). Then we need at least $ 2k \minus{} 2$ "old" elements. Notice for $ x \plus{} y \equal{} 2k \minus{} 1$ we can have at most one of $ x, y$, so from the set $ 1, 2, .., 2k \minus{} 2$ we have at most $ k \minus{} 1$ elements. Similarly, from the set $ \minus{} 1, \minus{} 2, ..., \minus{} (2k \minus{} 2)$ we have at most $ k \minus{} 1$ elements. Thus we must have equality which means we must pick one from each pair that sums to $ 2k \minus{} 1$. On the other hand, notice for any $ x \plus{} y \equal{} 2k$ we can have at most one of $ x, y$. Now, since $ 2k \minus{} 1$ is in the set, $ 1$ is not. Then $ 2k \minus{} 2$ must be in the set, else we have fewer than $ k \minus{} 1$ elements from $ 1, 2, .., 2k \minus{} 2$. Continuing this argument, we see that $ 1, 2, ..., k$ are not in the set, leaving $ k \minus{} 2$ elements from $ 1, 2, .., 2k \minus{} 2$. Contradiction.
Case 2 and 3: similar arguments.
[/hide]

5 pages.

[hide]The answer is $ 2\lceil\dfrac{n}{2}\rceil$. That is, when $ n$ is even, $ n$, and when $ n$ is odd, $ n\plus{}1$. This is achievable by taking all of the odd elements in the set, then $ a\plus{}b\plus{}c$ is odd, which is obviously not zero.

We first prove that the size of the set is at most $ n\plus{}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\plus{}1$. Note that if $ k>\dfrac{n}{2}$, we will have at most $ n\plus{}1$ elements, contradiction. Thus, $ k\le\dfrac{n}{2}$. Consider the following $ n\minus{}2k$ pairs of integers: $ \{\minus{}n\plus{}j,n\minus{}j\minus{}k\}$ for $ 0\le j\le n\minus{}2k\minus{}1$. Notice that the terms in each pair sum to $ \minus{}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 $ \minus{}2k,\minus{}2k\plus{}1,\minus{}2k\plus{}2,\ldots,\minus{}k$, and $ n\minus{}k\plus{}1,n\minus{}k\plus{}2,\ldots,n$, by the minimality of $ k$. But note that $ \minus{}2k$ cannot be in $ S$, since we have $ k$ in $ S$ and this will give us $ \minus{}2k\plus{}k\plus{}k\equal{}0$. After eliminating $ \minus{}2k$, we have at most $ 2k$ terms here, then at most $ n\minus{}2k$ in the pairs (one from each), plus $ k$. This gives us a total of at most $ n\plus{}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\plus{}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\plus{}2}{2}$ up to $ \pm{n}$. Now, note that to have $ n\plus{}1$ terms, we need to have exactly one term from each pair in the $ S$, and all of $ \minus{}2k\plus{}1,\minus{}2k\plus{}2,\ldots,\minus{}k$ and $ n\minus{}k\plus{}1,n\minus{}k\plus{}2,\ldots,n$ in $ S$ as well. We now consider three cases.

Case 1: $ 2k\le n\le 5k\minus{}3$. We claim that we will be able to find a term $ a$ among $ \minus{}2k\plus{}1,\minus{}2k\plus{}2,\ldots,\minus{}k$ and a term $ b$ among $ n\minus{}k\plus{}1,n\minus{}k\plus{}2,\ldots,n$ such that $ 2a\plus{}b\equal{}0$. Consider a term among $ \minus{}2k\plus{}1,\minus{}2k\plus{}2,\ldots,\minus{}k$, of the form $ a\equal{}\minus{}2k\plus{}i$ where $ 1\le i\le k$. Then, we can find a corresponding $ b$ if and only if $ n\minus{}k\plus{}1\le 4k\minus{}2i\le n$. Rearranging this, we want $ 4k\minus{}2i\le n\le 5k\minus{}2i$. But we see as we run this over $ 1\le i\le k$, every $ n$ within $ 2k\le n\le5k\minus{}3$ will be in one of these intervals. since the size of the interval is $ k\minus{}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\equal{}1$, in which we have $ n\equal{}2$, and the only interval we have to consider is $ 2\le n\le2$, in which $ n\equal{}2$ clearly falls. Therefore, if we take all of these elements in $ S$, we will be able to find $ a\plus{}b\plus{}c\equal{}0$, contradiction.

Case 2: $ n\equal{}5k\minus{}2$. Note that since $ n$ is even, we need $ k$ to be even. Now, note that since $ k\ge2$, we have $ n\minus{}k\plus{}\dfrac{k\plus{}2}{2}$ and $ \minus{}2k\plus{}\dfrac{k\plus{}2}{2}$ in $ S$ (recall that $ n\minus{}k\plus{}i$ and $ \minus{}2k\plus{}i$ are in $ s$ as long as $ 1\le i\le k$). Now, the sum of these two terms is $ n\minus{}3k\plus{}k\plus{}2\equal{}n\minus{}2k\plus{}2$. Thus, we cannot have $ \minus{}n\plus{}2k\minus{}2$ in $ S$. But since $ 0\le 2k\minus{}2\le n\minus{}2k\minus{}1\equal{}3k\minus{}3$, this means that $ n\minus{}3k\plus{}2\equal{}2k$ is in $ S$. But we have $ \minus{}k$ in $ S$, so now $ (\minus{}k)\plus{}(\minus{}k)\plus{}2k\equal{}0$, contradiction.

Case 3: $ n\ge5k\minus{}1$. Consider the pairs of terms $ \{\minus{}2k\plus{}i,n\minus{}k\plus{}i\}$ for $ 1\le i\le k$, which we know we have to have in $ S$. Their sum is $ n\minus{}3k\plus{}2i$. Thus, we cannot have $ \minus{}n\plus{}3k\minus{}2i$ in $ S$. But note that $ 0\le 3k\minus{}2i\le n\minus{}2k\minus{}1$, which follows from the assumption that $ n\ge5k\minus{}1$ and $ 1\le i\le k$. This means that $ n\minus{}4k\plus{}2i$ is in $ S$ for $ 1\le i\le k$. That is, $ n\minus{}2k,n\minus{}2k\minus{}2,\ldots,n\minus{}4k\plus{}2$ are all in $ S$. Note that $ n\minus{}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\minus{}2i,n\minus{}2i\minus{}2,\ldots,n\minus{}2i\minus{}2k\plus{}2$ are all in $ S$ such that $ n\minus{}2i\minus{}2k\plus{}2>2k$, then we can get that $ n\minus{}2i\minus{}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\minus{}2i\in S$ and additionally $ \minus{}k\in S$. Thus, we cannot have $ \minus{}n\plus{}2i\plus{}k\in S$. But we can get that $ 0\le 2i\plus{}k\le n\minus{}2k\minus{}1$, so $ n\minus{}2i\minus{}2k\in S$. This, finally, completes the proof.[/hide]

[hide="Hmm .. 4 pages. Wonder if ill get docked for messing up one of the last cases"]Let $ Z_n$ be the set of subsets satisfying the $ a \plus{} b \plus{} c \neq 0$ condition for $ n$, and let $ s_n$ be the largest size of a set in $ Z_n$. Let $ n \equal{} 2k$ if $ n$ is even, and $ n \equal{} 2k \minus{} 1$ if $ n$ is odd. We note that $ s_n \ge 2k$ due to the following constuction:
\[ \{ \minus{} 2k \plus{} 1, \minus{} 2k \plus{} 3, \ldots, 2k \minus{} 3, 2k \minus{} 1\}
\]
or all of the odd numbers in the set. Then the sum of any three will be odd and thus nonzero.

[b]Lemma 1[/b]: $ s_{n \plus{} 1} \le s_{n} \plus{} 2$. If $ M_{n \plus{} 1} \in Z_{n \plus{} 1}, |M_{n \plus{} 1}| \equal{} s_{n \plus{} 1}$, then we note that $ M_{n \plus{} 1} \setminus \{ \minus{} 2n \plus{} 1, 2n \minus{} 1\} \in Z_n$, so $ |M_{n \plus{} 1}| \minus{} 2 \le s_n$. $ \square$

[b]Lemma 2[/b]: $ s_{2k} \equal{} s_{2k \minus{} 1}$. Suppose, for sake of contradiction, that $ M_{2k} \in Z_{n \plus{} 1}$ and $ M_{2k} > s_{2k \minus{} 1}$. Remove $ 2k, \minus{} 2k$ from $ M_{2k}$, and partition the rest of the elements into two sets $ P_{2k \minus{} 1}, Q_{2k \minus{} 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 \plus{} 0 \plus{} 0 \equal{} 0$). WLOG, suppose $ |P_{2k \minus{} 1}| \ge |Q_{2k \minus{} 1}|$. Then $ |P_{2k \minus{} 1}| \plus{} |Q_{2k \minus{} 1}| \ge s_{2k \minus{} 1} \minus{} 1 \ge 2k \minus{} 1$. We now show the following two sub-results:

Sub-lemma (A): if $ |P_{2k \minus{} 1}| \ge k$, $ \minus{} 2k \not \in M_{2k}$ [and similar for $ Q$]; and

Sub-lemma (B): we cannot have both $ |P_{2k \minus{} 1}| \plus{} |Q_{2k \minus{} 1}| \ge 2k$ and $ |Q_{2k \minus{} 1}| < k$ simultaneously hold.

This is sufficient, because the only two elements that may be in $ M_{2k}$ that are not in $ P_{2k \minus{} 1}, Q_{2k \minus{} 1}$ are $ 2k$ and $ \minus{} 2k$; for $ M_{2k} > s_{2k \minus{} 1}$, we must either have $ |P_{2k \minus{} 1}| \plus{} |Q_{2k \minus{} 1}| \equal{} s_{2k \minus{} 1} \minus{} 1 \ge 2k \minus{} 1$ and both $ 2k, \minus{} 2k \in M_{2k}$ [but by pigeonhole $ |P_{2k \minus{} 1}| \ge k$, see sub-lemma (A)], or $ |P_{2k \minus{} 1}| \plus{} |Q_{2k \minus{} 1}| \equal{} s_{2k \minus{} 1} \ge 2k$, and $ 2k \in M_{2k}$, in which case by (A) we must have $ |Q_{2k \minus{} 1}| < k$, violating (B).

(A): Partition $ \{1,2,\ldots,2k \minus{} 1\}$ into the $ k$ sets $ \{k\}, \{1,2k \minus{} 1\}, \{2, 2k \minus{} 2\}, \cdots, \{k \minus{} 1, k \plus{} 1\}$. Because $ (k \plus{} \delta) \plus{} (k \minus{} \delta) \minus{} 2k \equal{} 0$, then if any of those sets are within $ P_{2k \minus{} 1}$, $ \minus{} 2k \not \in M_{2k}$. But by Pigeonhole at most $ k \minus{} 1$ elements may be in $ P_{2k \minus{} 1}$, contradiction.

(B): We prove this statement with another induction. We see that the statement easily holds true for $ k \equal{} 1$ or $ 2$, so suppose it is true for $ k \minus{} 1$, but [for sake of contradiction] false for $ k$. Let $ P_{2k \minus{} 3} \equal{} P_{2k \minus{} 1} \setminus \{2k \minus{} 2, 2k \minus{} 1\}$, and similarly for $ Q_{2k \minus{} 3}$. Again WLOG $ |P_{2k \minus{} 3}| \ge |Q_{2k \minus{} 3}|$. Then we have $ |P_{2k \minus{} 1}| \plus{} |Q_{2k \minus{} 1}| \le |P_{2k \minus{} 3}| \plus{} |Q_{2k \minus{} 3}| \plus{} 4$.

*If $ |P_{2k \minus{} 3}| \plus{} |Q_{2k \minus{} 3}| \ge 2k \minus{} 2$, then by inductive hypothesis, we must have $ |P_{2k \minus{} 3}| \equal{} |Q_{2k \minus{} 3}| \equal{} k \minus{} 1$. But (A) implies that we cannot add $ 2k \minus{} 2$ or $ \minus{} 2k \plus{} 2$. So to satisfy $ |P_{2k \minus{} 1}| \equal{} |Q_{2k \minus{} 1}| \ge 2k$ we must have $ 2k \minus{} 1, \minus{} 2k \plus{} 1$ added, but then $ |P_{2k \minus{} 1}| \equal{} |Q_{2k \minus{} 1}| \equal{} k$ contradiction.

*If $ |P_{2k \minus{} 3}| \plus{} |Q_{2k \minus{} 3}| \equal{} 2k \minus{} 3$, then at least three of $ \{2k \minus{} 2, 2k \minus{} 1, \minus{} 2k \plus{} 2, \minus{} 2k \plus{} 1\}$ added. But $ |P_{2k \minus{} 3}| \ge k \minus{} 1$, and by (A) we have that $ \minus{} 2k \plus{} 2$ cannot be added. If $ |P_{2k \minus{} 3}| \ge k$, then another grouping similar to (A) shows that $ \minus{} 2k \plus{} 1$ canno be added, contradiction. So $ |P_{2k \minus{} 3}| \equal{} k \minus{} 1$, $ |Q_{2k \minus{} 3}| \equal{} k \minus{} 2$, and adding the three remaining elements gives $ |P_{2k \minus{} 1}| \equal{} |Q_{2k \minus{} 1}| \equal{} k$ contradiction.

*If $ |P_{2k \minus{} 3}| \plus{} |Q_{2k \minus{} 3}| \equal{} 2k \minus{} 4$, then all four of $ \{2k \minus{} 2, 2k \minus{} 1, \minus{} 2k \plus{} 2, \minus{} 2k \plus{} 1\}$ must be added, and furthermore $ |P_{2k \minus{} 3}| > |Q_{2k \minus{} 3}|$. Then $ |P_{2k \minus{} 3}| \ge k \minus{} 1$, and by previous paragraph we cannot add $ \minus{} 2k \plus{} 2$. $ \square$

So we have $ \begin{cases} s_1 & \equal{} 2 \\
s_{2k} & \equal{} s_{2k \minus{} 1} \\
s_{2k \minus{} 1} & \le s_{2k \minus{} 2} \plus{} 2 \\
\end{cases}$ and by induction, that $ s_n \le \boxed{2\left\lceil \frac n2 \right \rceil} \equal{} 2k$, which we showed is achievable above.
[/hide]

[hide="Outline."]
=====
Let $ S_n\equal{}\{\minus{}n,\dots ,n\}$. Call a subset $ X$ of $ S_n$ [i]pretty [/i]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\equal{}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\plus{}0\plus{}0\equal{}0$. For $ n\equal{}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\equal{}2k\plus{}1$, we can only choose $ 2k$ elements from $ S_{2k}$ by assumption and then choose at most $ 2$ of $ \{\minus{}(2k\plus{}1),2k\plus{}1\}$, for a maximum of $ 2k\plus{}2$, so we can't do better. For $ n\equal{}2k\plus{}2$, suppose we could find a subset $ X$ of $ S_{2k\plus{}2}$ with cardinality greater than $ 2k\plus{}2$. We consider $ S_{2k\plus{}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\plus{}2$, we must choose at least three from $ \{\minus{}(2k\plus{}2),\minus{}(2k\plus{}1),2k\plus{}1,2k\plus{}2\}$. This leads to five cases.

CASE ONE: $ \minus{}(2k\plus{}2), \minus{}(2k\plus{}1), 2k\plus{}1$ are in $ X$, $ 2k\plus{}2$ is not.

Here we must choose $ 2k$ elements from $ S_{2k}$. Note that if any of $ 0,1,k\plus{}1$ are in $ X$, we'd have $ 0\plus{}0\plus{}0\equal{}0$, $ \minus{}(2k\plus{}2)\plus{}1\plus{}2k\plus{}1\equal{}0$, or $ (k\plus{}1)\plus{}(k\plus{}1)\minus{}(2k\plus{}2)\equal{}0$, so suppose none of these three are chosen from $ S_{2k}$. Partition the remaining elements of $ S_{2k}$ as follows:

$ \{\{\minus{}2k,\minus{}1\},\{\minus{}(2k\minus{}1),\minus{}2\},\dots ,\{\minus{}(k\plus{}1),\minus{}k\},\{2,2k\},\{3,2k\minus{}1\},\dots ,\{k,k\plus{}2\}\}$

There are $ 2k\minus{}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 $ \minus{}(2k\plus{}1)$ or $ 2k\plus{}2$, which we can pair with $ 2k\plus{}1$ and $ \minus{}(2k\plus{}2)$, respectively, so $ X$ isn't pretty, contradiction.

The other four cases are very similar, just with slightly different partitions.
=====
[/hide]

[quote="sdkudrgn88"]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.[/quote]

Uh what if you use a different algorithm

[quote="sdkudrgn88"]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$.[/quote]

Can you elucidate please? I don't see how this works without assuming that you have a specific subset to work with.

Do you think greedy algorithm works? Basically you take $ \{ \minus{}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.

"Greedy algorithm" isn't a solution at all. Why is the greedy algorithm optimal in this case?

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.

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.

[quote=ABCDE]Does this work?[/quote] Yep, this is actually the official solution if I recall correctly.

We claim the answer is $n$ for $n$ even and $n+1$ for $n$ odd. In both cases, we simply take the subset of all odd numbers as an equality case.

Let $P$ be the set of positive numbers in our subset, and $N$ be the set of negative numbers (note that $0$ is not in our subset since $0+0+0=0$). Now, the condition is equivalent to saying that $-P,-N,P+N$ are disjoint. Note that
\[P+N = \{p+n : p\in P, n\in N\}.\]
We now claim that $|P+N|\ge|P|+|N|-1$. To do this, let $P={x_1<\cdots<x_m}$ and let $N=\{y_1<\cdots<y_n\}$. Then, the following elements are in $P+N$:
\[x_1+y_1<x_2+y_1<\cdots<x_m+y_1<x_m+y_2<\cdots<x_m+y_n.\]This proves the claim. Now, since $-P,-N,P+N$ are disjoint, we have that
\[|-P|+|-N|+|P+N|\le 2n+1\implies |P|+|N|+|P|+|N|-1\le 2n+1\implies |P|+|N|\le n+1.\]This completes the proof for the odd case, but this is not strong enough for the even case.

We will now show that in fact $|P|+|N|\le n$ if $n$ is even. Assume not, so then equality must hold in all the above inequalities. Therefore, $(-P)\cup(-N)\cup(P+N) = \{-n,\cdots,n\}$, and $|P+N| = |P|+|N|-1$. To start, since $0\not\in P,N$, we must have that $n,-n\not\in P+N$, so $n\in P$ and $-n\in N$.

Say that some $x\in P$. Then, since $-n\in N$, we must have that $x-n\in P+N$. However, since $-P,-N,P+N$ are disjoint, we must have that $x-n\not\in -P$, or $n-x\not\in P$. Thus, $x\in P\implies n-x\not\in P$. Therefore, one sees that from the numbers $1,\ldots,n$, at most $1+\frac{n-2}{2}=n/2$ of them can be in $P$ (note that $n/2\not\in P$ since $n/2\in P\implies n-n/2=n/2\not\in P$). Similarly, one can show that there are at most $n/2$ elements in $N$. However, this implies $|P|+|N|\le n$, which is a contradiction, since we started by assuming $|P|+|N|>n$. Therefore, for $n$ even, we can have at most $n$ elements in the subset.

[hide=New Solution from August 30th, 2019]
We claim the answer is $n+1$ for $n$ odd and $n$ for $n$ even, with equality achieved by taking all the odd numbers. Now, suppose we have a set $S$ that works.

Note that $0+0+0=0$, so $0\not\in S$. Thus, we may split $S$ into the positive and negative elements, so $S=A\cup(-B)$ where $A,B\subset[n]$. If we have $a,b,c\in S$ such that $a+b+c=0$, then either two are positive and one is negative, or two are negative and one is positive. For $A$ and $B$, this amounts to saying that
\[(A+A)\cap B = (B+B)\cap A = \emptyset.\]
Write $A=\{a_1<\cdots<a_r\}$ and $B=\{b_1<\cdots<b_k\}$. We claim that $|A|+|B|\le n+1$ if $n$ odd and $|A|+|B|\le n$ if $n$ even.

Suppose $b_1>a_1$. Then,
\[b_1-a_1,\ldots,b_k-a_1\not\in A,\]
so $|A|\le n-k=n-|B|$, so $|A|+|B|\le n$. Similarly if $a_1>b_1$, we have the same result. So WLOG, we may assume $a_1=b_1$.

Suppose $b_k<a_k$. Then, we have
\[a_k-b_1,\ldots,a_k-b_k\not\in A,\]
so $|A|\le n-k=n-|B|$, so $|A|+|B|\le n$. We have the same result if $a_k<b_k$, so we may WLOG assume that $a_k=b_k$. Note that if $|A|=1$, then $b_k=b_1$, so $|B|=1$, and the bounds can be checked to hold for these small cases. Thus, we will assume $|A|,|B|\ge 2$.

In these cases, we have
\[b_2-a_1,\ldots,b_k-a_1\not\in A\]
and
\[a_k-b_1,\ldots,a_k-b_{k-1}\not\in A,\]
both of which individually imply $|A|\le n-k+1$, or $|A|+|B|\le n+1$ (note that we are going to be implicitly assuming $|B|\ge 3$ for a while). Thus, all that we have to show is that $|A|+|B|=n+1$ implies that $n$ is odd. If $|A|+|B|=n+1$, then both estimates are sharp, so in fact
\[A=[n]\setminus\{b_2-a_1,\ldots,b_k-a_1\}=[n]\setminus\{a_k-b_1,\ldots,a_k-b_{k-1}\}.\]
Thee complement sets are ordered, so we have $b_{i+1}-a_1=a_k-b_{k-i}$ for all $1\le i\le k-1$, so \[b_{i+1}+b_{k-i}=a_1+a_k=b_1+b_k,\]
now for all $0\le i\le k-1$. Similarly, we derive $a_{i+1}+a_{r-i}=a_1+a_k$ for all $0\le i\le r-1$.

However, we also have that
\[b_3-a_2,\ldots,b_k-a_2\not\in A,\]
so
\[\{b_3-a_2<\cdots<b_k-a_2\}\subset\{b_2-a_1<\ldots<b_k-a_1\}.\]
We have $b_k-a_2<b_k-a_1$, so in fact
\[\{b_3-a_2<\cdots<b_k-a_2\}\subset\{b_2-a_1<\ldots<b_{k-1}-a_1\},\]
so
\[b_3-b_2=\cdots=b_k-b_{k-1}=a_2-a_1.\]
Combined with the fact that $b_{i+1}+b_{k-i}=b_1+b_k$ for all $0\le i\le k-1$, we have that $(b_i)_{i=1}^k$ is an arithmetic progression of common difference $a_2-a_1$.

If $|A|\ge 3$, then the same logic gives that $(a_i)_{i=1}^r$ is an arithmetic progression of common difference $b_2-b_1=a_2-a_1$. However, this holds trivially if $|A|=2$ as well, so $A$ and $B$ are both arithmetic progressions with the same common difference. We also have that their minimums and maximums match, so in fact $A=B$, so $|A|+|B|=n+1$ is even, so $n$ is odd, as desired.
[/hide]

Throughout this solution define $S_i = \{ -i, -i+1, \dots , -2,-1,1,2, \dots ,i-1, i+1 \}$
First we provide a construction. For odd $n$, $\{n, -n+2, \dots ,-3,-1,1,3, \dots , n-2,n \}$ satisfies the condition. For even $n$, $\{ 1,2,3, \dots ,n-1,n \}$ works.

Consider the set $S_n$. We will construct its maximum subset $M$. Let $i$ be the largest number such that $i,-i \in M$.
Assume $i=2r-1$ is odd. Consider the pairs
$$(1,2r-2) , (-1, -2r+2), (2, 2r-3), (-2, -2r+3), \dots , (r-1, r), (-r+1, -r)$$
From each pair, we can choose at most $1$ number. Consider two cases:

Case 1: $i<n$. Either $i+1$ or $-i-1$ are in $M$.
WLOG $-i-1 = -2r \in M$. Consider $S_{2r-2}$. We will prove that at most $2r-3$ elements can be chosen from $S_{2r-2}$.
Assume for the sake of contradiction, we chose $2r-2$ elements from $S_{2r-2}$. Then we must choose exactly one number from each of the above-defined pairs since there are $2r-2$ pairs.

Clearly, $1 \notin M$ or else $-2r +2r-1+1 =0$. Hence $2r-2 \in M$.
Then, $2 \notin M$ or else $-2r +2r-2 +2=0$. So $2r-3 \in M$.
$$\vdots$$
$r-1 \notin M$ or else $-2r+ r+1 +r-1=0$. So $r \in M$. But then $-2r +r+r =0$. Contradiction.

Hence we can choose at most $2r-3$ elements from $S_{2r-3}$. $$(i+1, -i-1), (i+2, -i-2), \dots , (n,-n)$$ From each pair we can choose at maximum $1$ element. Choosing $2$ contradicts the maximality of $i$. Then $|M| \leq 3+2r-3 + n-(i+1) = n$.

Case 2: $i=n$.
Simply choose 1 element from each pair
$$(1,2r-2) , (-1, -2r+2), (2, 2r-3), (-2, -2r+3), \dots , (r-1, r), (-r+1, -r)$$
This gives $|M| \leq 2r-2 + 2 = 2r =n+1 $ as desired.

Now, assume $i=2r$.  Consider the pairs
$$(1,2r-1) , (-1, -2r+1), (2, 2r-2), (-2, -2r+2), \dots , (r-1, r+1), (-r+1, -r-1)$$
From each pair we can choose at most $1$ element and we cannot choose $-r$ or $r$.
If $i<n$ repeat the argument from Case 1 with these pairs.
If $i=n$ Simply choose 1 element from each pair. This gives $|M| \leq 2r-2 + 2 = 2r =n$ as desired. We are done.

I thought that this was a really nice problem, but it took me quite a long time (like 2.5-3 hours in total)

[hide=Solution]

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:

[b]Case 1[/b]: 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$

[b]Case 2[/b]: 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$.

[b]Case 3[/b]: 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$

[/hide]

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.

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$.

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$.

[b]Claim: [/b]If $n$ is even, the answer is $n$ and if $n$ is odd, $n+1$ is the answer.
[b]Proof:[/b]
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:

[u]Case 1:[/u] 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.

[u]Case 2:[/u] 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.

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.

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$

[hide]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.

[/hide]

[b]Old Solution that I copy and pasted. My proof writing used to be so terrible  :what?: [/b]

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$.

[hide=Solution]
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$

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;
[b]1.[/b] $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.
[b]2.[/b] 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.

[b](a) [/b] $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](b)[/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
[b]1. [/b] 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.

[b]2. [/b]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.

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.

\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)


Anything between $ \sqrt{7}\minus{}\sqrt{3}$ and $ \sqrt{7}\plus{}\sqrt{3}$ is a valid answer. Are you sure you're not leaving out anything?


$x,y,z$ are distinct positive integers such that:

$x$ is a divisor of $y+z+yz$
$y$ is a divisor of $z+x+xz$
$z$ is a divisor of $x+y+xy$

Show that $x,y,z$ can't all be primes.

It takes me just a few houres to solve my own logical [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=659942#659942]problem[/url]  :D

Sorry for the offtopic.


What is the coefficient of x^2 in:
(1 - x) (1 + 2x) (1 - 3x) (1 + 4x)… (1-15x)


Starting with a set of any 35 integers, you are allowed to select 23 of them at random and add 1 to each of the selected numbers and replace the originial numbers by the new set of numbers in the set. Prove that for any set of 35 integers, one can do this process repeatedly to arrive at all 35 integers equal.
eg-{1,2,3,4,5,6,....,34,35} can be replaced by {2,3,4,...,22,23,24,24,25,26,...,34,35} by selecting 1,2,3,4,...,22,23 and doing the process.

You can increment $ 2 \cdot 23 \minus{} 35 \equal{} 11$ of the elements by one with respect to the others by incrementing those $ 11$ elements and half of the remaining elements, and then incrementing those $ 11$ elements and the other half of the remaining elements. Similarly, you can increment any $ 4 \cdot 11 \minus{} 35 \equal{} 9$ elements of your choice, and any $ 4 \cdot 9 \equal{} 35 \equal{} 1$ element of your choice, from which the problem statement is obviously achievable.


superior algebra
superior algebra solved

I had the exam in my introductory algebra course today. It did not go well! The following is the third question (of 6), and I couldn't figure it out:

Show that a nonzero commutative ring $R$, with identity, is a field if and only if the only ideals of $R$ are $\{0\}$ and $R$ itself.

The only if part is straightforward, but how are you supposed to prove if?

take an ideal $(a) \subset R$, this is either $0$ (if $a=0$), or $R$: in the latter case, this means that $a$ is invertible, since $1 \in (a)$.

[quote="Kalle"]What is $(a)$?[/quote]
I haven't dealt with ring theory yet, but I assume this means the ideal generated by $a$:  $(a)=\{r\cdot a | r \in R\}$.

yes, $(a)$ is the minimal ideal containing $a$, which coincides with what yannick wrote...

Ah, I didn't know of that ideal. Of course I should have thought about it, I spent quite a lot of time trying to find an ideal to use like you did ma_go


Consider connected graph [tex]G[/tex]. Define [tex]G_n[/tex] as graph obtained from [tex]G[/tex] using the following operation:in [tex]G_n[/tex] two vertices [tex]u,v[/tex] are connected iff [tex]dist_G(u,v)\leq n[/tex]. ( [tex]dist_G(u,v)[/tex] is distance between these vertices, i.e. the length of minimal path in [tex]G[/tex] connecting these vertices)
For which minimal value of n holds the following statement:
for each [tex]G[/tex], [tex]G_n[/tex] is Hamiltonian graph (there is Hamilton circuit in [tex]G_n[/tex])

Just in case you don't know, a Hamilton cirucit is a path that goes through each vertex [i]exactly once[/i] and returns back to the starting vertex without retracing an edge. Unlike an Euler circuit, you do not have to visit every edge and you can't visit the same point more than once.

A good site is [url]http://www.ctl.ua.edu/math103/hamilton/hamilton.htm[/url]

Here's my work thus far:

[hide]First off, G_1=G. Secondly, if the distance between two points in G is m, then their distance in G_n will be ceiling(m/n). (The ceiling of a number is the least integer greater than or equal to that number). I'm not quite sure this is useful, but who knows?[/hide]

It may (or may not) help to think about it as connecting all the nodes except the ones that are > n apart.

I'm pretty sure that [hide]G_2 is not necessarily Hamiltonian. Draw a 3X3 grid of points and draw a big letter E (you should have drawn 8 unit segments). If I didn't mess up somewhere, the G_2 obtained from that graph is not Hamiltonian.[/hide]

[quote="probability1.01"]You're correct, because in order to pass through the "center," you must either go directly on the center node or use two of the three nodes connected to it in G.[/quote]

I don't think I quite understand what you're saying. Which point is the "center"? I think we should include some labels.

Yeah, what I mean by "center" is (1, 2), assuming the grid is (x, y) 1 :le: x, y :le: 3 (actual shape doesn't matter, but this is easier to sort).


quadratics
number theory proposed
number theory

Prove that if n is a quadratic residue in all prime mods, then that n must be a perfect square.


inequalities
calculus
function
geometry
3D geometry
integration
real analysis

Show that for all monotonically increasing function $f$ with $f(0)=0$ and $f(1)=1$, that
\[f(1/10)+f(2/10)+\dots+f(9/10)+f^{-1}(1/10)+\dots+f^{-1}(9/10)\leq 99/10 \]
[hide]
Im not sure if this is the right track but its what i have so far.
Given the unit cube in the first quadrant of R2 we consider the line $f(x)=x$. Now notice that we can consider the set of monotonic functions below $f(x)=x$ since there is a one to one correspondence between the functions above an below the line, and thus the sum,inverse sum value for corresponding functions is the same. This in mind we know that for functions below f takes on its greatest value at the line f(x)=x,(note i think this assumption can be made because the function is monotonically increasing on this interval), thus the sum has value
$f(1/10)+f(2/10)+\dots+f(9/10)+f^{-1}(1/10)+\dots+f^{-1}(9/10)$=$1/10+\dots+9/10+1/10+\dots+9/10$=$90/10$.
But this isnt right! Either im missing a trivial 9/10 or im missing something bigger. Anyway, please tell me.
[/hide]

Perhaps that "for some" should be "for all"?

Draw an example. The solution to this problem is very easy visually.
Note that $\int_{0}^{1}f(x)\,dx+\int_{0}^{1}f^{-1}(x)\,dx=1$; the integral of $f$ is the area below the graph of $f$ in the square, and the integral of $f^{-1}$ is the area above the graph in the square. If we divide our sum by 10, it's a sum of left endpoint Riemann sums for the two integrals; in the picture, these represent nonoverlapping areas.

[hide="The crux"]The missing band between the two areas includes the entire square with vertices $(0,0),(\frac1{10},0),(\frac1{10},\frac1{10}),(0,\frac1{10})$. With that taken out, the remaining area must be less than $\frac{99}{100}$.[/hide]


Let $ a,b,c$≥$ 0$ satisfying $ a^3\plus{}b^3\plus{}c^3\equal{}3$.Prove that
$ (ab)^4\plus{}(bc)^4\plus{}(ca)^4$≤$ 3$

[quote="SUPERMAN2"]Let $ a,b,c$≥$ 0$ satisfying $ a^3 \plus{} b^3 \plus{} c^3 \equal{} 3$.Prove that
$ (ab)^4 \plus{} (bc)^4 \plus{} (ca)^4$≤$ 3$[/quote]
See the Namdung's post here:
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=34428


Assume $a,b,c\geq0$ and $a+b+c+abc=1$. Prove that
\[
ab+bc+ca\leq\frac{(2+abc)(1+2abc)}{7-abc}.
\]


This is not a very hard problem, but it has some interesting variations.  Here's the idea:

Every player in the game is given a six sided die.  The players are seperated into different rooms so they do not see their oppenents' outcomes.  The goal of the game is to get the highest final number out of anybody else in the game.  In the game, there are [i]a[/i] rounds.  On the first round, you roll the die.  You keep the number shown if it is a "good roll" (I will get back to that) or wait for the next round if it is a bad roll.  If you keep the roll, you may not participate in the remaining rounds.  After all the rounds are completed, the players join in one room.  Whoever has the highest kept number is the winner.

There is an algorithm for playing that will get you the highest probability of winning.  If there are [i]a[/i] rounds, it is currently the [i]b[/i]th round and I got a roll of [i]c[/i].  I should keep this roll if [i]n[/i] is less than one half where [i]n[/i] is a number in terms of [i]a[/i], [i]b[/i], and [i]c[/i].  Find [i]n[/i].

The first variation is that one person (not you) is given one extra round.  What will [i]n[/i] be in this case?

The second variation is that you know your oppenents' outcomes and [i]d[/i] is the highest opponent's outcome so far.  What is [i]n[/i] now?

Finally, consider the case where the winner is the one with the highest average of rolls.  In terms of [i]a[/i], [i]b[/i], [i]c[/i], and all your previous rolls, find [i]n[/i].

I don't think you can find an algorithm to maximize your chance of winning unless you know the other players' strategy.  Maybe you want an algorithm to maximize the expected value of the roll you keep?

That's what the question was supposed to imply.

I don't know if this answers any of the questions, but I was just thinking about the problem, do I keep a roll if I have $x$ rounds left and wish to have the highest personal role possible?  (in your terms, $x=a-b$

Basically, if the chances of you getting a higher number in the next $x$ rounds is less than 50%, you keep it.

The chances of you not getting a higher roll than $n$ in $x$ rounds is

$(\frac{n}{6})^x$

So if $(\frac{n}{6})^{a-b}\leq\frac{1}{2}$, keep rolling.  Otherwise, keep it.  Note that if you have a 3 or lower you always roll again.

If you want an algorithm to maximize the expected value of the roll you keep, then how is the first variation any different from the original problem?

Hint: Pretend that the number of rounds left is one more than it really is - that way you'll have the same algorithm as the pereson with an extra round.

Try solving the other variations - especially the average one.


logarithms
calculus
integration
calculus computations

Solve the following ordinary differential equation of first order. Note that $ p \equal{} \frac {dy}{dx}$.

(1) $ p \plus{} xy \minus{} x \equal{} 0$

(2) $ xp^2 \minus{} 2yp \minus{} x \equal{} 0$

[hide]
$ \frac {dy}{dx} \plus{} xy \minus{} x \equal{} 0$
$ \frac {dy}{dx} \equal{} x(1 \minus{} y)$
$ \frac {dy}{1\minus{}y} \equal{} x.dx$
$ \minus{}ln(1\minus{}y) \equal{} \frac {1}{2}x^2 \plus{} C$ for a real constant $ C$, then :
$ x^2 \plus{} \minus{}ln(1 \minus{} y) \equal{} C$ for a real constant $ C$.
[/hide]

For 2)
[hide]
$ p \equal{} \frac {y \pm \sqrt {x^2 \plus{} y^2}}{x}$

I get that [hide]$ y \equal{} x \sinh(C \minus{} \ln x)$ [/hide][/hide]

Is this correct?

[quote="Qruni"][hide]
$ \frac {dy}{dx} \plus{} xy \minus{} x \equal{} 0$
$ \frac {dy}{dx} \equal{} x(1 \minus{} y)$
$ (1 \minus{} y)dy \equal{} x.dx$

[/hide][/quote]

I think the last step is incorrect.
You need to divide out the $ (1 \minus{} y)$, not multiply.

[quote="kabi"]1. Again a question of Linear equation.
Find integrating factor. [hide]=e^(x^2/2)[/hide]
Answer [hide]
x^2 + 2ln(y-1) = C.[/hide][/quote]

That should be $ x^2\plus{}2\ln |y\minus{}1|\equal{}C$.

Finally we have $ y\equal{}1\plus{}Ae^{\minus{}\frac{x^2}{2}}$ for Integral Constant $ A$.

[quote="DiscreetFourierTransform"]For 2)
$ p \equal{} \frac {y \pm \sqrt {x^2 \plus{} y^2}}{x}$

I get that $ y \equal{} x \sinh(C \minus{} \ln x)$

Is this correct?[/quote]

That's correct. :)

We can also write the solution as $ y \equal{} \frac {C}{2}x^2 \minus{} \frac {1}{2C},\ y \equal{} \minus{} \frac {1}{2A}x^2 \plus{} \frac {A}{2}$.


Given that $ x^2\minus{}5x \plus{} 8 \equal{} 1$, what is the positive value of $ x^4\minus{}10x^3\plus{} 25x^2\minus{}9$?

hello, from $ x^2\minus{}5x\plus{}8\equal{}1$ we have $ x_1\equal{}\frac{5}{2}\plus{}\frac{1}{2}\sqrt{3}i$
or $ x_2\equal{}\frac{5}{2}\minus{}\frac{1}{2}\sqrt{3}i$, further we get:
$ x_1^4\minus{}10x_1^3\plus{}25x_1^2\minus{}9\equal{}40$
$ x_2^4\minus{}10x_2^3\plus{}25x_2^2\minus{}9\equal{}40$
Sonnhard.

This was on last year's state Mathcounts test, so there should be a way to solve it without imaginary numbers....and there is.  Here's one:
$ x^2 - 5x + 8 = 1 x^2 - 5x + 7 = 0$

Squaring both sides, we have

\begin{align} 0 & = x^4 - 10x^3 + 25x^2 + 14x^2 - 70x + 49 \\
& = (x^4 - 10x^3 + 5x^2) + (14x^2 - 70x + 49) \\
& = (x^4 - 10x^3 + 5x^2) + (14(x^2 - 5x + 7) - 49) \\
& = ( x^4 - 10x^3 + 5x^2) + (14(0) - 49) \\
& = ( x^4 - 10x^3 + 5x^2) - 49
\end{align}

Adding 40 to both sides, we have

$ 40 = x^4 - 10x^3 + 5x^2 - 9$

$ \text{Since this is our desired value, our answer is } \boxed{40}$

note the $ x^2\minus{}5x\equal{}\minus{}7$ SQuaring this means that $ x^4\minus{}10x^3\plus{}25x^2\equal{}49$ Thus our answer is 49-9=40


Who qualified? I was surprisingly close, being only one AIME question away from qualifying by the floor.

EDIT: I realized that this is actually a pointless question because the qualifiers are posted online, but here's a place for those who qualified to brag.

I personally am fine with the fact that I didn't qualify. I wouldn't have done very well on the USAMO anyways. The fact that I was so close indicates that I may have a good shot at making GA ARML.

All ten georgians who made USAMO were ARMLers last year except for the ninth grader.

No, last year only eight Georgians qualified.  10/8 > 505/432; this is a proportional increase!  Yay!  (Okay, maybe it isn't conventionally statistically significant, but I happen to be very fond of my 75% confidence intervals, thank you very much.)

I'm sorry about that, Karthik. :(   Remember there's next year. . . Phillip was eight points below the index last year, and he qualified this year, his senior year.  And some MOPpers from last year didn't qualify this year :(

Anyhow, I don't know who Sagar Patel is, but presumably I will after ARML practice this year.

[quote="solafidefarms"]Exactly as many Georgians made it this year as last. This year 1 9th [same as last year], 2 10th, 2 11th, 5 12th. We'll have such a terrible ARML team next year without them...[/quote]

I disagree. Being the perpetually optimistic sort, I think that we have a tremendous amount of young talent coming up. Yes, our seniors are awesome and will be missed, but we've got the young talent to continue the tradition of strong Georgia teams.

Congrats to all that qualified. That is quite an accomplishment! And as we can tell, it's not assured that once you've qualified, you will again!

Fulton

My index was 24 points from the floor. Maybe I shouldn't have taken Karthik's advice, since I qualified by percentage (I was 1 point away by score). Next year I am definitely taking the AMC 10.

If Kathik's advice was to take the 12 both times, then I probably agree with that. I don't really believe that it's easier to qualify for the USAMO by taking the 10.

Vladimir Smirnov 10 Chamblee Hs Chamblee GA
He makes 11 USAMO qualifiers.
Does anyone know him?

OOoh yay Vova made it!

Vova was on GA Mathcounts the same year as Miles, Santosh, and I. He made ARML in 8th grade, but not 9th. Presumably he'll make it this year :).

OH

i get it now... vladimir = vova

all this time i thought vova was some other random kid

[quote="Karth"]wth? who's Sagar Patel?

Edit:

OH MY GOD

WHAT THE F***

MY INDEX WAS LESS THAN 3 POINTS OFF[/quote]

he goes to brookestone hs, which is in my area. i've seen him once or twice at local tournaments. i think he placed at state in mathcounts last year, but i'm not sure.


Can anyone prove that the reverse of a power of two is never a power of five ?

[quote="Afonso Bandeira"]What do you mean by the reverse of a number?[/quote]

Probably reverse the digits.

Sorry for not being precise. Yes, reverse of digits.


I just did the school round (our coach didn't give it to us), and #12 was kind of ambiguous...

A polyomino is a connected collection of unit squares where the unit squares create a [b]continuous path[/b] form the first square to the last square. Consecutive squares in the path must share a side. The smallest polyomino that has one hole uses 7 unit squares, as shown. How many unit squares are in the smallest polyomino that has two holes? (A hole is a unit square that is not part of the polyomino but is surrounded on all four sides by squares that are part of the polyomino.)

Using the question's definition, the answer should be 13...
Thankfully, I put 11 instead based on the conventional definition of polyomino and that's the correct answer.

Thoughts?

...?
Why?
Isn't it 13 by their definition?

Oh....
Position the holes diagonally....

Everyone just ignore this whole topic please.


Can someone tel me how to figure out this problem?

I am supposed to find the illegal variables in this statement: [url=http://imageshack.us][img]http://img140.imageshack.us/img140/7829/funkcs4.jpg[/img][/url]

What do you mean by "illegal"?  :maybe:
That expression simplifies, HINT factor.

Illegal variables??

Well, if it helps...

[hide]That equals $\frac{(c-5)(c+2)}{(c+7)(c-2)}\cdot\frac{(c-2)(c+1)}{(c-5)(c+3)}=\frac{(c+2)(c+1)}{(c+7)(c+3)}$[/hide]

which doesnt really help, since we still don't know what illegal variables are...

[quote="Nawahd Werdna"]Well, if you mean restricted values, then it is simply (using Walk Around The River's factorization) $c \not=-7, 2, 5,-3$ This is because the denominator of a rational expression cannot equal 0, as that would mean that it is undefined!!![/quote]

Good call.  I think that's right, as long as I factored correctly  :|

[quote="sunoco"]Its illegal values not variables. Sorry.[/quote]

In that case, just look at the values that make the denominator equal to $0$.


Let $a$, $b$, and $n$ be positive integers with $\gcd (a, b)=1$. Without using Dirichlet's theorem, show that there are infinitely many $k \in \mathbb{N}$ such that $\gcd(ak+b, n)=1$.

Let $ \mathbb{P}= \{p \in \mathbb{N}: p \mbox{ is prime}\}$ and $ \mathcal{Q}= \{p \in \mathbb{P}: p \mid n\;\wedge\;p \nmid b\}$. Then letting $ k = q \cdot \prod_{p \in \mathcal{Q}}p$ yields $ \gcd(ak+b, n) = 1$, for each $ q \in \mathbb{P}$ such that $ q > n$.

[u]Consequence [/u]
There exist infinite prime number.

[quote="s.tringali"]Let $ \mathbb{P} \equal{} \{p \in \mathbb{N}: p \mbox{ is prime}\}$ and $ \mathcal{Q} \equal{} \{p \in \mathbb{P}: p \mid n\;\wedge\;p \nmid b\}$. Then letting $ k \equal{} q \cdot \prod_{p \in \mathcal{Q}}p$ yields $ \gcd(ak \plus{} b, n) \equal{} 1$, for each $ q \in \mathbb{P}$ such that $ q > n$.[/quote]I don't understand. What if $ \mathcal Q$ is empty, for example if $ n|b$? What if $ \mathcal Q$ is infinite? Then $ \prod_{p \in \mathcal{Q}}p$ is not a number.

I am also.
Here is my solution:
Enough  to prove exist because if $ \gcd(ak + b,n) = 1$ then $ \gcd(a(k + nt) + b,m) = 1$
Now we prove this :
$ n = \prod_{i = 1}^rp_i^{a_i}$ where $ a_i > 0$
Now place each of them to one of set.
$ A = \{p\in P: p|\gcd(b,n)\}$
$ B = \{p\in P: p|n,\gcd(p,b) = 1\}$
Because $ \gcd(a,b) = 1$ so $ p\not|a,\forall p\in A$
Now we consider the system of congruent:
$ k\equiv 1 (\mod\prod_{p\in A}p)$
$ k\equiv 0 (\mod \prod _{p\in B})$
This equation has solution (Chinese remainder theorem).
Easy to check that $ \gcd(ak + b,n) = 1$

It seems like this should have a simple arithmetic solution, since it can be rephrased as:

Let a, b, n, x and y be integers with $ ax+by=1$ and $ n\ne 0$. Show that there exists integers z, k and w such that $ z(ak+b)+wn=1$.

The closest I could come does use the following lemma.

[b]Lemma[/b]: For every pair of positive integers $ n, b$, there exists a representation $ n=n_1n_2$ where $ n_2$ is coprime to $ b$ and $ n_1$ is a factor of a power of $ b$.

[b]Proof[/b]: Let $ t_0=n$, and define sequences $ t_i, u_i$ by $ u_i=\gcd(t_i,b)$, $ t_{i+1}=\frac{t_i}{u_i}$. Since $ u_i\ge 1$, $ t_{i+1}\le t_i$ and the positive integer sequence eventually becomes constant. Suppose $ t_k=t_{k+1}$. Then set $ n_2=t_k$ and $ n_1=u_1u_2\ldots u_{k-1}$. Clearly $ n=n_2$, $ t_k$ is coprime to $ b$, and since each $ u_i$ is a factor of $ b$, $ n_1$ is a factor of $ b^{k-1}$.
[b]QED[/b]

It is not hard to see that this representation is unique, but we won't use that.

Given our n, a, b from the problem, we know that $ \gcd(a,b)=1$, which means that $ \gcd(b,a+b)=1$.  From the above lemma, we can write $ n=n_1n_2$ where $ n_2$ is coprime to $ b$ and $ n_1$ is a factor of a power of $ b$. Since $ n_1$ is a factor of a power of $ b$, it is coprime to all things coprime to $ b$, in particular to $ n_2$ and to $ a+b$.

Thus we have the existence of integers $ x_i, y_i$ such that $ x_1n_1+y_1n_2=1$, $ x_2n_1+y_2(a+b)=1$ and $ x_3n_2+y_3b=1$.

Then: $ y_3(b+y_1n_2a)=y_3b+y_3y_1n_2a=1-x_3n_2+y_3y_1n_2a=1+(y_3y_1a-x_3)n_2$, so $ b+y_1n_2a$ is coprime to $ n_2$.

Similarly, $ y_2(b+y_1n_2a)=y_2(b+(1-x_1n_1)a)=y_2(b+a)-y_2x_1n_1a=1-x_2n_1-y_2x_1n_1a=1-(x_2+y_2x_1a)n_1$,
so $ b+y_1n_2a$ is coprime to $ n_1$.

Thus $ b+y_1n_2a$ is coprime to $ n_1n_2=n$.

Luke
See my puzzle blog at http://bozzball.blogspot.com/[/b]


[quote="rnwang2"]Consider a circle with radius 6. Show that the geometric mean of the area of the inscribed equilateral triangle and the area of the circumscribed equilateral triangle is the area of the inscribed regular hexagon.[/quote]

[hide]Let's start with the inscribed regular hexagon.  That has an area of $\frac{3(6)^{2}\sqrt3}{2}=54\sqrt3$ from some basic formula that I don't want to prove.

The area of the inscribed equilateral triangle is $3\cdot \frac{3\cdot 6\sqrt3}{2}=27\sqrt3$ if you draw the radius and let it be the hypotenuse of a 30-60-90 right triangle, find the area of that triangle, and multiply that by 3 (the number of these triangles).

Finally, the area of the circumscribed triangle is $3\cdot \frac{6\cdot 12\sqrt3}{2}=108\sqrt3$ by following the same steps as the inscribed one.

Now, we have to show that the geometric mean of $108\sqrt3$ and $27\sqrt3$ is $54\sqrt3$.
$\sqrt{108\sqrt3\cdot 27\sqrt3}=\sqrt{3\cdot 27^{2}\cdot 2^{2}}=27\cdot2\cdot \sqrt3=54\sqrt3$.  Since LHS=RHS, the proof is complete.

I think that was unnecessarily long.  How can I shorten it?[/hide]

I believe you could set the area of the equilateral triangle formed by two radii and a chord to x.

Let A be the area of the inscribed triangle.
Area of the circumscribed triangle is 4A
Area of the hexagon is 2A
$\sqrt{4A*A}=2A$


In Complex analysis, there are lots of questions asking us to prove if an entire function satisfying, for e.g., $ \Im f(z) > \Re f(z)$, then $ f$ is a constant. Usually, we construct a entire function $ g$ involving $ f$ and then consider the following function $ e^{g(z)}$. By assumption, we need to prove $ e^{g(z)}$ is bounded and then by means of the Liouville's theorem, $ g$ must be a constant and so is $ f$.

What I am asking is, for the above example, clearly $ f(z)$ does not attain the following two points $ 2\plus{}i$ and $ 3\plus{}i$, therefore by the Little Picard Theorem, $ f$ must be a constant. Is this correct?

If we assume $ \Im^2 f(z) > \Re^2 f(z)$, then $ f(z)$ also does not attain the following two points $ 2\plus{}i$ and $ 3\plus{}i$, and thus $ f$ is a constant.

Thank you.


Find the points on the ellipsoid $ x^2 \plus{} 2y^2 \plus{} z^2 \equal{} 7$ where the tangent plane is parallel to the plane $ \minus{}2x \plus{} 2y \plus{} z \equal{} 0$

I know that this had something to do with the gradients, and maybe directional derivative... help please?

Let $ f(x,y)$ be a differentiable function at $ (x_{0},y_{0})$.  Then the tangent plane to the surface $ z\equal{}f(x,y)$ at the point $ (x_{0},y_{0},z_{0})$ is
$ z\minus{}z_{0}\equal{}\frac{\partial f}{\partial x}(x\minus{}x_{0})\plus{}\frac{\partial f}{\partial y}(y\minus{}y_{0})$.

Can you generalize this?


Sally has a dozen eggs.  She wants to paint one of the purple, one  of then pink, one of them green, and one of them yellow.  In how many ways can she do this?

How come this problem has to use permutation instead of combination?

[hide="method one"]
There are 12 choices for the first, 11 for the second, 10 for the third, and 9 for the fourth, so $12*11*10*9=11880$[/hide]
[hide="method two"]
$_{12}P_{4}=11880$[/hide]

[quote="randomdragoon"][quote="anyone"][hide="method one"]
There are 12 choices for the first, 11 for the second, and 10 for the third, so $12*11*10=1320$[/hide]
[hide="method two"]
$_{12}P_{3}=1320$[/hide][/quote]
Right idea, except she's painting 4 eggs  :wink:[/quote]Oops, guess i can't count  :blush: I'll fix them. Thanks for correcting me

the title...... :P
i think u wanna know how to solve this problem by using permutation,right?
anyway...if Sally paints 4 eggs at the same time, it will be different..lol

[quote="xpmath"]There are different colors, so... they will be different. :rotfl:  :roll:[/quote]

Huh? Anyways, you just have to find out how many ways she can paint four eggs and multiply that by how many compinations of 4 eggs can be derived from 12.

[quote="xpmath"]It's 12*11*10*9

I was explaining the reason it is permutations, not combinations[/quote]

Ah, I see. That comes out to be...
11880

I didn't use a calculator, I swear!  :rotfl:


This fits all requirements for avatars. :)

I did not ask for an avatar. Funny how you made one based off my old avatar anyways.

It was made for
'must mock dragon'
purposes.

I played with GIMP,
this is probably a 'CLICK TO PLAY ANIMATION' thing.