Let $a_1,a_2,\ldots,a_n,\ldots$ be any permutation of all positive integers. Prove that there exist infinitely many positive integers $i$ such that $\gcd(a_i,a_{i+1})\leq \frac{3}{4} i$.
Problem
Source: China TST 2011 - Quiz 3 - D2 - P2
Tags: ceiling function, floor function, number theory unsolved, number theory
Batominovski
21.05.2011 01:22
Analytic Approach
Let $\gamma \geq \frac{3}{4}$. Write $d_n:=\gcd\left(a_n,a_{n+1}\right)$. Let $\ell$ be a real number greater than $1$. Note that \[\zeta(\ell)= \sum_{n=1}^\infty \frac{1}{n^\ell} = \sum_{n=1}^\infty \frac{1}{a_n^\ell} = \frac{1}{2a_1^\ell}+\frac{1}{2}\sum_{n=1}^\infty \left(\frac{1}{a_{n}^\ell}+\frac{1}{a_{n+1}^\ell}\right)\,.\] Assume for the sake of contradiction that $d_n \geq \gamma n$ for every $n \in \mathbb{N}$.We must have\[\zeta(\ell) \leq \frac{1}{2a_1^\ell}+\frac{1}{2}\left(1+\frac{1}{2^\ell}\right)\sum_{n=1}^\infty \frac{1}{\lceil \gamma n \rceil^\ell} \leq \frac{1}{2a_1^\ell}+\frac{1}{2}\left(1+\frac{1}{2^\ell}\right)\left(1+\frac{1}{(4\gamma)^\ell}\right)\zeta(\ell) \,.\] Therefore, \[ \left(1-\frac{1}{2}\left(1+\frac{1}{2^\ell}\right)\left(1+\frac{1}{(4\gamma)^\ell}\right)\right) \zeta(\ell) < \frac{1}{2a_1^\ell} \leq \frac{1}{2}\,.\] However, the limit of the left-hand side when $\ell \to 1^+$ is $\infty$ if $\gamma > \frac{3}{4}$, and is \[\frac{\ln(2)}{3}+\frac{\ln(3)}{4} = \frac{\ln(432)}{12} > \frac{1}{2}\] if $\gamma=\frac{3}{4}$. Ergo, we have derived a contradiction. Hence, there must be an $m$ such that $d_m < \gamma m$.
The hidden content is a proof for existence of an $i$. However, I think you can modify it a little to show that there are infinitely many $i$'s. Many apologies for this mistake. (It is easy to change my incomplete proof to show that for any $\gamma > \frac{3}{4}$, there exist infinitely many $i$ such that $\gcd\left(a_i,a_{i+1}\right) < \gamma i$.)
jgnr
26.05.2011 15:35
Assume the contrary. For sufficiently large $i$, we have $(a_i,a_{i+1})\le\frac34i$. Take a large number $b$ and let $k$ be the smallest positive integer not contained in $a_1,a_2,\ldots,a_b$. Let $p$ be the integer such that $a_p=k$ and $q$ be the smallest positive integer such that the sequence $a_1,a_2,\ldots,a_q$ contains $1,2,\ldots,2k-1$.
Since $a_1,a_2,\ldots,a_b$ contains $1,2,\ldots,k-1$, then $b\ge k-1$. It is also clear that $p>b$, hence $p\ge k$.
Claim: If $p\le r<r+1\le q$, then $\max\{a_r,a_{r+1}\}\ge2k$.
Proof: Suppose the contrary, let $(a_r,a_{r+1})=l$. We have $l>\frac34r\ge\frac34p\ge\frac34k$. But $a_r$ and $a_{r+1}$ are multiples of $l$ and less than $2k$. Since $3l>\frac94k>2k$, then $a_r$ and $a_{r+1}$ must be $l$ and $2l$. So $l$ does not appear in $a_1,a_2,\ldots,a_b$, which implies $l\ge k$ and hence $2l\ge 2k$. Therefore one of $a_r$ and $a_{r+1}$ is not less than $2k$, a contradiction. The proof of claim is done. $\Box$
Therefore, among $a_p,a_{p+1},\ldots,a_q$, there are at most $\frac{q-(p-1)+1}2=\frac{q-p}2+1$ numbers which are less than $2k$. Since $a_1,a_2,\ldots,a_q$ contains $1,2,\ldots,2k-1$, then \[2k-1\le p-1+\frac{q-p}2+1=\frac{p+q}2\] Using $k>\frac34p$ and $2k-1>\frac34q$, we get $p\le\frac{4k-1}3$ and $q\le\frac{4(2k-1)-1}3=\frac{8k-5}3$, so $\frac{p+q}2\le2k-1$. Equality must hold, so $p=\frac{4k-1}3,q=\frac{8k-5}3,a_q=2k-1$. We also conclude that $a_1,a_2,\ldots,a_{p-1},a_p,a_{p+2},a_{p+4},\ldots,a_q$ are less than $2k$.
Since $1,2,\ldots,2k-2$ appears in $a_1,a_2,\ldots,a_{q-1}$ and $a_q=2k-1$, using the same argument as above, we conclude that $a_1,a_2,\ldots,a_{q-1}$ must be less than $2(2k-1)=4k-2$.
Now note that $(a_p,a_{p+1})>\frac34p=\frac{4k-1}4$, so $(k,a_{p+1})\ge k$, equality must hold, so $k|a_{p+1}$. But $a_{p+1}<4k-2$. So $a_{p+1}=2k\text{ or }3k$.
If $a_{p+1}=2k$, then $(2k,a_{p+1})>\frac34(p+1)=\frac{4k+2}4>k$, so $(2k,a_{p+2})=2k$ and $a_{p+2}>2k$, a contradiction.
Hence $a_{p+1}=3k$. We have $(3k,a_{p+2})>\frac34(p+1)>k$. Hence $(3k,a_{p+2}=\frac{3k}2$ and hence $a_{p+2}=\frac{3k}2$. Finally, we have $(a_{p+2},a_{p+3})>\frac34(p+2)$. Hence $(\frac{3k}2,a_{p+3})>\frac{4k+5}4>k$, hence $(\frac{3k}2,a_{p+3})=\frac{3k}2$. But $a_{p+3}$ cannot be equal to $a_{p+1}=3k$, hence $a_{p+3}\ge3\cdot\frac{3k}2>4k-2$, a contradiction. And we are finally done.
math154
17.02.2012 21:28
Assume for the sake of contradiction that there exists a positive integer $N$ such that $\gcd(a_i,a_{i+1})>3i/4\forall{i\ge N}$, and let $M=\max(a_1,\ldots,a_{N-1})$. We will repeatedly use the fact that $\min(a_i,a_{i+1})\ge 1+\lfloor{3i/4}\rfloor$ and $\max(a_i,a_{i+1})\ge 2+2\lfloor{3i/4}\rfloor$ for all $i\ge N$. (*) Now take a sufficiently large $n>M,N$ with $\{1,2,\ldots,M\}\subseteq\{a_1,\ldots,a_N,\ldots,a_{4m-1}\}$. Clearly we have $|\{1,2,\ldots,M\}\cap\{a_1,\ldots,a_{N-1}\}| = N-1$, so $|\{1,2,\ldots,M\}\cap\{a_N,\ldots,a_{4n-1}\}| = M-N+1$ and \begin{align*} |\{M+1,\ldots,6n\}\cap\{a_1,\ldots,a_{4n-1}\}| &=|\{M+1,\ldots,6n\}\cap\{a_N,\ldots,a_{4n-1}\}| \\ &\le 4n-1-N+1-(M-N+1)=4n-M-1. \end{align*}On the other hand, if $a_i\le 6n$, then by (*) and the fact that $1+\lfloor{3(8n)/4}\rfloor=1+6n$ we have $i\le 8n-1$. Furthermore, if $4n\le i\le 8n-1$, then $\max(a_i,a_{i+1})\ge 2+2\lfloor{3(4n)/4}\rfloor=2+6n$, so we can't have $a_i,a_{i+1}\le 6n$. Thus \begin{align*} 6n-M=|\{M+1,\ldots,6n\}\cap\{a_i\}_{i=1}^{\infty}| &=|\{M+1,\ldots,6n\}\cap\{a_i\}_{i=N}^{8n-1}| \\ &\le (4n-M-1)+\frac{8n-1-4n+1}{2}=6n-M-1, \end{align*}contradiction.
toto1234567890
04.05.2015 18:02
How much can the bound $ 3/4 $ be lowered?
Yankuangsi
08.08.2019 08:01
One can prove the constant is at least $\frac{1}{2}$ by constructing a sequence. However, the 'best' constant I know so far is $\sqrt{3}-1$, which is far from $1/2$.
Ti-Ci
08.03.2020 08:20
Using techniques similar to math154's we can replace the constant with $\frac{8}{11}(<\sqrt{3}-1)$.
mofumofu
27.01.2021 15:35
Here's a pretty quick proof for the original problem: Suppose there exists a positive integer $N$ such that $\gcd(a_i,a_{i+1})>3i/4\forall{i\ge N}$, then using the fact that all integers appears at least once in the sequence, we have that for any $k>N$, all integers from $1$ to $3k$ must appear among $a_1,a_2,\ldots a_{4k-1}$. Let $S_k = \{1,2,\ldots 3k\}$. Hence among $a_{2k},a_{2k+1},\ldots a_{4k-1}$ we can find at least $k+1$ of them belonging to $S_k$, thus there must exist $i$ with $2k\le i \le 4k-2$ such that $a_i, a_{i+1}$ both belong to $S_k$. Then since $a_i$ and $a_{i+1}$ are distinct, $\gcd(a_i,a_{i+1})\le \frac{3k}{2} = \frac{3}{4} (2k)$ and we are done.