Let $a_1,a_2,a_3, \cdots $ be distinct positive integers, and $0<c<\frac{3}{2}$ . Prove that : There exist infinitely many positive integers $k$, such that $[a_k,a_{k+1}]>ck $.
Problem
Source: China Hangzhou
Tags: number theory, inequalities, China TST
13.03.2015 14:34
Could anybody post the other problems?
13.03.2015 15:24
What do you mean by $[a_k, a_{k+1}]$? Is that a GCD or an LCM or what?
13.03.2015 15:39
@yugrey: It is supposed to be the LCM of the numbers.
13.03.2015 16:00
The least common multiple .
14.03.2015 16:02
How would you prove this problem? Can someone help me? Thanks a lot!
15.03.2015 06:48
Here is what I believe is some progress on the problem. It can succeed in showing that the sequence $\{a_i\}$ has infinitely many triples of terms $(a_m, a_{m + 1}, a_{m + 2})$ such that one is a multiple of the other two. However, I cannot seem to finish the problem. If anyone has any ideas or modifications to the idea please let me know.
15.03.2015 12:32
Suppose that there are finitely many $k$, then for some positive integer $N$ we have that $\forall x \geq N$, $[a_x,a_{x+1}] \leq cx$. Now let's use some trivial bounding, if $a_x | a_{x+1}$ then $ 2a_x \leq a_{x+1} = [a_x,a_{x+1}] \leq cx$, similarly if $a_{x+1} | a_x$ we get that $ 2a_{x+1} \leq a_x = [a_x,a_{x+1}] \leq cx \leq c(x+1)$, on the other hand if one is not a multiple of the other we get $2 max(a_x,a_{x+1}) \leq [a_x,a_{x+1}] \leq cx$. Now let's take a triple $(a_{x},a_{x+1},a_{x+2})$, we wish to prove that under these conditions $a_{x}+a_{x+1}+a_{x+2} \leq 2xc + C$ (for some constant $C$). Indeed suppose that $a_{x} = max (a_{x},a_{x+1},a_{x+2})$ then considering the cases above for the pair $(a_x,a_{x+1})$ we get $a_{x+1} \leq (c/2)x$, also if we had that $a_{x+1} | a_{x+2}$, then that together with the fact that $a_x > a_{x+2}$ implies that $a_{x+2} \leq a_x - a_{x+1}$ so $a_{x}+a_{x+1}+a_{x+2} \leq 2 a_{x} \leq 2cx$ (note that this is for the case when $a_{x+1}|a_x$, the other case results in $a_x \leq (c/2)x$ and is also true). So suppose that $ a_{x+1} \not | a_{x+2}$ then by the cases above $a_{x+2} \leq (c/2)(x+1) = (c/2)x + C$ so $a_{x}+a_{x+1}+a_{x+2} \leq cx + (c/2)x + (c/2)x + C = 2cx + C$. Suppose now that $a_{x+1} = max (a_{x},a_{x+1},a_{x+2})$ then similarly $a_x \leq cx/2$ and $a_{x+2}\leq c(x+1)/2$ so $a_{x}+a_{x+1}+a_{x+2} \leq 2cx + C$. The case when $a_{x+2}$ is maximum is done similarly. Thus considering the sequence $(a_{x},a_{x+1},...,a_{x+n})$ for some $x>N$, and by summing up the sum for each consecutive triple we get that $(3/2)(n+1)(n+2) - o \leq S \leq 2c(x+x+1+...+x+(n-2)) + C *(n-2)= 2cx*o` + c(n-1)(n-2) + C*(n-2)$ where $o,o`$ are linear functions on $n$ and $C$ is a constant (the LHS is calculated by considering that each term is distinct and in maximum 3 triples). Dividing by $n^2$ and taking the limit $n \rightarrow \infty$ results in $3/2 \leq c$ which is impossible. Remark: by only considering pairs one can similarly prove the weaker statement for $0<c<(4/3)$
15.03.2015 17:18
I think it is possible to generalize this to $0 < c^3 < 4$. sqing wrote: Let $a_1,a_2,a_3, \cdots $ be distinct positive integers, and $0<c^3<4$ . Prove that : There exist infinitely many positive integers $k$, such that $[a_k,a_{k+1}]>ck $. Suppose to the contrary, i.e. $\exists L$ $\in \mathbb{N}$ such that $\text{lcm}[a_k, a_{k+1}] \le ck$ $\forall k \ge L$. Let $k$ be sufficiently large. Then, $[a_k, a_{k+1}] \le ck$. If neither term divides the other, then $2\text{max}(a_k, a_{k+1}) \le [a_k, a_{k+1}] \le ck$. Otherwise, if $a_k|a_{k+1}$, then $2a_k \le [a_k, a_{k+1}] \le ck$ else $2a_{k+1} \le ck$. Let, $x,y,z = a_{k+2}$ be $3$ consecutive terms of the sequence. Now, all three of these are $\le c(k+2) = M$. We show that $xyz \le M^3/4$. Suppose the contrary. Then we must have $\text{max}(x,y,z) > M/2$. If $x = max(x,y,z)$ (this case is identical to the case where $z$ is maximum), then $y|x$. If $y \nmid z$, we have $z \le M/2$, and our claim is true. Otherwise, $y|x$ and $y|z$. Since $x>z$, therefore, $z \le x-y$. Then, $xyz \le x(y+z)^2/4$ $\le x^3/4$ $ \le M^3/4$. The other case arises if $y = max(x,y,z)$. Then $x|y$ and $z|y$, therefore $x,z \le M/2 \implies xyz \le M^3/4$. Let $k \ge L$ and consider $P = \prod_{i=k}^{k+n-1}a_{i}a_{i+1}a_{i+2}$. Note that $P$ is at least $(n!)^3$ (due to distinctness). Using the inequality proved above, we have \[(n!)^3 \le P \le \prod_{i=0}^{n-1}\left( \frac{c^3(k+i+2)^3}{4} \right) \implies n! \le \prod_{i=0}^{n-1}\left( \frac{c(k+i+2)}{\sqrt[3]{4}} \right)\] \[\implies \left( \frac{\sqrt[3]{4}}{c} \right)^n \le \binom{k+n+1}{n} \quad \forall n \in \mathbb{N}\]Since $\binom{k+n+1}{n} = \binom{k+n}{n-1}\left( 1+\frac{k+1}{n} \right)$ and $\frac{k+1}{n} \to 0$ as $n \to \infty$, we infer that this is impossible for large enough $n$, since $\sqrt[3]{4} > c$. Alternatively, one may obtain the same result using Stirling's approximation. Comment 1: If we can eliminate the messy casework (still working on that) and formally prove the corresponding inequality for arbitrarily large sets of consecutive terms, we can have the result true for $0 < c < 2$. Comment 2: As to why I chose products over sums, unlike the previous post is because I started out by writing $\text{lcm}(a,b) = ab/\text{gcd}(a,b)$ and obtained the result for $0< c <\sqrt{2}$ using pairs rather than triples.
16.03.2015 12:48
Suppose otherwise, hence $[a_k,a_{k+1}]<3k/2$ for all $k\geq d$ for fixed $d$. Since $\frac{a_ia_{i+1}}{|a_{i+1}-a_i|}<\frac{3k}{2}$, hence $|\frac{1}{a_i}-\frac{1}{a_{i+1}}|> \frac{2}{3k}$. Therefore, $|\frac{1}{a_d}-\frac{1}{a_{d+1}}|+|\frac{1}{a_{d+1}}-\frac{1}{a_{d+2}}|+...+|\frac{1}{a_n}-\frac{1}{a_{n+1}}|>\frac{2}{3d}+...+\frac{2}{3n}$ (where we pick $n$ s.t. $n+1-d$ even). Now we choose $a_i$ such that $LHS$ is maximal. Note that the $LHS$ evaluates to some number of the form $2(x_1+...+x_l)-2(y_1+...+y_l)$ for some $l$, where $x_i,y_j$ are some $\frac{1}{a_m}$. As $a_i<\frac{3n}{2}$ (otherwise the $LCM$ clearly exceeds), hence $2(\frac{1}{1}+...+\frac{1}{\frac{n+1-d}{2}})-2(\frac{1}{\frac{3n}{2}}+...+\frac{1}{\frac{3n}{2}+1-\frac{n+1-d}{2}})> \frac{2}{3d}+...+\frac{2}{3n}$. Let $RHS-LHS=S_n$ Hence for $S_{n+2}$, $S_{n+2}-S_n=\frac{2}{3(n+1)}+\frac{2}{3(n+2)}-\frac{2}{\frac{n+3-d}{2}}+\frac{2}{\frac{3(n+1)}{2}}+\frac{2}{\frac{3(n+2)}{2}}-\frac{2}{\frac{2n+d+1}{2}}$ $=\frac{4}{n+1}+\frac{4}{n+2}-\frac{4}{n+3-d}-\frac{4}{2n+d+1}$ $\geq \frac{4}{2n+2}+\frac{4}{n+2}-\frac{4}{n+3-d}$ Hence if we jump from $S_n$ to $S_{n+2k}$, $S_{n+2k}-S_n>\frac{4}{2(n+1)}+...+\frac{4}{2(n+2k-1)}+\frac{4}{n+2}+\frac{4}{n+4}+...+\frac{4}{n+2k}-\frac{4}{n+3-d}-\frac{4}{n+5-d}+...+\frac{4}{n+2k+1-d}>\frac{4}{2(n+1)}+...+\frac{4}{2(n+2k-1)}-\frac{4}{n+3-d}-\frac{4}{n+4-d}-...-\frac{4}{n+1}$ Clearly this number tends to infinity for $k$ increasing, hence there exist a $k$ such that $S_{n+2k}$ is positive, contradiction.
24.03.2015 17:02
Assume for the sake of contradiction that for some $ L \in \mathbb{Z}^{+}, $ we have that $ [a_k, a_{k + 1}] \le ck $ for all $ k \ge L. $ Lemma 1: $ a_k + a_{k + 1} + a_{k + 2} \le 2c(k + 2) $ for all $ k \ge L. $ Proof: For now, assume that $ a_{k + 1} = \text{max}(a_k, a_{k + 1}, a_{k + 2}). $ If $ a_k \vert a_{k + 1} $ and $ a_{k + 2} \vert a_{k + 1} $ then it's clear that $ a_k + a_{k + 1} + a_{k + 2} \le 2a_{k + 1} \le 2c(k + 1) $ as desired. Otherwise, assume WLOG that $ a_k \nmid a_{k + 1}. $ Then since $ [a_k, a_{k + 1}] \le ck $ we must have that $ a_{k + 1} \le \frac{c(k + 2)}{2} $ so $ a_k + a_{k + 1} + a_{k + 2} \le 3a_{k + 1} \le \frac{3c(k + 2)}{2} < 2c(k + 2) $ as desired. Now, assume that $ a_k = \text{max}(a_k, a_{k + 1}, a_{k + 2}) $ (the remaining case follows similarly). If $ a_{k + 1} \nmid a_k $ then like in the last paragraph we find that $ a_k \le \frac{ck}{2} $ so $ a_k + a_{k + 1} + a_{k + 2} \le 3a_k \le \frac{3ck}{2} < 2c(k + 2) $ as desired. Otherwise, we have $ a_{k + 1} \vert a_k $ which implies that $ a_{k + 1} \le \frac{ck}{2}. $ If $ a_{k + 1} \nmid a_{k + 2} $ then we also have $ a_{k + 2} \le \frac{c(k + 1)}{2} $ and so $ a_k + a_{k + 1} + a_{k + 2} \le ck + \frac{ck}{2} + \frac{c(k + 1)}{2} \le 2c(k + 2) $ as desired. Otherwise $ a_{k + 1} \vert a_{k + 2} $ so we have $ a_{k + 2} \le a_k - a_{k + 1} $ which implies that $ a_k + a_{k + 1} + a_{k + 2} \le 2a_k \le 2ck < 2c(k + 2) $ as desired. This concludes the proof of the lemma. Now using the lemma we have that $ \sum_{i = L}^{L + n - 1}(a_i + a_{i + 1} + a_{i + 2}) \le 2c\sum_{i = L}^{L +n - 1}(i + 2) = \frac{2cn(n + 2L + 3)}{2} $ for any $ n \in \mathbb{Z}^{+}. $ But $ \sum_{i = L}^{L + n - 1}(a_i + a_{i + 1} + a_{i + 2}) \ge \sum_{i = L}^{L + n - 1}(3i + 6 - 3L) = \frac{3(n^2 + 3n)}{2}. $ Combining these two inequalities we find that $ 2c(n + 2L + 3) \ge 3(n + 3) \Longrightarrow c \ge \frac{3(n + 3)}{2(n + 2L + 3)} $ so by letting $ n $ grow arbitrarily large we find that $ c \ge \frac{3}{2} $ as desired.
29.03.2015 20:59
Consider $(a_k,a_{k+1},a_{k+2})$, the sum is $\le 2ck+O(1)$ so sum over all the triples up to $N$ and for a big $N$ we get a contradiction
05.04.2015 07:52
For $ c < \frac{3}{2} $ let's say for all $ n>N $ : $ [a_{n},a_{n+1}]\leq cn $. then we use $ (a_{n},a_{n+1})\leq \frac{a_{n}+a_{n+1}}{3} $. So, we get $ \frac{1}{a_{n}}+\frac{1}{a_{n+1}}=\frac{a_{n}+a_{n+1}}{a_{n}a_{n+1}}\geq \frac{3(a_{n},a_{n+1})}{a_{n}a_{n+1}}=\frac{3}{[a_{n},a_{n+1}]}\geq \frac{3}{cn} $. So, if we add up, $\sum_{i=1}^{N}\frac{1}{i}+\sum_{i=1}^{2M}\frac{1}{N+i}= \sum_{i=1}^{N+2M}\frac{1}{i}\geq \sum_{i=1}^{N+2M}\frac{1}{a_{i}}=\sum_{i=1}^{N}\frac{1}{a_{i}}+\sum_{i=1}^{M}(\frac{1}{a_{N+2i-1}}+\frac{1}{a_{N+2i}})=A+\frac{3}{c}\sum_{i=1}^{M}\frac{1}{N+2i-1}> A+\frac{3}{2c}\sum_{i=1}^{M}(\frac{1}{N+2i-1}+\frac{1}{N+2i})=A+\frac{3}{2c}\sum_{i=1}^{2M}\frac{1}{N+i} $ . This is a contradiction.
24.04.2015 19:51
Assume that there are only a finite number of such integers. Then for some $N$, if $n>N$, then we have $a_k<cn$ if $k<n$. Let $A=(a_1,a_2,...a_{2n})$,$B=(a_{2n+1},a_{2n+2},...a_{4n})$. Then all the elements of $A$ are less than $2cn$, so there can be at most $2cn-2n$ elements of $B$ less than $2cn$. Since $c<3/2$, this means that more than half of the elements of $B$ are between $2cn$ and $4cn$, so we must have two consecutive elements of $B$, $a_k,a_{k+1}$ such that $2cn < a_k,a_{k+1}<4cn$. So neither of $a_k,a_{k+1}$ divides the other. Thus $[a_k,a_{k+1} ]> 4cn > ck$.
29.12.2015 16:33
What is the maximal c for this problem?? Does there exist one???
30.04.2017 18:20
Here is an interesting discussion about the upper bounds: https://mathoverflow.net/questions/228762/infinitely-many-k-such-that-a-k-a-k1ck2/228801#228801 It will be nice if someone can prove that $[a_k, a_{k+1}] = O(k)$ is not possible.
26.10.2020 19:56
Solved with nukelauncher. Assume for contradiction there is a positive integer \(K\) such that \(\operatorname{lcm}(a_k,a_{k+1})\le ck\) for all integers \(k\ge K\). Claim: For all \(k\ge K\), \[\frac1{a_k}+\frac1{a_{k+1}}\ge\frac3{ck}.\] Proof. Recall that \(a_k\ne a_{k+1}\). Then observe that \(a_k+a_{k+1}\ge3\gcd(a_k,a_{k+1})\) since \(\gcd(a_k,a_{k+1})\) divides \(a_k+a_{k+1}\) and \(a_k+a_{k+1}>2\min\{a_k,a_{k+1}\}\ge2\gcd(a_k,a_{k+1})\). Hence \[\frac1{a_k}+\frac1{a_{k+1}}=\frac{a_k+a_{k+1}}{\gcd(a_k,a_{k+1})\cdot\operatorname{lcm}(a_k,a_{k+1})}\ge\frac3{\operatorname{lcm}(a_k,a_{k+1})}\ge\frac3{ck}.\]\(\blacksquare\) Summing from \(k=K\) to \(k=N\), where \(N\) is arbitrary, we have \[\sum_{i=K}^N\left(\frac1{a_i}+\frac1{a_{i+1}}\right)\ge\frac3c\left(\frac1K+\cdots+\frac1N\right).\]But \(a_K\), \ldots, \(a_{N+1}\) are all distinct, so in the left-hand summation, \(1/j\) appears at most twice for each positive integer \(j\); then, \[\sum_{i=K}^n\left(\frac1{a_i}+\frac1{a_{i+1}}\right)\le\frac21+\cdots+\frac2N.\] Combining these two inequalities and rearranging, \[\frac21+\cdots+\frac2K\ge\left(\frac3c-2\right)\left(\frac1K+\cdots+\frac1N\right).\]Since \(3/c>2\), the left-hand side is fixed but the right-hand side is unbounded as \(N\to\infty\), contradiction.
07.08.2022 16:56
Can somebody check this solution?
19.07.2023 01:34
Suppose otherwise, so there are exactly $m$ positive integers $k$ with $\operatorname{lcm}(a_k,a_{k+1})>ck$; call such $k$ exceptional. Now take $N\gg m$ to be massive and consider the numbers $a_1,\ldots,a_{4N}$. On one hand, at most $2cN$ of these terms are at most $2cN$, so at least $(4-2c)N$ of these terms are more than $2cN$. On the other hand, for $k \leq 2N$, if $k$ is not exceptional, then we have $$a_k \leq \operatorname{lcm}(a_k,a_{k+1}) \leq ck \leq 2cN,$$so at most $m$ of the terms which are more than $3N$ lie in $\{a_1,\ldots,a_{2N}\}$, so at least $(4-2c)N-m$ of these terms lie in $\{a_{2N+1},\ldots,a_{4N}\}$. Since $4-2c>1$, it follows that for sufficiently large $N$ we have $(4-2c)N-m>\tfrac{1}{2}|\{a_{2N+1},\ldots,a_{4N}\}|=N$, so there must exist some $i \in [2N+1,4N-1]$ such that $a_i,a_{i+1}>2cN>\tfrac{c}{2}i$. If $\max\{a_i,a_{i+1}\}>ci$ then we immediately have $\operatorname{lcm}(a_i,a_{i+1})>ci$. Otherwise, since $\max\{a_i,a_{i+1}\}<2\min\{a_i,a_{i+1}\}$, $a_i$ cannot be a divisor of $a_{i+1}$ nor vice versa, hence $\operatorname{lcm}(a_i,a_{i+1})\geq 2a_i>ci$ as well: contradiction, since $i$ should not be exceptional by construction. $\blacksquare$ Remark: An excellent problem. My solution shows the power of trying stupid things, especially since the bound given appears to be very stupid (although the mathoverflow link above seems to indicate that this might not be the case)
21.06.2024 09:04
Suppose otherwise, and that $\text{lcm}(a_k, a_{k+1}) \leq ck$ for all $k \geq N$, for some positive integer $N$. Let us call an index $i > N$ big if it satisfies $a_i \geq 3i/4$. We consider all other indices small (even those including $i \leq N$). Note that $a_i \leq ci$ for all $i \geq N$. Claim: If index $k$ is big, then both $k-1, k+1$ are small. Further, one of $a_{k-1}, a_{k+1}$ is at most $k/2$. Proof: We have $\text{lcm}(a_{k-1}, a_k) \leq ck$ and $\text{lcm}(a_{k}, a_{k+1}) \leq ck$. Since $2a_k > ck$ (as the real $c$ is less than $3/2$) it follows that both of these LCMs are equal to $a_k$. As a result, $a_{k-1}$ and $a_{k+1}$ both divide $a_k$. This implies that big indices cannot be consecutive. Now we can also observe that among $a_{k-1}, a_{k+1}$, one of these is at most $a_k/3$, which is $\leq k/2$. We now write down numbers $a_1, a_2, \dots, a_M$ in that order for some $M > N$, to be chosen later. We color all the big indices black, and the corresponding index obtained from the claim for each of them blue (thus an index may be assigned blue more than once). We thus note that each black index has a blue index adjacent to it. Let us consider the sum of the $a_i$. Treating the initial $a_1+\dots+a_{N-1}$ as garbage offset (say equal to some fixed $C$), we focus on $i \geq N$. If we try to look at the "error" term $a_i - \frac{3i}{4}$ for these indices, we find that whenever some index $k$ is big, it's error goes from $0$ to $\leq (c-3/4)k+O(1)$, whereas whenever some index $k$ is colored blue, it's error goes from $0$ to $\leq -k/2+O(1)$. Let us consider the process of marking some index black, and some index adjacent to it as blue. This process increases our error by no more than $(c-3/4)i - i/2 + O(1) = (c-5/4)i + O(1)$. However, this bound cannot be easily summed over all black indices, since blue indices can be operated on twice. Thus we halve the $i/2$ to an $i/4$, and let the process increase our error by $(c-3/4)i - i/4 + O(1) = (c-1)i+O(1)$ instead. We can now treat the process as selecting a set $S$ of non adjacent indices from the range $[N, M]$ and increasing the sum of errors by $\leq (c-1)i+O(1)$. Since the best we can do by such a sum is $\leq M^2/4 + O(M)$ (select alternating), our error increases by at most \[(c-1)M^2/4 + O(M)\] Thus the total sum is at most \[C + \frac{3M^2}{8} + \frac{(c-1)M^2}{4} + O(M)\]But on the other hand, the numbers $a_1, a_2, \dots, a_M$ are all distinct; thus the sum is at least $\frac{M^2}{2}+O(M)$. Taking $M$ large, we obtain that \[\frac{c-1}{4} + \frac{3}{8} \geq \frac{1}{2}\]which implies that $c \geq 3/2$, a plain contradiction. This solves the problem.
01.01.2025 04:48
We will prove the result for $c<\frac{5}{3}$. Suppose otherwise, then move way past the finitely many counterexamples to take some index $n$. Define a small number to be a positive integer $m\le\frac{c}{3} n$, and define a big number to be a positive integer $m$ with $\frac{c}{3} n<m<cn$. Then note that if we only consider the first $n$ numbers in the sequence, it can only be composed of small and big numbers. Further divide the big numbers into sizeable numbers $m<\frac{c}{2} n$ and huge numbers $m\ge\frac{c}{2} n$. We claim that if two big numbers are adjacent, then one is a multiple of the other. This is because if there is a huge number, then two times that number is too big, so the lcm must be the huge number, contradiction, and if there are two sizeable numbers, then if they are $a$ and $b$ we would need their lcm to be both $2a$ and $2b$ ($3a$ and $3b$ are too large), contradiction. Now we claim that we cannot have three big numbers that are adjacent. Indeed, if it is $a<b<c$ or the other way around, then $c\ge 4a$ which is bad. If it is $a<b>c$, then one of $a,c$ is $\le b/3$ which is bad. If it is $a>b<c$, then one of $a,c$ is $\ge 3b$ which is bad. Now note that the first $\frac13 n-O(1)$ numbers in the sequence have to be small numbers since otherwise $a_k>ck$. Then for the other part, we will get at least $\frac13\cdot\left(\frac23 n+O(1)\right)-O(1)$ small numbers. So in total we will get at least $\frac59 n+O(1)>\frac{c}{3} n$ small numbers, which is too many. $\blacksquare$