This is probably the least elegant way, but it's much better than nothing!

You can also start from the end: a(1)+a(n-2)=a(n-1), etc. So a is 2,4,6,...,(2n-2).

Don't forget the second part of the solution- You have to show that all sequences 2,4,6,...2(n-1) meet all of the criteria, not just that any sequence that meets it must be of this form

I had a different proof (I hope it works). Here is an outline. Let $S=({x_1, x_2, \dots, x_{n-1}})$ 1) Prove that for all $j>i$, $(x_j - x_i) \in S$. 2) Now consider the sum $2n>x_{n-1} = (x_{n-1} - x_{n-1}) + (x_{n-2} - x_{n-3}) + \dots + (x_2 - x_1) + x_1$. 3) Pigeonhole on the above shows that for some $m$ either $x_m - x_{m-1}$ or $x_1$ is $1$ or $2$. 4) By (1) this is in $S$. 5) Induct on the case that it was $1$ and induct that it was $2$. 6) This shows either $S=({1,2,3, \dots 2n-1})$ or $S=({2,4,6, \dots, 2n-2})$. 7) In the first case, $|S| = 2n-1 > n-1$ which is a contradiction. Hence the only solution is $S={2,4,6, \dots, 2n-2}$.

Goldey wrote: Don't forget the second part of the solution- You have to show that all sequences 2,4,6,...2(n-1) meet all of the criteria, not just that any sequence that meets it must be of this form Right. Should be fixed now.

So we actually didn't need the fact the sequence was positive integers? My proof was really similar to quadraticfanatic's:

I hope I get a point for just doing the if part...

Would it be possible to see that $a_1$ must equal $2$ and then show that it constitutes the rest?

Assuming you mean $x_1$, what do you mean "constitutes the rest"? And you might want to explain how you want to get that $x_1=2$, since this does not seem trivial.

Caught my mistake. Thank you

SnowEverywhere wrote: I had a different proof (I hope it works). Here is an outline. Let $S=({x_1, x_2, \dots, x_{n-1}})$ 1) Prove that for all $j>i$, $(x_j - x_i) \in S$. 2) Now consider the sum $2n>x_{n-1} = (x_{n-1} - x_{n-1}) + (x_{n-2} - x_{n-3}) + \dots + (x_2 - x_1) + x_1$. 3) Pigeonhole on the above shows that for some $m$ either $x_m - x_{m-1}$ or $x_1$ is $1$ or $2$. 4) By (1) this is in $S$. 5) Induct on the case that it was $1$ and induct that it was $2$. 6) This shows either $S=({1,2,3, \dots 2n-1})$ or $S=({2,4,6, \dots, 2n-2})$. 7) In the first case, $|S| = 2n-1 > n-1$ which is a contradiction. Hence the only solution is $S={2,4,6, \dots, 2n-2}$. this is exactly my solution,.good soln @snoweverywhere

Better organized proof: Consider the sequence: $x_1 + x_1 < x_1 + x_2 <... <x_1 + x_{n-2}<x_1 + x_{n-1}=2n$. They are different terms of the original sequence except the last term. Because all the terms are greater than $x_1$, we should have $x_1 + x_1 =x_2$ and $x_1 + x_i =x_{i+1}$ for $1\leq i \leq n-2$. This implies that the original sequence is an arithmetic sequence with initial term $x_1$ and common difference $x_1$. $x_1+x_{n-1} =2n$ will imply $x_1=2$.

We know $x_1+x_{n-1}=2n$. Because $x_{n-2}<x_{n-1}$, we have that $x_1+x_{n-2}=x_{n-1}$ because of property (c). Using similar logic we can conclude that $x_1+x_{n-3}=x_{n-2}$. We can continue this on until we have $x_1+x_2=x_3$. We subtract the first 2 equations we got to get that $x_{n-2}-x_{n-3}=x_{n-1}-x_{n-2}$. We can do this for all the equations we have to conclude that the sequence $x_1, x_2,..., x_{n-1}$ is an arithmetic sequence. But this does not guarantee that $x_1$ is a part of the arithmetic sequence, so we use the fact that $x_{n-1}+x_1=x_{n-2}+x_2$. This means that $x_2-x_1=x_{n-1}-x_{n-2}$ which does mean that $x_1$ is a part of the arithmetic sequence. Let the common difference of this arithmetic sequence be $d$. We use the equation $x_1+x_{n-2}=x_{n-1}$ to get the fact that $x_1=d$. This means our sequence is of the form $x_1, 2x_1, 3x_1,..., (n-1)x_1$. Now we use the equation $x_1+x_{n-1}=2n$ which gives $x_1=2$. So the only sequence that works is $2,4,6....2n-2$.

How do you know that x_1+x_n-2=x_n-1? Why can't it be x_n-3?

electrobrain wrote: How do you know that x_1+x_n-2=x_n-1? Why can't it be x_n-3? They are positive integers, and we are given that $x_{n-1}$ is greater than $x_{n-2}$ while $x_{n-3}$ is less than $x_{n-2}$. Rest should be self explanatory.

I was asking why can the x_n-2 not be x_n-3 but I got it now. Thank you for replynig.

Is this good?

Let $x_1=k$. Furthermore, let $X=(x_1, x_2,\dots x_n-1)$. It follows that $x_{n-1}=2n-k$. Now for all $m$, $1\leq m<n-1$, we have, by $(c)$ that $x_m+k\in X$. We must have that $x_{n-2}+k=x_{n-1}$. In a similar fashion, we can show that $x_{n-t}=n-tk$. Hence, $X=(k,2k,\dots (n-1)k)$. Since $k+(n-1)k=nk=2n$, we must have that $k=2$. Checking the conditions: (a) Yes, since $x_i<x_i+2$ (b) Yes since $2t+2(n-t)=2t$ (c) Yes, because $X$ is an arithmetic sequence Hence, $X=(2,4,8\dots 2n-2)$. $\square$

Just note that \[x_1+x_{n-2}=x_{n-1}\]\[x_1+x_{n-3}=x_{n-2}\]\[\vdots\]\[x_1+x_2=x_3\]\[x_1+x_1=x_2\]so the numbers form an arithmetic sequence $\{2,4,\dots,2n-2\}$. $\blacksquare$

v_Enhance wrote: So we actually didn't need the fact the sequence was positive integers? My proof was really similar to quadraticfanatic's:

Wow '0'

hmmmm... I just looked at tons of arthimetic sequences and found that 2,4,6,8,10,12,14,16.....2n-2 works

Solved with huashiliao2020.

A very nice inductive question. The whole question is centred around $a_{n-i}-a_{n-1-i}=a_1$. This can be proven inductively by using pigeonhole principle and strictly increasing condition on the last condition. Then we have $a_i=ki$ for some k and solving get $k=2$. The other direction is much easier. Full proof here https://infinityintegral.substack.com/p/usajmo-2010-contest-review

I claim that the only sequence is $x_i=2i$. It is easy to see that such a sequence suffices the condition. Now we prove that this is the only one. Firstly, for some $n$, we prove that $x_i=i\cdot x_1$. We proceed using induction. The base case $x_1=1\cdot x_1=x_1$ is clearly true. Now assume the induction hypothesis for some $k-1<n-1$, and we prove it for $k$. Consider the following sequence.\[x_1+x_{n-k},x_2+x_{n-k},\ldots,x_{k-1}+x_{n-k}.\]Note that this sequence has $k-1$ terms in it. Firstly, we have that $x_k+x_{n-k}=2n$ and the fact that $x_i<x_k$ for all $1\le i\le k-1$. So this gives us that $x_i+x_{n-k}<x_k+x_{n-k}=2n$ which means that we will get some $x_j$ for each $i$ such that $x_j=x_i+x_{n-k}$. Now clearly from the increasing condition of the sequence, we get that $j\ge n-k+1$. So each $x_j$ belongs to the following sequence.\[x_{n-(k-1)},x_{n-(k)},\ldots,x_{n-1}.\]So note that this sequence also has $k-1$ terms. So this forces that the equality occurs in each of the values of $x_j$ from both the sequences. So this gives that $x_1+x_{n-k}=x_{n-(k-1)}$, which further gives that $x_1+(2n - x_{n-(n-k)})=2n - x_{n-((n-k+1)}\implies x_1 - x_k = -x_{k-1}\implies x_1+x_{k-1}=x_k$. Now using our induction hypothesis, we get that $x_{k-1}=(k-1)x_1$ which finally gives $x_k=k\cdot x_1$. Now then, we finally get that $x_{n-1}=(n-1)x_1$. Putting this into $x_1+x_{n-1}=2n$, we get that $x_1=2$ and we are done.

We claim the only possible sequence is if $x_i=2i$. This sequence clearly works, and we now prove it is the only one.// First of all, consider $x_1+x_{n-2}$. As $x_1>0$, it has to be more than $x_{n-2}$, which implies that it must be $x_{n-1}$. As each of the following sums are in decreasing order, from top to bottom: \[x_1+x_{n-2}\]\[x_1+x_{n-3}\]\[\dots\]\[x_1+x_1,\]and there are $n-2$ of them, we can say that: \[x_1+x_{n-2}=x_{n-1}\]\[x_1+x_{n-3}=x_{n-2}\]\[\dots\]\[x_1+x_1=x_2.\] Therefore, it is easy to see that $x_{i}=ix_1$. Therefore, $nx_1=2n$, or $x_1=2$, as desired.

Note that we are given, $x_1 < x_2 < \dots < x_{n-1}$ $x_1 + x_{n-1} = x_2 + x_{n-2} = x_3 + x_{n-3} = \dots = 2n$ From the final condition we find $x_1 + x_2$, $x_1 + x_3$, $\dots$, $x_1+x_{n-2}$ all belong to $(x_i)$. Clearly $x_1 + x_{n-2} = x_{n-1}$ or that $$x_{n-2} = x_{n-1} - x_1$$Then $x_1 + x_{n-3} = x_{n-2}$, which in turn gives, $$x_{n-3} = x_{n-1} - 2x_1$$and so on. Inducting downwards we find $$x_{n-1-k} = x_{n-1} - kx_1$$However then $x_1 = x_{n-1} - (n-2)x_1$ which gives $nx_1 = 2n$, or $x_1 = 2$. Now from our induction we find the sequence of $(x_i)$ are simply the even integers from $2$ to $2n - 2$.

Consider the sequence $x_1+x_1, x_1+x_2, \dots, x_1+x_{n-1} = 2n$. Each of the $n-2$ terms before $2n$ are obviously less than $2n$, and they must be part of the sequence $x_1, x_2, \dots, x_{n-1}$. This means we must necessarily have \begin{align*} x_1+x_1 &= x_2, \\ x_1+x_2 &= x_3, \\ \dots &\phantom{=} \\ x_1+x_{n-2} &= x_{n-1}. \end{align*} Hence, $x_k = kx_1$, and plugging this in gives \[x_1+(n-1)x_1=2n \implies x_1=2.\] Thus, $x_n = \boxed{2n}$, which is easily checked to be true.

We find that \[x_1 < x_1 + x_1 < x_1 + x_2 \dots x_1 + x_{n-2}\]are all in $x_i$, due to $(c)$, and since there are $n-1$ terms, this sequence must be equivalent to \[x_1, x_2, \dots, x_{n-1}\]So, we can rewrite each term as $ix_1$. $\newline$ \[x_1 + x_{n-1} = 2n\]can be rewritten as \[x_1 + (n-1)x_1 = 2n \implies nx_1 = 2n \implies x_1 = 2\]Due to the fact that each term is equal to $ix_1$, this sequence is just $x_i = 2i$.

Due to the third condition, we know the sequence $x_2, x_3, \ldots, x_{n-1}, 2n$ must correspond with the terms of \[x_1+x_1 < x_1+x_2 < \ldots < x_1+x_{n-2} < x_1+x_{n-1} = 2n.\] Thus we know $x_k = k \cdot x_1$ for $1 \leq k \leq n-1$, from which the second condition tells us our only solution is $\boxed{x_i = 2i}$. $\blacksquare$

I goofed last time; I claim that the only possible sequence is $2$, $4$, $6$, $\dots$, $2n-2$. Note that by problem conditions, we have that \[x_1+x_{n-1}=2n,\]but we also have that \[x_1+x_{n-2}=x_j,\]for some integer $j$. However, since $x_1<x_2<\dots<x_{n-1}$, we must have that $x_{n-2}=x_{n-1}-x_1$. Similarly, we get that \[x_k=x_1+x_{n-3}<x_1+x_{n-2}=x_{n-1},\]meaning that $k=n-2$. Continuing this, we get that our sequence must be $x_1$, $2x_1$, $\dots$, $(n-1)x_1$, and since $x_1+x_{n-1}=2n$, we also get that $x_1$ must be equal to $2$. Therefore the only possible sequence is $2$, $4$, $6$, $\dots$, $2n-2$, which indeed works, finishing the problem.

is this correct? why is my solution different from everyone else lol For any two terms $x_i < x_j$, notice that the following terms are also in the sequence \[x_i, x_j \rightarrow 2n-x_j \rightarrow 2n-x_j+x_i \rightarrow x_j-x_i\]This is essentially a stronger version of the converse of condition 3. From here, note that we may prove that each element is a multiple of $x_1$ by induction. The only possible sequences are now $1,2,\dots, n-1$ and $2,4,\dots,2(n-1)$. The first sequence doesn't work, while the second one does.

My solution is different from others so did I fakesolve? We separate the problem into $2$ cases which both are analogous. Case 1. $n-\text{is even}$

Case 2. $n-\text{is odd}$

Since in both cases we have: $\{x_1,x_{k_1}, \dots , x_{k_{n-2}} \}=\{x_1,x_2, \dots, x_{n-1} \}$ we get: $x_1=x_1 , x_2=x_{k_1} , x_3=x_{k-2} , \dots , x_{n-1}=x_{k_{n-2}}$ So $x_1+x_1=x_{k_1}=x_2 \implies x_1+x_1=x_2 \implies x_2=2 \cdot x_1$ $x_1+x_2=x_{k_2}=x_3 \implies x_1+x_2=x_3 \implies x_3=x_1+x_2=x_1 + 2 \cdot x_1=3 \cdot x_1 \implies x_3=3 \cdot x_1$ $x_2+x_2=x_{k_3}=x_4 \implies x_2+x_2=x_4 \implies x_4=2 \cdot x_2=2 \cdot 2 \cdot x_1= 4 \cdot x_1 \implies x_4=4 \cdot x_1$ $x_2+x_3=x_{k_4}=x_5 \implies x_2+x_3=x_5 \implies x_5=x_2+x_3=2 \cdot x_1 + 3 \cdot x_1 =5 \cdot x_1 \implies x_5= 5 \cdot x_1$ $x_3+x_3=x_{k_5}=x_6 \implies x_3+x_3=x_6\implies x_6=x_3+x_3=3 \cdot x_1 + 3 \cdot x_1=6 \cdot x_1 \implies x_6=6 \cdot x_1$ $\dots$ $x_{\frac{n}{2}-1}+x_{\frac{n}{2}-1}=x_{k_{n-3}}=x_{n-2} \implies x_{\frac{n}{2}-1}+x_{\frac{n}{2}-1}=x_{n-2} \implies x_{n-2}= x_{\frac{n}{2}-1}+x_{\frac{n}{2}-1}=2 \cdot x_{\frac{n}{2}-1} = 2 \cdot (\frac{n}{2}-1) \cdot x_1=(n-2) \cdot x_1 \implies x_{n-2}=(n-2) \cdot x_1$ Now again by $(b) \implies$ $x_2+x_{n-2}=2n \implies 2 \cdot x_1 + (n-2) \cdot x_1 =2n \implies n \cdot x_1=2n \implies x_1=2 So x_1=2, x_2=2 \cdot x_1=2 \cdot 2=4 , x_3=3 \cdot x_1= 3 \cdot 2=6 , \dots x_{n-1}=(n-1) \cdot x_1=(n-1) \cdot 2=2n-2$ Hence $(x_1,x_2, \dots , x_{n-1}=(2,4, \dots ,2n-2)$

Observe that property (b) is equivalent to $$i+j < n \iff x_i+x_j < 2n.$$Therefore, $$x_1 < x_1+x_1 < x_1+x_2 < \cdots < x_1+x_{n-2} < 2n.$$However, each of these sums are some $x_k$ but since $$x_2<x_3<\cdots < x_{n-1} < 2n$$it follows that $x_1+x_k=x_{k+1}$ for each $k=1, 2, \dots, n-2.$ Thus $x_2=2x_1, x_3=3x_1,$ etc. This yields $2n=x_1+x_{n-1}=x_1+(n-1)x_1 \implies x_1=2,$ and it follows that the sequence is $$2, 4, 6, \cdots, 2n-2.$$It is easy to show that this works.