Maths Olympiad Prep

Library / /16 of 25

Number theory Difficulty 6.7 National olympiad Prove it Russia

Does there exist an infinite strictly increasing sequence a1,a2,a3,a_1, a_2, a_3, \ldots of positive integers such that the sum of any two distinct members of the sequence is coprime to the sum of any three its distinct members?

Существует ли бесконечно возрастающая последовательность a1,a2,a3,a_1, a_2, a_3, \ldots положительных целых чисел, такая, что сумма любых двух различных членов последовательности взаимно проста с суммой любых трёх различных её членов?

Solutions — 2

Solution 1

One example of such sequence is determined by a1=1a_1 = 1, a2=7a_2 = 7, an+1=(3an)!+1a_{n+1} = (3a_n)! + 1. Define a good pair/triple of elements of this sequence as such pair/triple where only number 1 may repeat. To show that the sequence fits, prove by induction that any good pair and any good triple have coprime sums.

Let (ai,aj)(a_i, a_j) and (ap,aq,ar)(a_p, a_q, a_r) be a good pair and a good triple of elements of the sequence. Then
gcd(ai+aj,ap+aq+ar)=gcd(ai+aj,ap+aqar)=1. \gcd(a_i + a_j, a_p + a_q + a_r) = \gcd(a_i + a_j, a_p + a_q - a_r) = 1.

Case 1. Suppose ama_m is only in the pair; say, am=aja_m = a_j. Then, since 0<ap+aq±ar3am10 < |a_p + a_q \pm a_r| \le 3a_{m-1}, the number am1=(3am1)!a_m - 1 = (3a_{m-1})! is divisible by ap+aq±ara_p + a_q \pm a_r, so
gcd(ai+am,ap+aq±ar)=gcd((ai+1)+(am1),ap+aq±ar)=gcd(ai+a1,ap+aq±ar)=1 \gcd(a_i + a_m, a_p + a_q \pm a_r) = \gcd((a_i + 1) + (a_m - 1), a_p + a_q \pm a_r) = \gcd(a_i + a_1, a_p + a_q \pm a_r) = 1
by the induction hypothesis.

Case 2. Suppose ama_m is only in the triple; say, am=aqa_m = a_q. Similarly, am1a_m - 1 is divisible by ai+aja_i + a_j, so
gcd(ai+aj,ap+a1±ar)=1 \gcd(a_i + a_j, a_p + a_1 \pm a_r) = 1
by the induction hypothesis.

Case 3. Suppose ama_m is in both the pair and the triple; say, am=aj=aqa_m = a_j = a_q. Then am1a_m - 1 is divisible by apai±ara_p - a_i \pm a_r, so
gcd(ai+am,ap+am±ar)=gcd(ai+am,apai±ar)=gcd(ai+a1,apai±ar)=1 \gcd(a_i + a_m, a_p + a_m \pm a_r) = \gcd(a_i + a_m, a_p - a_i \pm a_r) = \gcd(a_i + a_1, a_p - a_i \pm a_r) = 1
by the induction hypothesis. The induction step is proved.

Solution 2

Ответ. Да, существует.
Построим пример такой последовательности. Положим a1=1a_1 = 1, a2=7a_2 = 7, an+1=(3an)!+1a_{n+1} = (3a_n)! + 1. Для того, чтобы показать, что она удовлетворяет требованиям, нам придется доказать следующее утверждение, из которого будет следовать, что положенная последовательность — требуемая.

Пусть (ai,aj)(a_i, a_j) и (ap,aq,ar)(a_p, a_q, a_r) — хорошие пара и тройка элементов последовательности. Тогда
НОД(ai+aj,ap+aq+ar)=НОД(ai+aj,ap+aqar)=1. НОД(a_i + a_j, a_p + a_q + a_r) = НОД(a_i + a_j, a_p + a_q - a_r) = 1.
Доказательство проведём индукцией по наибольшему элементу. Для перехода предположим, что m>1m > 1. Число ama_m либо входит только в пару, либо только в тройку, либо в обе.

Случай 1. Пусть ama_m — только элемент пары; скажем, am=aja_m = a_j. Тогда, поскольку 0<ap+aq±ar3am10 < |a_p + a_q \pm a_r| \le 3a_{m-1}, число am1=(3am1)!a_m - 1 = (3a_{m-1})! делится на ap+aq±ara_p + a_q \pm a_r, то есть
НОД(ai+am,ap+aq±ar)=НОД((ai+1)+(am1),ap+aq±ar)=НОД(ai+a1,ap+aq±ar)=1 НОД(a_i + a_m, a_p + a_q \pm a_r) = НОД((a_i + 1) + (a_m - 1), a_p + a_q \pm a_r) = НОД(a_i + a_1, a_p + a_q \pm a_r) = 1
по предположению индукции.

Случай 2. Пусть ama_m — только элемент тройки; скажем, am=aqa_m = a_q. Аналогично, am1a_m - 1 делится на ai+aja_i + a_j, так что
НОД(ai+aj,ap+a1±ar)=1 НОД(a_i + a_j, a_p + a_1 \pm a_r) = 1
по предположению индукции.

Случай 3. Пусть ama_m — элемент и пары, и тройки; скажем, am=aj=aqa_m = a_j = a_q. Тогда am1a_m - 1 делится на apai±ara_p - a_i \pm a_r, так что
НОД(ai+am,ap+am±ar)=НОД(ai+am,apai±ar)=НОД(ai+a1,apai±ar)=1 НОД(a_i + a_m, a_p + a_m \pm a_r) = НОД(a_i + a_m, a_p - a_i \pm a_r) = НОД(a_i + a_1, a_p - a_i \pm a_r) = 1
по предположению индукции. Переход индукции доказан.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.