Sequence with condition on million consecutive terms

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Sequence with condition on million consecutive terms

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2021 Iberoamerican Mathematical Olympiad, P3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

225 posts

jbaca

#1 h Oct 20, 2021, 10:54 PM

Y by

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}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

303 posts

#2 h Oct 21, 2021, 12:25 AM • 1 Y

Y by PRMOisTheHardestExam

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.

This post has been edited 2 times. Last edited by blackbluecar, Dec 19, 2021, 4:54 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1184 posts

L567

#3 h Oct 21, 2021, 2:34 AM • 1 Y

Y by PRMOisTheHardestExam

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$

Remark

oops @below, I meant "un"bounded

This post has been edited 1 time. Last edited by L567, Oct 21, 2021, 4:40 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

323 posts

#4 h Oct 21, 2021, 4:03 PM • 3 Y

Y by PRMOisTheHardestExam, guptaamitu1, MatBoy-123

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$ .

This post has been edited 1 time. Last edited by juckter, Oct 21, 2021, 4:04 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6877 posts

#5 h Oct 23, 2021, 1:39 AM • 4 Y

Y by PRMOisTheHardestExam, HamstPan38825, Mathematicsislovely, pog

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

186 posts

#6 h Jan 15, 2022, 12:19 AM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

656 posts

#7 h Feb 7, 2022, 6:54 PM

Y by

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$

This post has been edited 1 time. Last edited by guptaamitu1, Feb 7, 2022, 6:55 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5610 posts

#8 h Jan 18, 2023, 1:08 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5003 posts

#9 h Feb 17, 2023, 12:26 AM • 1 Y

Y by megarnie

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1051 posts

#10 h Feb 17, 2023, 3:30 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

75 posts

#11 h Sep 21, 2023, 7:59 AM • 1 Y

Y by Vahe_Arsenyan

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8867 posts

#12 h Dec 21, 2023, 11:46 PM

Y by

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.

This post has been edited 1 time. Last edited by HamstPan38825, Dec 21, 2023, 11:47 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

733 posts

#13 h Feb 9, 2025, 3:44 PM

Y by

Suppose that $\{b_i\}_{i=1}^{\infty}$ is bounded above by $C$ . Since there are finitely many positive integers $b_i$ can take, there are infinitely many pairs where $b_i=b_j$ . Assume that the value $T$ is taken infinitely many times. Let $T=b_{m_1}=\dots=b_{m_r}=\dots$
$\frac{a_1\dots a_k}{a_1+\dots+a_k}=T=\frac{a_1\dots a_k\dots a_{k+l}}{a_1+\dots+a_{k+l}}\implies a_{k+1}\dots a_{k+l}=1+\frac{a_{k+1}+\dots+a_{k+l}}{a_1+\dots+a_k}$ Note that $a_1+\dots+a_k|a_{k+1}+\dots+a_{k+l}$ hence $k\leq a_{k+1}+\dots+a_{k+l}$ . We see that
$\frac{a_{k+1}+\dots+a_{k+l}}{l}\leq a_{k+1}\dots a_{k+l}=1+\frac{a_{k+1}+\dots+a_{k+l}}{a_1+\dots+a_k}\leq 1+\frac{a_{k+1}+\dots+a_{k+l}}{k}$ We pick $l\leq 10^6$ and $k$ sufficiently large (since there are infinitely many $b_i\in \mathbb{Z}^+$ and consecutive ones have difference at most $10^6$ we can apply this).
$1\geq (a_{k+1}+\dots+a_{k+l})(\frac{1}{l}-\frac{1}{k})\geq k(\frac{1}{l}-\frac{1}{k})\geq \frac{k}{l}-1>1$ Which gives a contradiction as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

658 posts

#15 h Apr 26, 2025, 5:16 AM

Y by

Suppose $b_n$ is bounded above. Let $A = 143414341434$ be a fixed constant.
Claim: Let $N$ be any integer. Then, there exists a value $k$ such that $a_k = a_{k + 1} = \dots = a_{k + N - 1} = 1.$
Proof: Suppose $c_1, \dots, c_k$ are the values greater than 1 in the set $a_1, a_2, \dots, a_m,$ where $m$ is some very big number. Then, $b_m = \frac{c_1\dots c_k}{c_1 + \dots + c_k + (m - k)}.$ Observe that $\frac{x\cdot j}{x + j}$ is an increasing function over $x \in (1, \infty)$ for a fixed $j > 0.$ Thus, if we were to smooth the value of $b_m$ by forcing all of the $c_i = 2,$ we get $b_m \geq \frac{2^m}{2m + k - m} \geq 2021^{2021}$ for sufficiently large $m.$ Thus, the claim must be true.

We now prove that this is a contradiction. Assume $b_n$ is bounded above by $B.$ We know there exists $k$ such that $a_{k + 1} = a_{k + 2} = \dots = a_{AB + k} = 1.$ Clearly, at least $B + 1$ values in the set $\{b_{k + 1}, b_{k + 2}, \dots, b_{k + AB + k}\}$ must be integers. However, clearly, the values $b_{k + i} > b_{k + j}$ for $i > j.$ Thus, this is impossible.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a