# Problem A. 569. (October 2012)

**A. 569.** Call a set *interesting* if 2*y*-*x**A* for all pairs *x*,*y**A* with *x*<*y*. Let *a*_{1}<*a*_{2}<...<*a*_{k} be positive integers (*k*2) whose greatest common divisor is 1. Prove that if *A* is an interesting set and then *a*_{1}+*a*_{k}-3*A*.

Proposed by: *Carlos Gustavo T. A. Moreira (Gugu),* Rio de Janeiro

(5 pont)

**Deadline expired on November 12, 2012.**

**Solution. **We prove a more general statement.

*Lemma.* If *a*_{0}<*a*_{1}<...<*a*_{k} (*k*2) are elements of an interesting set *A*, the greatest common divisor of (*a*_{1}-*a*_{0}), (*a*_{2}-*a*_{0}), ..., (*a*_{k}-*a*_{0}) is 1, and *s*=*a*_{k}+*a*_{1}-*a*_{0}-3, then {*s*,*s*+1,*s*+2,...}*A*.

In the particular case *a*_{0}=0 this implies *s**A*.

We prove the Lemma by induction on (*a*_{k}-*a*_{0}).

In the case *a*_{k}-*a*_{0}2 we have *k*=2, *a*_{1}=*a*_{0}+1 and *a*_{2}=*a*_{0}+2, therefore *s*=*a*_{2}+*a*_{1}-*a*_{0}-3=*a*_{0}. So, *s*=*a*_{0}*A*, *s*+1=*a*_{1}*A*, és *s*+2=*a*_{2}*A*. The set *A* is interesting, for every integer *x*, *x**A* and *x*+1*A* impiles *x*+2=2(*x*+1)-*x**A*. Hence, *s*,*s*+1,*s*+2,... are all elements of *A*.

Now suppose that *a*_{k}-*a*_{0}>2, and consider the numbers *a*_{1},*a*_{2},...,*a*_{k} and 2*a*_{1}-*a*_{0}. We will apply the induction hypothesis to these numbers.

Since *A* is interesting 2*a*_{1}-*a*_{0}*A*. Among 2*a*_{1}-*a*_{0},*a*_{1},*a*_{2},...,*a*_{k} the number *a*_{1} is the smallest. The greatest common divisor of (*a*_{2}-*a*_{1}),...,(*a*_{k}-*a*_{1}) and (2*a*_{1}-*a*_{0})-*a*_{1}) also is 1, due to (*a*_{i}-*a*_{1},(2*a*_{1}-*a*_{0})-*a*_{1})=(*a*_{i}-*a*_{1},*a*_{1}-*a*_{0})=(*a*_{i}-*a*_{0},*a*_{1}-*a*_{0}).

*Case 1: *There are at most 2 different values among 2*a*_{1}-*a*_{0},*a*_{1},*a*_{2},...,*a*_{k}.

Since *a*_{2},...,*a*_{k} and 2*a*_{1}-*a*_{0} are all greater thatn *a*_{1}, this means *k*=2 and 2*a*_{1}-*a*_{0}=*a*_{2}. Then *a*_{2}-*a*_{0}=2(*a*_{1}-*a*_{0}). The numbers *a*_{2}-*a*_{0} and *a*_{1}-*a*_{0} must be co-primes, so *a*_{1}-*a*_{0}=1 and *a*_{2}-*a*_{0}=2; this contradicts the assumption *a*_{k}-*a*_{0}>2.

*Case 2: *There are at least 3 distict values among 2*a*_{1}-*a*_{0},*a*_{1},*a*_{2},...,*a*_{k}, and 2*a*_{1}-*a*_{0}<*a*_{2}.

Apply the induction hypothesis to *b*_{0}=*a*_{1}<*b*_{1}=2*a*_{1}-*a*_{0}<*b*_{2}=*a*_{2}<...<*b*_{k}=*a*_{k}. (This is allowed by *b*_{k}-*b*_{0}=*a*_{k}-*a*_{1}<*a*_{k}-*a*_{0}.) Let *t*=*b*_{k}+*b*_{1}-*b*_{0}-3. By the hypothesis . Due to *t*=*a*_{k}+(2*a*_{1}-*a*_{0})-*a*_{1}-3=*s*, this is what we need.

*Case 3: *There are at least 3 distict values among 2*a*_{1}-*a*_{0},*a*_{1},*a*_{2},...,*a*_{k}, and 2*a*_{1}-*a*_{0}>*a*_{k}.

Apply the induction hypothesis to *b*_{0}=*a*_{1},*b*_{1}=*a*_{2},...,*b*_{k-1}=*a*_{k},*b*_{k}=2*a*_{1}-*a*_{0}. (Not that *b*_{k}-*b*_{0}=*a*_{1}-*a*_{0}<*a*_{k}-*a*_{0}.) Let *t*=*b*_{k}+*b*_{1}-*b*_{0}-3. By the hypothesis, {*t*,*t*+1...}*A*. By *t*=(2*a*_{1}-*a*_{0})+*a*_{2}-*a*_{1}-3=*a*_{2}+*a*_{1}-*a*_{0}-3*s*, we have {*s*,*s*+1,...}{*t*,*t*+1,...}*A*.

*Case 4: *There are at least 3 distict values among 2*a*_{1}-*a*_{0},*a*_{1},*a*_{2},...,*a*_{k}, and *a*_{2}2*a*_{1}-*a*_{0}*a*_{k}.

Sort the numbers *a*_{1},...,*a*_{k} and 2*a*_{1}-*a*_{0} in increasing order; let the ordered sequence be , where =*k *or =*k*-1, *b*_{0}=*a*_{1}, *b*_{1}=*a*_{2} és .

Let . Due to *b*-*b*_{0}=*a*_{k}-*a*_{1}<*a*_{k}-*a*_{0}, we can apply the induction hypothesis to get {*t*,*t*+1,...}*A*. Since *t*=*a*_{k}+*a*_{2}-*a*_{1}-3*a*_{k}+(2*a*_{1}-*a*_{0})-*a*_{1}-3=*s*, we have {*s*,*s*+1,...}{*t*,*t*+1,...}*A*.

### Statistics:

8 students sent a solution. 5 points: Janzer Olivér, Nagy Róbert, Omer Cerrahoglu, Szabó 789 Barnabás. 1 point: 1 student. 0 point: 3 students.

Problems in Mathematics of KöMaL, October 2012