Sums of pairs in a sequence

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

tenniskidperson3

2376 posts

tenniskidperson3

#1 h Apr 29, 2010, 3:41 PM • 8 Y

Y by itslumi, HWenslawski, mathmax12, Adventure10, Mango247, Spiritpalm, ItsBesi, DEKT

Let $n > 1$ be an integer. Find, with proof, all sequences $x_1 , x_2 , \ldots , x_{n-1}$ of positive integers with the following three properties:
(a). $x_1 < x_2 < \cdots < x_{n-1}$ ;
(b). $x_i + x_{n-i} = 2n$ for all $i = 1, 2, \ldots , n - 1$ ;
(c). given any two indices $i$ and $j$ (not necessarily distinct) for which $x_i + x_j < 2n$ , there is an index $k$ such that $x_i + x_j = x_k$ .

This post has been edited 1 time. Last edited by tenniskidperson3, Apr 30, 2010, 3:43 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

quadraticfanatic

23 posts

quadraticfanatic

#2 h Apr 29, 2010, 7:26 PM • 6 Y

Y by HWenslawski, Adventure10, GreenBanana666, Mango247, DEKT, and 1 other user

My solution, right or wrong!

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

This post has been edited 1 time. Last edited by quadraticfanatic, Apr 29, 2010, 10:25 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Fermat1601

31 posts

Fermat1601

#3 h Apr 29, 2010, 7:54 PM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Goldey

333 posts

Goldey

#4 h Apr 29, 2010, 8:08 PM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SnowEverywhere

801 posts

SnowEverywhere

#5 h Apr 29, 2010, 8:37 PM • 3 Y

Y by Adventure10, Mango247, and 1 other user

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

quadraticfanatic

23 posts

quadraticfanatic

#6 h Apr 29, 2010, 10:26 PM • 1 Y

Y by Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6874 posts

v_Enhance

#7 h Apr 30, 2010, 1:49 AM • 12 Y

Y by electrobrain, samuel, Wizard_32, myh2910, vvluo, mijail, HamstPan38825, itslumi, math31415926535, Adventure10, Mango247, and 1 other user

So we actually didn't need the fact the sequence was positive integers?

My proof was really similar to quadraticfanatic's:
Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

BarbieRocks

1102 posts

BarbieRocks

#8 h Apr 30, 2010, 2:14 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

va2010

1276 posts

va2010

#9 h Apr 21, 2013, 3:09 PM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6874 posts

v_Enhance

#10 h Apr 21, 2013, 3:14 PM • 3 Y

Y by HamstPan38825, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

va2010

1276 posts

va2010

#11 h Apr 21, 2013, 3:18 PM • 1 Y

Y by Adventure10

Caught my mistake. Thank you

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

vanu1996

607 posts

vanu1996

#12 h Jan 11, 2014, 6:33 AM • 1 Y

Y by Adventure10

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathdoctor

226 posts

mathdoctor

#13 h Jan 11, 2014, 8:49 PM • 3 Y

Y by electrobrain, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Wave-Particle

3690 posts

Wave-Particle

#14 h Jul 9, 2015, 8:00 PM • 3 Y

Y by electrobrain, Adventure10, Mango247

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

This post has been edited 1 time. Last edited by Wave-Particle, Jul 9, 2015, 8:01 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

electrobrain

101 posts

electrobrain

#15 h Jul 9, 2015, 8:10 PM • 1 Y

Y by Adventure10

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

kamatadu

477 posts

kamatadu

#44 h Aug 15, 2023, 9:13 AM • 1 Y

Y by HoripodoKrishno

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

trk08

614 posts

trk08

#45 h Dec 6, 2023, 4:40 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Shreyasharma

678 posts

Shreyasharma

#46 h Dec 6, 2023, 5:37 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

joshualiu315

2513 posts

joshualiu315

#47 h Dec 22, 2023, 8:50 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dolphinday

1320 posts

dolphinday

#48 h Jan 6, 2024, 11:57 AM

Y by

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

This post has been edited 1 time. Last edited by dolphinday, Jan 6, 2024, 11:58 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

794 posts

shendrew7

#49 h Jan 19, 2024, 3:25 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

peppapig_

280 posts

peppapig_

#50 h Feb 24, 2024, 3:32 AM

Y by

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.

This post has been edited 1 time. Last edited by peppapig_, Feb 24, 2024, 3:33 AM
Reason: Missed a $

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

two_steps

102 posts

two_steps

#51 h Mar 9, 2024, 6:40 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ItsBesi

142 posts

ItsBesi

#52 h Sep 26, 2024, 1:11 PM

Y by

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}$
Click to reveal hidden text

Case 2. $n-\text{is odd}$
Click to reveal hidden text

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

This post has been edited 1 time. Last edited by ItsBesi, Sep 26, 2024, 1:12 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Maximilian113

549 posts

Maximilian113

#53 h Jan 21, 2025, 4:34 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

eg4334

631 posts

eg4334

#54 h Jan 22, 2025, 5:19 AM

Y by

Goofy problem.

The conditions imply that the sums, in increasing order, $\{ x_1+x_1, x_1+x_2, \dots x_1+x_{n-1} \}$ must biject to $x_2, x_3, \dots x_{n-1}$ . Therefore, $x_1+x_1=x_2$ , $x_1+x_2=x_3$ , and likewise. Then its not hard to see that $x_i = i x_1$ and from the second condition we obtain $x_1=2$ . Therefore the only sequence is the increasing one of evens.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ihatecombin

58 posts

Ihatecombin

#55 h Feb 20, 2025, 12:14 PM

Y by

Notice that $a_1,a_1 + a_1, a_1 + a_2, \dots. a_1 +a_{n-2}$ are all different,
by an easy induction we obtain the only sequence that works is $a_i = 2i$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bjump

999 posts

bjump

#56 h Feb 24, 2025, 6:52 PM • 2 Y

Y by KenWuMath, imagien_bad

Solution from over a year ago ...

The answer is $x_{k}= 2n$
Note that
$x_1 + x_{n-1}=2n$ $x_{1}+ x_{n-2} = x_{n-1}$ $\vdots$ $x_{1}+x_{1}=x_{2}$ I claim that $x_{n} = nx_1$ we will prove this via induction with a trivial base case of $n=1$ . Assume that this is true for $1 \le n \le k$ then $x_{k+1} = x_{k}+ x_1=kx_1+x_1= (k+1)x_1$ . Now by condition (b) $x_i+x_{n-i} = 2n \iff (n-i+i)x_1=2n \iff x_1=2$ . Therefore $x_k = k x_1 = 2k$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

de-Kirschbaum

196 posts

de-Kirschbaum

#57 h Mar 6, 2025, 4:33 AM

Y by

Note that $x_{n-2}<x_1+x_{n-2}<x_2+x_{n-2}=2n$ so by property 3 we must have $x_{n-2}+x_1=x_{n-1}$ . By a similar reasoning this works for all $x_i$ so we have that $x_1, x_2,\ldots, x_{n-1}$ is an arithmetic sequence with common difference $x_1$ , and by property 1 we must have $nx_1=2n \implies x_1=2$ so the only sequence that works is $x_i=2i$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Marcus_Zhang

979 posts

Marcus_Zhang

#58 h Apr 6, 2025, 4:13 PM

Y by

Storage

Z K Y