Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem A. 569. (October 2012)

A. 569. Call a set A\subset\mathbb{Z} interesting if 2y-x\inA for all pairs x,y\inA with x<y. Let a1<a2<...<ak be positive integers (k\ge2) whose greatest common divisor is 1. Prove that if A is an interesting set and \{0,a_1,\ldots,a_k\}\subset A then a1+ak-3\inA.

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 a0<a1<...<ak (k\ge2) are elements of an interesting set A, the greatest common divisor of (a1-a0), (a2-a0), ..., (ak-a0) is 1, and s=ak+a1-a0-3, then {s,s+1,s+2,...}\subsetA.

In the particular case a0=0 this implies s\inA.

We prove the Lemma by induction on (ak-a0).

In the case ak-a0\ge2 we have k=2, a1=a0+1 and a2=a0+2, therefore s=a2+a1-a0-3=a0. So, s=a0\inA, s+1=a1\inA, és s+2=a2\inA. The set A is interesting, for every integer x, x\inA and x+1\inA impiles x+2=2(x+1)-x\inA. Hence, s,s+1,s+2,... are all elements of A.

Now suppose that ak-a0>2, and consider the numbers a1,a2,...,ak and 2a1-a0. We will apply the induction hypothesis to these numbers.

Since A is interesting 2a1-a0\inA. Among 2a1-a0,a1,a2,...,ak the number a1 is the smallest. The greatest common divisor of (a2-a1),...,(ak-a1) and (2a1-a0)-a1) also is 1, due to (ai-a1,(2a1-a0)-a1)=(ai-a1,a1-a0)=(ai-a0,a1-a0).

Case 1: There are at most 2 different values among 2a1-a0,a1,a2,...,ak.

Since a2,...,ak and 2a1-a0 are all greater thatn a1, this means k=2 and 2a1-a0=a2. Then a2-a0=2(a1-a0). The numbers a2-a0 and a1-a0 must be co-primes, so a1-a0=1 and a2-a0=2; this contradicts the assumption ak-a0>2.

Case 2: There are at least 3 distict values among 2a1-a0,a1,a2,...,ak, and 2a1-a0<a2.

Apply the induction hypothesis to b0=a1<b1=2a1-a0<b2=a2<...<bk=ak. (This is allowed by bk-b0=ak-a1<ak-a0.) Let t=bk+b1-b0-3. By the hypothesis \{t,t+1...\}\sbset A. Due to t=ak+(2a1-a0)-a1-3=s, this is what we need.

Case 3: There are at least 3 distict values among 2a1-a0,a1,a2,...,ak, and 2a1-a0>ak.

Apply the induction hypothesis to b0=a1,b1=a2,...,bk-1=ak,bk=2a1-a0. (Not that bk-b0=a1-a0<ak-a0.) Let t=bk+b1-b0-3. By the hypothesis, {t,t+1...}\subsetA. By t=(2a1-a0)+a2-a1-3=a2+a1-a0-3\les, we have {s,s+1,...}\subset{t,t+1,...}\subsetA.

Case 4: There are at least 3 distict values among 2a1-a0,a1,a2,...,ak, and a2\le2a1-a0\leak.

Sort the numbers a1,...,ak and 2a1-a0 in increasing order; let the ordered sequence be b_0<b_1<...<b_\ell, where \ell=k or \ell=k-1, b0=a1, b1=a2 és b_\ell=a_k.

Let t=b_\ell+b_1-b_0-3. Due to b\ell-b0=ak-a1<ak-a0, we can apply the induction hypothesis to get {t,t+1,...}\subsetA. Since t=ak+a2-a1-3\leak+(2a1-a0)-a1-3=s, we have {s,s+1,...}\subset{t,t+1,...}\subsetA.


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