Let $a_1,a_2,a_3, \ldots$ be a sequence of positive integers and let $b_1,b_2,b_3,\ldots$ be the sequence of real numbers given by $$b_n = \dfrac{a_1a_2\cdots a_n}{a_1+a_2+\cdots + a_n},\ \mbox{for}\ n\geq 1$$Show that, if there exists at least one term among every million consecutive terms of the sequence $b_1,b_2,b_3,\ldots$ that is an integer, then there exists some $k$ such that $b_k > 2021^{2021}$.
Problem
Source: 2021 Iberoamerican Mathematical Olympiad, P3
Tags: inequalities
21.10.2021 03:25
Notice that if $b_i$ and $b_j$ are consecutive integer terms then $i-j$ is bounded. This implies that there exists some integer $k$ where if $b_i=k=b_j$ and $b_i$ and $b_j$ are consecutive terms with this property, then $i-j$ is bounded. Now, notice that the only thing that decreases the denominator is $a_i=1$ and it does so linearly. And, if $a_i>1$ then the numerator increases exponentially while the denominator grows linearly. Thus, we require an arbitrarily large number of $a_i=1$'s to drag $b_i$ down to $k$, contradicting $i-j$ bounded.
21.10.2021 05:34
Suppose not, and let the $b_i$ be bounded above by $M$. Ignore the first $10000000M$ terms and only consider the rest, so the denominator of the $b_i$'s now only has numbers $> 10000000M$. Let $N$ be a sufficiently large number and consider the first $N$ terms. Every million terms, there is at least one integer, so there are at least $\frac{N}{10^6}$ integers. Since there are only $M$ possibilities for these, some integer appears at least $\frac{N}{10^6M}$ times, so by PHP, we can find two of these that are at most $10^6M$ apart. Say for the first number, we had the $b_i$ equal to $\frac{x}{y}$. The numbers in between cant be all $1$'s since then the integers cannot be equal. Let $P$ be the product of the numbers in between and $S$ be the sum. We have $\frac{xP}{y+S} = \frac{x}{y} \implies yP = y+S$. Note that we cant have $P = 1$ because then LHS is too small, so $P \ge 2$. I claim the LHS is now too big. Note that if an $a_i$ in between is $> 1$, then replacing it with $a_i - 1$ only decreases the difference between RHS and LHS. So, the worst case is when one number is $2$ and others are $1$, but then we want to show $2y > y+S \iff y > S$, which is true since $y$ was at least $10000000M$ and $S$ is at most $1000000M$ since there are those many numbers, so it is indeed impossible for the $b_i$ to be bounded, as claimed. $\blacksquare$
oops @below, I meant "un"bounded
21.10.2021 19:03
L567's remark wrote: We can also prove $a_i$ is bounded but this is useless for the problem. Wrong. Assume FTSOC that $b_i$ is bounded above. Claim. $a$ is bounded. Proof. Assume otherwise and choose a large $k$ such that $a_k > \max(a_1, a_2, \dots, a_{k - 1})$. Let $r \ge k - 10^6$ be such that $b_r$ is an integer and let $k = r + t$. Let $P_r = a_1\dots a_r$ and $S_r = a_1 + \dots + a_r$, so $P_r \ge S_r$. Then \begin{align*} b_k = \frac{a_1 \dots a_k}{a_1 + a_2 + \dots + a_k} > \frac{P_ra_k}{S_r + ta_k} \ge \frac{S_ra_k}{S_r + ta_k} \ge \frac{S_ra_k}{2\max(S_r, ta_k)} = \min \left(\frac{a_k}{2}, \frac{S_r}{2t}\right) \end{align*} Since $S_r \ge k - 10^6$ and both $k$ and $a_k$ can be arbitrarily large, this provides a contradiction. $\square$ Assume now that $a$ is bounded above by $M$. Let $c_1, c_2, \dots$ be the sequence of integers in the sequence $b_1, b_2, \dots$. Notice that the numerators of the $c_i$ are $M$-smooth, i.e. all of their prime factors are at most $M$. Since the $c_i$ are integers it follows that all the denominators must be $M$-smooth too. On the other hand, by the problem condition the sequence of denominators is strictly increasing, and any two consecutive denominators differ by at most $10^6 M$. This means the sequence of denominators has a positive lower density, which is a contradiction as the $M$-smooth numbers have density $0$.
23.10.2021 04:39
Let $K = 10^{10^{100}}$ be a huge absolute constant. We consider two cases. The first case is captured in the following claim. Claim: Suppose that after the first $K$ terms, at least one of every $K$ terms $a_i$ is greater than $1$. Then $b_i$ is unbounded. Proof. In that case, consider the first $n$ terms for some large $n$. Let $M = \max(a_1, \dots, a_n)$. We have that \[ b_n \ge \frac{ 2^{\left\lfloor 10^{-6} n - 1 \right\rfloor} M} {M+M+\dots+M} \ge \frac{1}{n} 2^{\left\lfloor 10^{-6} n - 1 \right\rfloor} \]since the product of every million terms is at least $2$ and one of the products is actually equal to $M$. The right-hand side is unbounded in $n$, as desired. $\blacksquare$ Thus, we may focus on the case where $a_N = a_{N+1} = \dots = a_{N+K-1} = 1$ for some $N \ge K$. Look at two indices $b_{N+i}$ and $b_{N+j}$ with $|j-i| \le 10^6$ and such that $b_i$ and $b_j$ are integers, as promised by the problem condition. We may write \[ b_i = \frac{X}{Y+i}, \qquad b_j = \frac{X}{Y+j} \]where $Y = a_1 + \dots + a_N \ge N \ge K$. Then \[ X \ge \operatorname{lcm} (Y+i, Y+j) = \frac{(Y+i)(Y+j)}{\gcd(Y+i, Y+j)} \ge \frac{1}{10^6} (Y+i)(Y+j) \]which means that \[ b_j \ge \frac{Y+j}{10^6} > \frac{K}{10^6} \]as needed.
15.01.2022 03:19
07.02.2022 21:54
Assume contrary. Let $\text{one million} = x$ and $2021^{2021} = y$. Note $$ \frac{a_{n+k}}{a_n} = a_{n+1} \cdots a_{n+k} \cdot \frac{a_1 + a_2 + \cdots + a_n}{a_1 + \cdots + a_{n+k}} $$Observe decreasing any of $a_1,\ldots,a_{k+n}$ would decrease the above value and increasing them would increase it (this fact will be used several times). By assumption the sequence $\{b_i\}_{i \ge 1}$ is bounded above by $y$. Fix a large $M$. Pick a $N > M$ such that $b_N$ is the max possible integer among $b_M,b_{M+1},\ldots$. We have two cases: Case 1: All of $a_{N+1},\ldots,a_{N+x}$ equal $1$. Pick a $1 \le r \le x$ such that $a_{N+r} \in \mathbb Z$. Then both $$ b_N = \frac{a_1a_2 \cdots a_N}{a_1 + \cdots + a_N} ~~,~~ b_{N+r} = \frac{a_1 \cdots a_N}{a_1 + \cdots + a_N + r} $$are integers. In particular $a_1a_2 \cdots a_N$ is divisible by both $a_1 + \cdots + a_N, a_1 + \cdots + a_N + x$. Thus, $$ b_N \ge \frac{\text{lcm}(a_1 + \cdots + a_N, a_1 + \cdots + a_N+r)}{a_1 + a_2 + \cdots + a_N} \ge \frac{a_1 + a_2 + \cdots + a_N + r}{r} \ge \frac{M}{x} $$But as $M$ is large, so $b_N > y$, contradiction. $\square$ Case 2: $a_{N+s} > 1$ for some $1 \le s \le x$. Then, $$ \frac{b_{N+s}}{b_N} = a_{N+1} \cdots a_{N+s} \cdot \frac{a_1 + \cdots + a_N}{a_1 + \cdots + a_{N+s}} \ge 2 \cdot \frac{N}{N+s+1} \ge \frac{2M}{M+s+1} \ge \frac{2M}{M+x+1} $$Now pick a $1 \le t \le x$ such that $b_{N + s + t} \in \mathbb Z$. Then, $$ \frac{b_{N+s+t}}{b_{N+s}} = a_{N+s+1} \cdots a_{N+s+t} \cdot \frac{a_1 + \cdots + a_{N+s}}{a_1 + \cdots + a_{N+s+t} } \ge \frac{N+s}{N+s+t} \ge \frac{M+s}{M+s+t} \ge \frac{M}{M+t} \ge \frac{M}{M+x} $$Thus it follows that $$ \frac{b_{N+s+t}}{b_N} \ge \frac{2M}{M+x+1} \cdot \frac{M}{M+x} $$As $M$ is large, so $b_{N+s+t} > b_N$, which contradicts the maximality assumption on $b_N$. $\blacksquare$
18.01.2023 04:08
Suppose that $b_i\le 2021^{2021}$ for all $i$. Claim: There exist arbitrarily large groups of consecutive $a_i$ all equal to $1$. Proof: Suppose this was not the case. Then for any arbitrarily large $k$, we have that at least one of $k$ consecutive terms in the sequence $(a_i)$ is greater than $1$. Fix a $k=C> 69^{420^{665^{1434}}}$ satisfying that condition. Notice that for any $n$ at least $n$ of $a_1, a_2, \ldots, a_{n\cdot C}$ are greater than $1$, which implies that \[b_{n\cdot C} \ge \frac{2^n}{a_1 + a_2 + \cdots + a_{n\cdot C}}\]Notice that the function $\frac{kx}{k+x}$ for fixed $k$ is increasing over the interval $(1, \infty)$, which implies that \[b_{n\cdot C} \ge \frac{2^n}{n\cdot 2 + (C-n)\cdot 1} = \frac{2^n}{n(C+1)},\]which exceeds $2021^{2021}$ for large $n$. $\square$ Now we have for any $M$, there exist $a_i, a_{i+1}, \ldots, a_{i+M-1}$ all equal to $1$. Fix a large $M > 665^{1434^{7776}}$ for which $a_i = a_{i+1} = \cdots = a_{i+M-1} = 1$, where $i> 665^{1434^{7776}}$ is a positive integer. Notice that there exist $x<y$ strictly between $i$ and $i+M - 1$ such that $y-x\le 10^6$ and $b_x, b_y\in \mathbb{Z}$. Let $x+d = y, a_1a_2 \cdots a_x = P, a_1 + a_2 \cdots + a_x = S$. We have \[b_x = \frac{P}{S}, b_y = \frac{P}{S+d}\]This implies that $\mathrm{lcm}(S, S+d)\mid P$, so \[P\ge \frac{S(S+d)}{\gcd(S, S+d)} \ge \frac{S(S+d)}{10^6},\]which implies that $b_x \ge \frac{S+d}{10^6}$, which exceeds $2021^{2021}$ because $S\ge x$ is a sufficiently large positive integer, contradiction.
17.02.2023 03:26
We prove that $b_i$ is unbounded which clearly finishes. Suppose for the sake of contradiction that the $b_i$ are all bounded above by some positive integer $M$. First note that $S_n:=a_1+\cdots+a_n$ is clearly unbounded, so $P_n:=a_1\ldots a_n$ must be as well, since it's bounded below by $S_n$ at least once in every million consecutive terms. We now prove the central claim. Claim: There cannot exist one trillion consecutive terms $a_{n+1}=\cdots=a_{n+10^{12}}=1$ for $n$ sufficiently large. Proof: We will first prove that there cannot exist one billion consecutive terms $a_{n+1}=\cdots=a_{n+10^9}=1$ if $b_n$ is an integer, if $n$ is sufficiently large, so $S_n\geq GM$, where $G$ is Graham's number. Suppose that we have $P_n=kS_n$, so $k\leq M$. Then if $a_{n+1}=\cdots=a_{n+10^9}=1$, we have $$b_{n+10^9}=\frac{kS_n}{S_n+10^9}>k-1 \iff kS_n>kS_n-S_n+10^9k-10^9 \iff S_n>10^9k-10^9,$$which is true. Thus $b_i \in (k-1,k)$ for all $n+1 \leq i \leq n+10^9$, so we have $10^9$ consecutive noninteger $b_i$: illegal. To finish, note that if $a_{n+1}=\cdots=a_{n+10^{12}}=1$ we can find some $1 \leq i \leq 10^6$ such that $b_i$ is an integer, so applying this lemma implies that there are at most $10^6+10^9$ consecutive one terms at a time, which clearly implies the desired claim. Now for large $n$ such that $S_n \geq \mathrm{TREE}(3)M$ (note that $\mathrm{TREE}(3)\gg G$), if we have $a_{n+1}=\cdots=a_{n+k}=1$ and $a_{n+k+1}=c>1$, we have $$b_{n+k+1}=\frac{cP_n}{S_n+c+k}\geq \frac{1.001P_n}{S_n}=1.001b_n \iff cS_n\geq 1.001(S_n+c+k) \iff S_n \geq \frac{1.001c+1.001k}{c-1.001}\geq 1.001+\frac{1.001k+1.001^2}{c-1.001}.$$By our claim, $k\leq M$, hence the last inequality is certainly true as $c\geq 2$. Thus we can find a subsequence of the $b_i$ which grows exponentially, which contradicts our initial assumption. This clearly gives us some $b_k>2021^{2021}$, so we're done. $\blacksquare$
17.02.2023 06:30
The goal is to prove that $(b_i)$ is unbounded; suppose otherwise. Now we first prove that we can never have an infinitely long string of $1$s, since otherwise for infinitely many consecutive $b_i$ we have $b_i < 1$ as $a_1a_2\cdots a_i$ is bounded whilst $a_1+a_2+\cdots + a_i$ is unbounded. Now take a very large $n$ and $k$ such that some term between $a_n$ and $a_{n+k}$ is greater than $1$ and with $b_n \geq b_k$; we can do this since $(b_i)$ is bounded. We get that $S \left( a_{n+1}a_{n+2}\dots a_{n+k} \right) \leq a_{n+1} + a_{n+2} + \dots + a_{n+k}$ where $S = a_1 + a_2 + \dots + a_n$. Suppose that $t$ of the $a_i$ between $a_n$ and $a_{n+k}$ are greater than $1$. Then if $t = 1$ then with sufficiently high $S$ we note that $S(a_i -1) > 10^6-1 + a_i$ which is a contradiction. Otherwise if $t>1$ we can just induct down on $t$ by noticing $a_i > 1$ contributes a lot more to the left-hand side than the right-hand side, done.
21.09.2023 10:59
We assume FTSOC that $b_k\leq 2021^{2021}$ $\forall k.$ Now the key claim is the following: Claim. For all $a\in\mathbb{N}$ $\exists b s.t. a_{b+i}=1 \forall i\in \{1,2,\dots, a\}.$ Proof. For some $a_i$ with $i$ arbitrarely big, let $c_1,c_2,...,c_k$ be the $a_j\geq 2$ for $j\leq i.$ Now: $$b_i=\frac{c_1\cdots c_k}{c_1+\cdots + c_k+(i-k)}.$$If we can show that $(i-k)>ck$ has a solution $k$ $\forall c,$ then the claim is proven by $PHP.$ In order to show this, we claim that $b_i$ would dicrease if we swap some $a_l\to a_l-1f.$ For the sake of simplicity we'll replace $a_1\to a_1-1.$ This is equivalent to: $$\frac{(c_1-1)c_2\cdots c_k}{c_1-1+c_2+\cdots c_k}\leq \frac{c_1\cdots c_k}{c_1+c_2+\cdots c_k}$$which is trivially true by expanding. So, iterating this procces until all $c_i's$ are $2$ we get that $$b_i\leq \frac{2^{k}}{2k+(i-k)}\leq 2021^{2021},$$which ends the claim. \blacksquare This means that we can get a $d$ such that there exist $d_1,d_2,...,d_m<10^6$ satisfying that all $b_{d}, b_{d+d_1}, b_{d+d_1+d_2}, \dots, b_{d+d_1+\cdots +d_m}$ are all integers, and $a_d,a_{d+1}, \dots a_{d+d_1+\cdots +d_k}=1.$ Let $f(i)=a_1+a_2+\cdots a_i.$ Now we have that $lcm(f(d),f(d+d_1),\dots f(d+d_1+\cdots +d_m))\mid a_1\cdot a_2\cdots a_d.$ Bounding the quotient of this $lcm$ and $f(d)$ is trivial, and ends the problem immediately.
22.12.2023 02:46
Let $\{x_i\}$ be the maximal subsequence of $\{b_i\}$ that consists of only integers. (For convenience, the indices of $\{x_i\}$ will match those of $\{b_i\}$ and thus not be always consecutive.) I claim that for every $x_i$, there exists an $r$ such that $x_{i+r} > x_i$, which will imply the result. Suppose for the sake of contradiction that there exists an $n$ such that $\{x_i\}$ is constant at $c$ for all $i \geq n$. Then, for $k > \ell > n$, we have \begin{align*} a_1a_2\cdots a_k &= c(a_1+a_2+\cdots+a_k) \\ a_1a_2\cdots a_\ell &= c(a_1+a_2+\cdots+a_\ell) \\ \implies a_{\ell+1}a_{\ell+2}\cdots a_k(a_1+a_2+\cdots+a_\ell) &= a_1+a_2+\cdots + a_k. \end{align*}Let $N = a_1+a_2+\cdots + a_\ell$. Then suppose $a_{\ell+1}+a_{\ell+2}+\cdots + a_k = m \cdot N$, such that $a_{\ell+1}a_{\ell+2}\cdots a_n > m \cdot N - 10^6$ as $k - \ell < 10^6$. It follows that $$Na_{\ell + 1}a_{\ell+2} \cdots a_k > N(m \cdot N - 10^6) > (m+1)N = a_1+a_2+\cdots+ a_k,$$which is an obvious contradiction.