a) $gcd(a_{2i}+2j,a_{2j}+2i)=1 \to a_{2i}$ or $a_{2j}$ is odd. Let it is $a_{2i}$ $gcd(a_{2i}+(2j+1),a_{2j+1}+2i)=1 \to a_{2j+1}$ is odd for every $j$ $2|gcd(a_{2i+1}+(2j+1),a_{2j+1}+(2i+1)) $ - contradiction

my idea:($a_i+j,a_j+i$)=($a_i+i+a_j+j,a_i+j$) then we take $a_i+i$=1(mod p) then $a_i+i+a_j+j$=2(mod p) with all odd prime p so we complete

For b I let: $a_1=p , a_2=p-1 , a_3=p-2 , ... , a_p=1$ $a_{p+1}=p , a_{p+2}=p-1 , a_{p+3}=p-2 , ... , a_{2p}=1$ $a_{2p+1}=p , a_{2p+2}=p-1 , a_{2p+3}=p-2 , ... , a_{3p}=1$ $...$ And proof is easy...

Another Problem: Do there exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: gcd(a_i+j,a_j+i)\leq2$ What if the sequence is a permutation of $\mathbb{N}$ ?

https://artofproblemsolving.com/community/c6h1268919p6622862

MahyarSefidgaran wrote: Another Problem: Do there exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: gcd(a_i+j,a_j+i)\leq2$ What if the sequence is a permutation of $\mathbb{N}$ ? IMO Shorlist 2015, N7, about good functions

oneCUBAN wrote: MahyarSefidgaran wrote: Another Problem: Do there exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: gcd(a_i+j,a_j+i)\leq2$ What if the sequence is a permutation of $\mathbb{N}$ ? IMO Shorlist 2015, N7, about good functions useless bump

Math-Ninja wrote: oneCUBAN wrote: MahyarSefidgaran wrote: Another Problem: Do there exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: gcd(a_i+j,a_j+i)\leq2$ What if the sequence is a permutation of $\mathbb{N}$ ? IMO Shorlist 2015, N7, about good functions useless bump No, the sequence exist in most general way, with $i\neq j$. The other part is your

Storage.

soroush.MG wrote: a) Prove that there doesn't exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: gcd(a_i+j,a_j+i)=1$ b) Let $p$ be an odd prime number. Prove that there exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: p \not | gcd(a_i+j,a_j+i)$ a) For this part, let us assume for the sake of contradiction that there does exists such a sequence $a_1, a_2, a_3 \dots \in \mathbb{N}$. Choose $i = 2m, j = 2n$ where $m \neq n$. We get that $\text{gcd}(a_{2m} + 2n, a_{2n} + 2m) = 1$ which is impossible if both $a_{2m}, a_{2n}$ are even and so one of $a_{2m}, a_{2n}$ is odd, let us say without loss of generality that $a_{2m}$ is odd. Then choose $i = 2m, j = 2r+1$ and we see that $\text{gcd}(a_{2m} + 2r + 1, a_{2r+1} + 2m) = 1$ which means that necessarily $a_{2r+1}$ is always odd, now choose $i = 2r_1 + 1, j = 2r_2 + 1$ and see that $\text{gcd}(a_{2r_1+1} + 2r_2 + 1, a_{2r_2+1}+2r_1+1) \geq 2 = 1$ which is a contradiction and hence our assumption is wrong as desired. b) For this part, since $p$ is an odd prime, take $a_i \in \mathbb{Z}_p$ such that $a_1 \equiv 1 - i \pmod{p}$. We see that $a_i + j \equiv a_j + i \equiv 0 \pmod{p} \implies 1 - i + j \equiv 1 - j + i \equiv 0 \pmod{p} \implies i - j \equiv j - i \equiv 1 \pmod{p} \implies (i-j) + (j-i) = 0 \equiv 2 \pmod{p}$ which is a contradiction, implying that $a_i + j, a_j + i \not\equiv 0 \pmod{p}$ for all $(i, j) \in \mathbb{N}$ which is the desired contradiction.

soroush.MG wrote: a) Prove that there doesn't exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: gcd(a_i+j,a_j+i)=1$ b) Let $p$ be an odd prime number. Prove that there exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: p \not | gcd(a_i+j,a_j+i)$ FTSOC assume there exist such sequence in $N$. Case 1-: if $a_1$ is odd then as we need $gcd(a_1+3,a_3+1)=1$ So $a_3$ must be even. Now as $gcd(a_2+3, a_3+2)=1$ then $a_2$ must be odd. Now we need $a_4$ such that $gcd(a_3+4, a_4+3)=gcd(a_2+4, a_4+2)=1$ but observe if $a_4$ is even then $gcd(a_3+4, a_4+3)\neq 1$ and similarly if $a_4$ is odd then $gcd(a_2+4, a_4+2)\neq 1$. Hence contradiction. Case 2-: if $a_1$ is even then $gcd(a_1+2,a_{2}+1)=1$ so $a_{2}$ is even and $gcd(a_2+4,a_4+2)=1$ so $a_4$ is odd. But then $gcd(a_1+4,a_4+1)\neq 1$ Hence contradiction. So No such sequence exist. soroush.MG wrote: b) Let $p$ be an odd prime number. Prove that there exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: p \not | gcd(a_i+j,a_j+i)$ For any odd prime $p$ we can always have a sequence $a_i\equiv 1-i\mod p$ which indeed satisfy $p\nmid gcd(a_i+j,a_j+i)=1$. $\blacksquare$

dame dame

I was most ridiculous in forcing the $a_i$'s I hope my sequence works

Oops fakesolved part b Part a) Suppose \( (i,j) = (2m, 2t+1) \) where $m$ is fixed and $t$ varies We have \[ \text{gcd}(a_{2m}+(2t+1), a_{2t+1}+(2m) ) = 1\] which implies \( (a_{2m}, a_{2t+1}) = (0,0), (1,1) \) where we take \( a_{2m}, a_{2t+1} \in \mathbb{Z}_2 \) Thus, our ordered triple becomes either \[ (a_1, a_2, a_3, a_4, ... ) = (0,0,0,0, ... ) \] or \[ (a_1,a_2,a_3,a_4, ... ) = (1,1,1,1, ... ) \] Case 1: \( (a_1, a_2, a_3, a_4, ... ) = (0,0,0,0, ... ) \) Take \( (i,j) = (2,4) \) and we have \( \text{gcd}(a_2+4, a_4+2) = 2 \), contradiction. Case 2: \( (a_1,a_2,a_3,a_4, ... ) = (1,1,1,1, ... ) \) Take \( (i,j) = (1,3) \) and we have \( \text{gcd}(a_1+3, a_3+1) = 2 \), contradiction. Thus, no sequence of $a_{i, i \geq 1}$ exists.

Solved with Periwinkle27 and Proxima1681.

(a) Assume the contrary. Notice if $2\nmid a_{2n}$ for any $n,$ then $\gcd(a_{2m+1}+2n,a_{2n}+2m+1)=1$ or $2\mid a_{2m+1}$ for all $m.$ Then, $$\gcd(a_{2m+1}+2k+1,a_{2k+1}+2m+1)\ge 2,$$a contradiction. Hence, we assume $2\mid a_{2n}$ for all $n,$ which implies $$\gcd(a_{2n}+2k,a_{2k}+2n)\ge 2,$$a contradiction. (b) Let $a_i\equiv 1-i\pmod{p},$ and assume FTSOC that $$p\mid\gcd(a_i+j,a_j+i)\implies p\mid a_i+j\land p\mid a_j+i.$$Then, $1-i+j\equiv 1-j+i\equiv 0\pmod{p},$ or $-1\equiv 1\pmod{p}\implies p\mid 2.$ $\square$

a) We first observe that there can be at most one even integer $a_m$ with an even index $m$, as otherwise, if there is another integer with an even index, say $a_n$, then $\gcd(a_n+m,a_m+n)=2$. Similarly, there can be at most one odd number $a_r$ with an odd index $r$. Hence, for all the other numbers, the paritity of $a_i$ and $i$ are different. Among those, choose an even $i$ and any odd $j>i$. This also immediatily implies that $\gcd(a_i+j,a_j+i)=2$. b) We claim that $a_i=1-i\mod p$ works for any odd prime $p$. First note if $p$ does not divide $a_j+i+a_i+j$, then $p$ can't divide both of $a_i+j$ and $a_j+i$, and hence cannot divide their gcd. Now, $$a_j+i+a_i+j=1-i+i+1-j+j=2\mod p$$so we are done.

(a) For the sake of contradiction, we assume the given condition to be false. Consider $a_1$ is odd. \[\gcd(a_1 + 2k + 1, a_{2k + 1} + 1) = 1\]So, $\forall k \in \mathbb{N}, a_{2k + 1} + 1$ is odd. Consider $a_2$ is odd. Then, \[\gcd(a_2 + 3, a_3 + 2) = 1\]$a_2$ is assumed odd, $a_3 + 2 \in \text{even}$. Hence, $2 \mid a_2 + 3$ and $2 \mid a_3 + 2$. Contradiction. So, $a_2$ is even. \[\gcd(a_2 + 4, a_4 + 2) = 1\]$2 \mid a_2 + 4$, so $a_4 + 2$ is odd $\implies a_4$ is odd. \[\gcd(a_4 + 5, a_5 + 4) = 1\]$a_5$ is even and so does $a_5 + 4$. Check that, $2 \mid a_4 + 5$, contradiction! Now, we assumed $a_1$ to be odd. Now, we are left with the part $a_1$ to be even. \[\gcd(a_1 + 2k, a_{2k} + 1) = 1\]$a_{2k} + 1$ must be odd. So, $\forall k \in \mathbb{N}, a_{2k}$ is even. Hence, $a_2$ is even. Let's assume $a_3$ is even too. \[\gcd(a_3 + 1, a_1 + 3) = 1\]Contradiction. So, $a_3$ is odd. \[\gcd(a_3 + 2k + 1, a_{2k + 1} + 3) = 1\]Hence, $a_{5}$ is even. Now, note that, \[d \mid a_1 + 5 \text{ and } d \mid a_5 + 1\]\[d \mid (a_5 - a_1) - 4\]$a_5$ and $a_1$ both are even, hence $d \geq 2$, contradiction!

1. Assume, with contradiction, that such a sequence exists for the given conditions. Consider $(i,j)=(2a,2b) \implies \gcd(a_{2a}+2b,a_{2b}+2a)=1.$ Note that for the latter condition to hold, we must have at most $1$ value of $i$ for which $a_{2i}$ is even. Therefore, $a_{2n} \equiv a_{2m} \equiv 1 \pmod{2}.$ From here, we can proceed with casework. Case 1. $(i,j)=(2n+1,2m) \implies \gcd(a_{2n}+2m,2_{2m}+2n+1)=1.$ However, since $a_{2m}$ is odd, $a_{2m}+2n+1$ is even, and hence $a_{2n+1}+2m$ must be odd, so $a_{2n+1}$ is odd. Case 2. $(i,j)=(2n,2m+1) \implies \gcd(a_{2n}+2m+1,a_{2m+1}+2n)=1.$ However, since $a_{2n}$ is odd, $a_{2n}+2m+1$ is even, and hence $a_{2m+1}+2n$ must be odd, so $a_{2m+1}$ is odd. Now, note that considering $(i,j)=(2n+1,2m+1) \implies \gcd(a_{2n+1}+2m+1,a_{2m+1}+2n+1)=1,$ we cannot have both $a_{2n+1}$ and $a_{2m+1}$ be odd, since then there would be more than one value of $i$ for which $a_{2i}$ is even, and hence $\gcd(a_{2n+1}+2m+1,a_{2m+1}+2n+1) \neq 1,$ a contradiction. 2. Note that $a_i=ip+1-i$ holds since $p$ is an odd prime.

1. Assume there exists a sequence that satisfies the conditions. Observe when $i,j = 2m,2n$ and $i,j = 2m+1,2n+1$. Then, $gcd(a_{2m} + 2n, a_{2n} + 2m) = 1$, so this means that at least one of $2m$ and $2n$ is odd. $gcd(a_{2m+1} + 2n+1, a_{2n+1} + 2m+1) = 1$ and this means that at least one of $2m+1$ and $2n+1$ is odd. Now, by comparing $i,j$ that is odd and even, we arrive at a contradiction as gcd has to be 2. 2. Note that $a_i = p(1-i)+pk$ works where is a variable that makes $a_i$ positive.

soroush.MG wrote: a) Prove that there doesn't exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: gcd(a_i+j,a_j+i)=1$ b) Let $p$ be an odd prime number. Prove that there exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: p \not | gcd(a_i+j,a_j+i)$ a. If we place $a_1$ as an odd number we will get a contradiction because we could pair all fo $a_n$ and we will see that all of $a_(odd)$ will be odd so we could not pair two odd $a_i$ because we will get an $gcd$ of a multiple of 2. Therefore, $a_1$ is even, and also because of the previous temp, we get all even terms odd and every odd ters even and we will get a contradiction if we pair 1 even term and 1 odd term. b. just make the ters of mod 3 like 2, 1, 0 then it will work

jelena_ivanchic wrote: Solved with Periwinkle27 and Proxima1681.

No, Your construction for part b doesn't work. As, $gcd(a_{p-1} + p, a_p + p-1)=gcd(p(i+1),p)=p$

Solved with kingu. I'm not entirely sure what possessed me when I didn't notice parity arguments killed part (a), of course our god kept his calm and carried as usual. (a) Say there exists such a sequence. We consider two even indices $i$ and $j$. Then, $a_i +i$ and $a_j+j$ can't both be even, so one of $a_i$ and $a_j$ is clearly odd. Say it is $a_i$. Then, for all odd integers $k$ , $a_i+k$ is even. Thus, $a_k+i$ cannot be even, which implies that $a_k$ is odd for all odd integers $k$. But then, considering two odd integers $k_1$ and $k_2$ we have that $a_{k_1}+k_2 $ and $a_{k_2}+k_1$ are both even, and thus there $\text{gcd}$ is greater than 1. Contradiction! Thus, there cannot exist such a sequence. (b) Consider the sequence $a_{pk}=pk-(p-1), a_{pk-1}=pk-(p-2) , \dots a_{pk-(p-1)}=pk$ for all positive integers $k$. In particular, here $a_i \equiv (p+1) -i \pmod{p}$ for all indices $i$. Then, say there exists two indices $i$ and $j$ which violate the desired condition. Then, $a_i+j \equiv (p+1)-i+j$ and $a_j+i \equiv (p+1)-j+i$. But, if \[p \mid (p+1)-i+j \implies p \mid j-i +1 \text{ and } p \mid (p+1)-j+i \implies p\mid i-j+1\]summing implies that $p \mid (i-j+1)+(j-i+1) = 2$ which is a clear contradiction. Thus, this sequence indeed satisfies the given condition and we are done. (This actually solves the extension in #5 as well).

a) Assume FTSOC such a sequence exists. Since $\gcd(a_2+4,a_4+2)=1$, it follows that $a_2$ or $a_4$ is odd. WLOG $a_2$ is odd. Then $\gcd(a_2+n,a_n+2)=1$ so $a_n$ is odd if $n$ is odd. But $a_1+3$ and $a_3+1$ are both even, a contradiction. $\square$ b) Choose $a_i$ such that $a_i+i\equiv1\pmod{p}$. Then $\gcd(a_i+j,a_j+i)=\gcd(a_i+i+a_j+j,a_j+i)$ is not divisible by $p$ since $a_i+i+a_j+j\equiv 2\pmod{p}$. $\square$

a) Consider $(2m, 2n)$: $(a_{2m}+2n, a_{2n}+2m) = 1$ implies that either $a_{2n}$ or $a_{2m}$ is odd. WLOG let $a_{2n}$ to be odd. Then: $$(a_{2n}+2k+1, a_{2k+1}+2n) = 1$$implies $a_{2k+1}$ is odd for all integers $k \ge 0$. Notice that: $$(a_{2k+1}+2t+1, a_{2t+1}+2k+1)=1$$implies $a_{2t+1}$ to be even, contradiction. There doesnt exists such a sequence. b) The sequence $a_i = pi+1-i$ evidently works and we are done. (For intuition on getting the sequence $a_i$) Notice that: $p \nmid \gcd(a_i+j,a_j+i) = \gcd(a_i+j + a_j + i, a_i,a_j+i)$ thus: $p \nmid a_i+a_j + i + j$. Taking any sequence $a_i$ which satisfies these conditions would work and we are done.

Saucepan_man02 wrote: a) Consider $(2m, 2n)$: $(a_{2m}+2n, a_{2n}+2m) = 1$ implies that either $a_{2n}$ or $a_{2m}$ is odd. WLOG let $a_{2n}$ to be odd. Then: $$(a_{2n}+2k+1, a_{2k+1}+2n) = 1$$implies $a_{2k+1}$ is odd for all integers $k \ge 0$. Notice that: $$(a_{2k+1}+2t+1, a_{2t+1}+2k+1)=1$$implies $a_{2t+1}$ to be even, contradiction. There doesnt exists such a sequence. b) The sequence $a_i = pi+1-i$ evidently works and we are done. (For intuition on getting the sequence $a_i$) Notice that: $p \nmid \gcd(a_i+j,a_j+i) = \gcd(a_i+j + a_j + i, a_i,a_j+i)$ thus: $p \nmid a_i+a_j + i + j$. Taking any sequence $a_i$ which satisfies these conditions would work and we are done. new and nice solution!

just put a_i= p-1 if i is divisible by p a_i=p if i isnt divisible by p and a_i reminder by p isnt 1 a_i=1 if else