Maths Olympiad Prep

Library / /33 of 34

Algebra Difficulty 7.5 National olympiad, round 2 Find the answer

Let n>1n > 1 be an integer. Find, with proof, all sequences x1,x2,,xn1x_1, x_2, \ldots, x_{n-1} of positive integers with the following
three properties:
(a). ; (b). for all ; (c). given any two indices and (not necessarily distinct)
for which , there is an index such
that .

A number or a short expression. Spacing and $ signs are ignored.

Solution

The sequence is 2,4,6,,2n22, 4, 6, \ldots, 2n-2 .
Proof 1
We will prove that any sequence x1,,xn1x_1, \ldots, x_{n-1} , that satisfies
the given conditions, is an
arithmetic progression with x1x_1 as both the first term and the
increment. Once this is proved, condition (b) implies that x1+xn1=x1+(n1)x1=nx1=2nx_1 + x_{n-1} = x_1 + (n-1)x_1 = nx_1 = 2n . Therefore x1=2x_1 = 2 ,
and the sequence is just the even numbers from 22 to 2n22n-2 . The
sequence of successive even numbers clearly satisfies all three conditions,
and we are done.
First a degenerate case.
If n=2n = 2 , there is only one element x1x_1 , and condition (b) gives x1+x1=4x_1 + x_1 = 4 or x1=2x_1 = 2 . Conditions (a) and (c) are vacuously
true.
Otherwise, for n>2n > 2 , we will prove by induction on mm that the
difference xnmxn1m=x1x_{n-m} - x_{n-1-m} = x_1 for all m[1,n2]m \in [1, n-2] ,
which makes all the differences xn1xn2==x2x1=x1x_{n-1} - x_{n-2} = \ldots = x_2 - x_1 = x_1 , i.e. the sequence is an arithmetic progression with x1x_1 as the first term and increment as promised.
So first the m=1m=1 case. With n>2n > 2 , xn2x_{n-2} exists and is less
than xn1x_{n-1} by condition (a). Now since by condition (b) x1+xn1=2nx_1 + x_{n-1} = 2n , we conclude that x1+xn2<2nx_1 + x_{n-2} < 2n , and therefore
by condition (c) x1+xn2=xkx_1 + x_{n-2} = x_k for some kk . Now, since x1>0x_1 > 0 , xk>xn2x_k > x_{n-2} and can only be xn1x_{n-1} . So x1+xn2=xn1x_1 + x_{n-2} = x_{n-1} .
Now for the induction step on all values of mm .
Suppose we have shown that for all imi \le m , x1+xn1i=xnix_1 + x_{n-1-i} = x_{n-i} . If m=n2m = n-2 we are done, otherwise m<n2m < n-2 , and by
condition (c) x1+xn2m=xkx_1 + x_{n-2-m} = x_k for some kk . This xkx_k is
larger than xn2mx_{n-2-m} , but smaller than x1+xn1m=xnmx_1 + x_{n-1-m} = x_{n-m} by the inductive hypothesis. It then follows that x1+xn2m=xn1mx_1 + x_{n-2-m} = x_{n-1-m} , the only element of the sequence between xn2mx_{n-2-m} and xnmx_{n-m} . This establishes the result for i=m+1i=m+1 .
So, by induction x1+xn1m=xnmx_1 + x_{n-1-m} = x_{n-m} for all m[1,n2]m \in [1, n-2] ,
which completes the proof.
Proof 2
Let S={x1,x2,...,xn1}S=\{x_1,x_2,...,x_{n-1}\} .
Notice that x1<x1+x1<x1+x2<<x1+xn2<2n.x_1<x_1+x_1<x_1+x_2<\dots <x_1+x_{n-2}<2n. Then by condition (c), we must have x1,x1+x1,...,x1+xn2Sx_1,x_1+x_1,...,x_1+x_{n-2}\in S . This implies that x1=x1,x1+x1=x2,...,x1+xn2=xn1x_1=x_1,x_1+x_1=x_2,...,x_1+x_{n-2}=x_{n-1} , or that xk=kx1x_k=kx_1 . Then we have x1+xn1=n(x1)=2nx1=2x_1+x_{n-1}=n(x_1)=2n\rightarrow x_1=2 , and the rest is trivial.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.