Arithmetic Sequence of Products

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

Arithmetic Sequence of Products

G H J

Reveal topic tags

arithmetic sequence

L

G H BBookmark kLocked kLocked NReply

Source: IMO Shortlist 2023 N4

The post below has been deleted. Click to close.

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

813 posts

#1 h Jul 17, 2024, 12:01 PM • 6 Y

Y by OronSH, peace09, Tqhoud, BorivojeGuzic123, iamnotgentle, NO_SQUARES

Let $a_1, \dots, a_n, b_1, \dots, b_n$ be $2n$ positive integers such that the $n+1$ products
$a_1 a_2 a_3 \cdots a_n, b_1 a_2 a_3 \cdots a_n, b_1 b_2 a_3 \cdots a_n, \dots, b_1 b_2 b_3 \cdots b_n$ form a strictly increasing arithmetic progression in that order. Determine the smallest possible integer that could be the common difference of such an arithmetic progression.

This post has been edited 2 times. Last edited by GrantStar, Sep 15, 2024, 7:55 PM
Reason: Extra comma

Z K Y

The post below has been deleted. Click to close.

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

813 posts

#2 h Jul 17, 2024, 12:01 PM • 2 Y

Y by peace09, Tqhoud

Solution

This post has been edited 1 time. Last edited by GrantStar, Jul 17, 2024, 12:05 PM

Z K Y

The post below has been deleted. Click to close.

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

1593 posts

#3 h Jul 17, 2024, 12:06 PM • 1 Y

Y by peace09

We claim the smallest possible common difference is $n!$ . This is achievable with $a_i=i$ and $b_i=i+1$ .

Without loss of generality, let $\gcd(a_i,b_i)=1$ . Otherwise, we can divide both $a_i$ and $b_i$ by their gcd.

Next, let the arithmetic progression by $x, x+y, \dots, x+ny$ . Then, by dividing adjacent terms, we get that
$\frac{a_i}{b_i} = \frac{x+(i-1)y}{x+iy}.$ However, since $\gcd(a_i,b_i)=1$ , we get that $x+(i-1)y\mid a_i$ , so in fact, $a_i\geq x+(i-1)y\geq i$ . Finally, we have
$y=(b_1-a_1)\prod_{i=2}^na_i\geq 1\prod_{i=2}^n i=n!,$ as desired.

Z K Y

The post below has been deleted. Click to close.

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

407 posts

#4 h Jul 17, 2024, 1:29 PM • 1 Y

Y by Tqhoud

Let the common difference be $d_n$ . We'll prove that $d_n \geq n!$ (equality occurs if $a_i=i$ and $b_i = i+1$ ) and $B_n = \prod\limits_{i=1}^{n} b_i \geq (n+1)!$ by induction. The base case $n=1$ is trivial and for the induction step from $n$ to $n+1$ , note that the numbers $a_1a_2\ldots a_n$ , $b_1a_2\ldots a_n$ , $\ldots, b_1b_2\ldots b_n$ form an arithmetic progression because the numbers $a_1a_2\ldots a_na_{n+1}, b_1a_2\ldots a_na_{n+1}, \ldots, b_1b_2\ldots b_na_{n+1}$ do. Hence, by the induction hypothesis,
$d_{n+1} = d_na_{n+1} = B_n(b_{n+1}-a_{n+1}).$ However, $B_n$ is the $n$ -th term in the arithmetic progression $a_1a_2\ldots a_n, b_1a_2\ldots a_n, \ldots, B_n$ , so $B_n>nd_n$ . From here,
$a_{n+1} = \frac{B_n}{d_n}(b_{n+1}-a_{n+1})>n(b_{n+1}-a_{n+1})\geq n.$ Therefore $d_{n+1} = d_na_{n+1} \geq d_n (n+1) \geq (n+1)!$ by the induction hypothesis. To conclude, $b_{n+1} > a_{n+1} \geq n+1$ , so we have that $B_{n+1}\geq b_{n+1}(n+1)!\geq (n+2)!$ and the induction step is complete.

Z K Y

The post below has been deleted. Click to close.

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

256 posts

#5 h Jul 17, 2024, 2:32 PM • 4 Y

Y by khina, plagueis, Supertinito, InCtrl

This problem was proposed by Matthew Brennan (SnowEverywhere), Canada.

Z K Y

The post below has been deleted. Click to close.

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

179 posts

dkedu

#6 h Jul 17, 2024, 11:18 PM • 1 Y

Y by Tqhoud

We claim the answer is $n!$ , achievable with $a_i = i, b_i = i+1$ . Let $r_i = \frac {b_i}{a_i}$ . We can deduce that
$(r_i - 1)r_{i-1} = r_{i-1} - 1 \implies r_i = \frac{2r_{i-1} - 1}{r_{i-1}}$ We let $a_1 = a, b_1 = b$ and get that
$r_i = \frac{ib - (i-1)a}{(i-1)b - (i-2)a}\text{ when } i \ge 2$ So the difference is at least
$\begin{align*} &\left(\frac{b}{a} - 1\right)(a)(2b-a)(3b-2a)\cdots ((n-1)b - (n-2)a) \\ &= (b-a)(2b - a) \cdots ((n-1)b - (n-2)a) \\ &\ge 1 \cdot 2 \cdots n = n! \end{align*}$ since $b-a \ge 1$ and $ib - (i-1)a \ge (i-1)(b-a) + b = i + 1$ since $b > a \ge 1$ .

Z K Y

The post below has been deleted. Click to close.

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

26 posts

Tqhoud

#7 h Jul 18, 2024, 8:28 AM

Y by

We see that the common difference is

$r=(b_i - a_i ) b_1b_2\dots b_{i-1} a_{i+1} \dots a_n$
and we want smaller number can take it $r$

where $i$ is any positive integer and $n \ge i$

We see that if

$b_1b_2\dots b_{i-1}a_i\dots a_n,b_1b_2\dots b_{i}a_{i+1}\dots a_n ,b_1b_2\dots b_{i+1}a_{i+2}\dots a_n$
are consecutive numbers in arithmetic sequence equal to

$b_1b_2\dots b_{i-1}a_i\dots a_n + b_1b_2\dots b_{i+1}a_{i+2}\dots a_n = 2(b_1b_2\dots b_{i}a_{i+1}\dots a_n)$
$b_ib_{i+1}+a_ia_{i+1}=2(b_{i}a_{i+1})$
$\frac{a_i}{b_i} + \frac{b_{i+1}}{a_{i+1}}= 2$
We see that $gcd(a_i,b_i)=k$ where $k$ is any positive integer doesn't effect in this relation but we know that $b_i-a_i|r$
and we want smaller number $r$ so we can check that $gcd(a_i,b_i)=1$ where $i$ is a positive integer and $n \ge i$

from $b_ib_{i+1}+a_ia_{i+1}=2(b_{i}a_{i+1})$ we can see that

$a_{i+1}|b_ib_{i+1}$ so $a_{i+1}|b_i$ and $b_i|a_ia_{i+1}$ so $b_i|a_{i+1}$ so $b_i=a_{i+1}$

We get that

$a_{i+1}a_{i+2}+a_ia_{i+1}=2(a_{i+1})^2$
$a_{i+2}+a_i=2a_{i+1}, a_{i+2}-a_{i+1}=a_{i+1}-a_{i}=c$
$a_{i}=(n-1)c+a_{1}$
$r=(a_{i+1}-a_{i})a_2a_3\dots a_n=1(c+a_1)(2c+a_1)\dots ((n-1)c+a_1) \ge 1(2)(3)\dots (n)=n!$
so $r\ge n!$ and if we let

$a_i=i,b_i=i+1$
we see is a solution and $r=n!$ and we are done

This post has been edited 5 times. Last edited by Tqhoud, Jul 18, 2024, 8:36 AM
Reason: .

Z K Y

The post below has been deleted. Click to close.

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

1385 posts

#8 h Jul 21, 2024, 12:23 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.

614 posts

trk08

#9 h Jul 21, 2024, 4:54 AM

Y by

We claim the answer is $n!$ which can be achieved by $a_i=i$ and $b_i=i+1$ . We now show it is the smallest.

Note that in order to be an arithmetic sequence:
$\frac{a_1a_2+b_1b_2}{2}=b_1a_2$ $\frac{a_1a_2+b_1b_2}{2}=b_1a_2$ $\dots$ $\frac{a_{n-1}a_n+b_{n-1}b_n}{2}=b_{n-1}a_n.$ Thus:
$a_ia_{i+1}+b_ib_{i+1}=2b_ia_{i+1}$ $\iff b_{i+1}-a_{i+1}=\frac{a_{i+1}}{b_i}(b_i-a_i).$ If we let $b_1-a_1=k$ , then:
$b_1-a_1=k$ $b_2-a_2=\frac{k}{b_1}\cdot a_2$ $\dots$ $b_n-a_n=\frac{k}{b_1}\cdot\frac{a_2}{b_2}\dots\frac{a_{n-1}}{b_{n-1}}\cdot a_n.$ As a result:
$D=k\cdot a_n\cdot a_{n-1}\dots a_3\cdot a_2.$

Let:
$f(i)=\frac{b_1}{k}\cdot\frac{b_2}{a_2}\dots\frac{b_{i}}{a_{i}}.$ Note:
$b_i-a_i=\frac{1}{f(i-1)}\cdot a_i$ $\iff \frac{b_i}{a_i}-1=\frac{1}{f(i-1)}$ $\iff f(i)=f(i-1)+1.$ Also:
$b_i-a_i\geq 1$ $\implies a_i\geq f(i-1).$

Thus:
$f(1)=\frac{b_1}{k}>1$ $\implies f(1)\geq 2$ $\implies f(i)\geq i+1$ $\implies a_i\geq f(i-1)\geq i$ $\implies D\geq k\cdot n!\geq n!$ 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.

109 posts

#10 h Jul 23, 2024, 9:38 AM

Y by

Note that scaling all the terms of an arithmetic progression doesn't change the fact that it is an arithmetic progression. With that in mind, scale the given arithmetic progression such that the first term is $1$ , and the common difference $d=\frac{s}{t}$ for some $s,t \in \mathbb{N}$ such that $(s,t)=1$ . Hence the arithmetic progression becomes, $1, \frac{t+s}{t},\frac{t+2s}{t}, \cdots,\frac{t+ns}{t+(n-1)s}$ with $\frac{b_i}{a_i}=\frac{t+is}{t+(i-1)s}$ (Here, note that $(t+is,t+(i-1)s)=1$ because $(s,t)=1$ )
Now, note that all the terms of the arithmetic progression are integers. This forces that $a_i \ge t+(i-1)s$ . Thus, $a_1 \cdots a_n \ge \prod_{i=1}^n (t+(i-1)s)$ . In the equality case, the common difference becomes, $\prod_{i=0}^{n-1}(s+it) \ge n!$ With equality when $s=t=1$

This post has been edited 1 time. Last edited by Krish230905, Jul 23, 2024, 9:39 AM

Z K Y

The post below has been deleted. Click to close.

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

874 posts

#11 h Jul 29, 2024, 5:02 PM

Y by

The answer is $n!$ which is achieved when $a_i=i$ and $b_i=i+1$ for all $1\leq i \leq n$ . Choose positive integers $a$ and $d$ such that the arithmetic progression is $a,a+d,\dots, a+nd$ . Let $g=\gcd(a,d)$ , $a=ga'$ , and $d=gd'$ . Then by dividing consecutive terms, $\frac{b_i}{a_i}=\frac{a+id}{a+(i-1)d}$ thus $(a'+(i-1)d')|a_i$ . Multiplying cyclically and dividing out by $a'$ gives that $(a'+d)(a'+2d)\dots (a'+(n-1)d')|g$ Thus we have that $n!\leq g|d$ , as desired.

Z K Y

The post below has been deleted. Click to close.

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

161 posts

#12 h Jul 30, 2024, 1:09 PM

Y by

By rewriting the definition for the original arithmetic progression we notice that $\{\frac{a_i}{b_i-a_i}, 1 \le i \le n\}$ is an arithmetic progression with difference 1. Hence, for each $1 \le i \le n$ , $a_i$ > $(b_i-a_i)(i-1)$ , which implies $a_i \ge i$ . Then the difference is $(b_1-a_1)a_2a_3 \ldots a_n \ge 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n = n!$

Z K Y

The post below has been deleted. Click to close.

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

1868 posts

#13 h Aug 17, 2024, 11:18 PM • 2 Y

Y by OronSH, GrantStar

The answer is $\boxed{n!}$ , with construction $a_k=k$ and $b_k=k+1$ . Clearly this works.

Let $x$ be the first term, and let $y$ be the common difference. Let $d=\gcd(x,y)$ , and let $x=ds$ , $y=dt$ . Now note that
$\frac{b_k}{a_k}=\frac{x+ky}{x+(k-1)y}=\frac{s+kt}{s+(k-1)t}.$ Note that this is a reduced fraction because $\gcd(s+kt,s+(k-1)t)=\gcd(s+kt,t)=\gcd(s,t)=1$ . Therefore,
$x=a_1a_2\dots a_n\ge (s)(s+t)(s+2t)\dots (s+(n-1)t),$ so
$d\ge (s+t)(s+2t)\dots (s+(n-1)t)\ge (1+1)(1+2)\dots (1+(n-1))=n!,$ so $y=dt\ge d\ge n!$ . $\blacksquare$

This post has been edited 1 time. Last edited by cj13609517288, Aug 17, 2024, 11:19 PM

Z K Y

The post below has been deleted. Click to close.

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

SomeonesPenguin

123 posts

SomeonesPenguin

#14 h Nov 14, 2024, 7:26 PM

Y by

The answer is $n!$ which is achieved for $a_i=i$ and $b_i=i+1$ .

First of all, it's easy to see that $b_i\ge a_i+1$ for all $i$ . Notice that since the sequence is an arithmetic progression, the term with $k$ $b$ 's plus the term with $k+2$ $b$ 's is equal to twice the term with $k+1$ $b$ 's. After dividing by the common terms this yields $a_ka_{k+1}+b_kb_{k+1}=2b_ka_{k+1}\iff \frac{b_k}{b_k-a_k}=\frac{a_{k+1}}{b_{k+1}-a_{k+1}}$ Now let $c_k=\frac{a_k}{b_k-a_k}$ . We have that $c_k=c_1+k-1, \ \forall k$ And since $c_1>0$ We get $\frac{a_k}{b_k-a_k}> k-1$ and this implies that $a_k>k-1$ , or $a_k\ge k$ . Finally, note that the common difference is $(b_1-a_1)a_2\ldots a_n\ge n!$ And this completes the proof. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

38 posts

#15 h Nov 21, 2024, 7:21 PM

Y by

MarkBcc168 wrote:

We claim the smallest possible common difference is $n!$ . This is achievable with $a_i=i$ and $b_i=i+1$ .

Without loss of generality, let $\gcd(a_i,b_i)=1$ . Otherwise, we can divide both $a_i$ and $b_i$ by their gcd.

Next, let the arithmetic progression by $x, x+y, \dots, x+ny$ . Then, by dividing adjacent terms, we get that
$\frac{a_i}{b_i} = \frac{x+(i-1)y}{x+iy}.$ However, since $\gcd(a_i,b_i)=1$ , we get that $x+(i-1)y\mid a_i$ , so in fact, $a_i\geq x+(i-1)y\geq i$ . Finally, we have
$y=(b_1-a_1)\prod_{i=2}^na_i\geq 1\prod_{i=2}^n i=n!,$ as desired.

Sorry but, shouldn't it be $a_i | x+(i-1)y$ ?

Z K Y

The post below has been deleted. Click to close.

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

8854 posts

#16 h Dec 16, 2024, 4:01 AM

Y by

The smallest possible difference is $n!$ . We will show the bound and give a construction simultaneously.

Let $d$ be the common difference. Notice that $a_2a_3 \cdots a_n(b_1-a_1) = d = b_1a_3\cdots a_n(b_2-a_2)$ so $\frac{b_1-a_1}{b_2 - a_2} = \frac{b_1}{a_2}$ . Similar equations hold for each index $i$ . Letting $c_i = b_i - a_i$ for each $1 \leq i \leq n$ (noting that $c_i > 0$ ), the equations rewrite as $\frac{c_i}{c_i+a_i} = \frac{c_{i+1}}{a_{i+1}}$ for each $i$ .

Now let $d_i = \gcd(a_i, c_i)$ and $a_i = d_ix_i$ , $c_i = d_i z_i$ for each $i$ , with $x_i$ and $z_i$ relatively prime. Then $\frac{z_i}{x_i+z_i} = \frac{z_{i+1}}{x_{i+1}}$ for each $i$ , which implies that $z_i = z_{i+1} = z$ for some $z$ and $x_i = x_i + z_i = x_1 + (i-1)z$ . In particular, $d = a_2a_3\cdots a_n c_1 = d_1d_2\cdots d_n \prod_{i=2}^n (x_1 + (i-1)z).$ The values $x_1 + (i-1)z$ are positive and distinct for each $i$ , hence they multiply to at least $n!$ . Equality holds when $x_1 = 0$ and $z = 1$ , with all the $d_i$ equal to $1$ .

This post has been edited 2 times. Last edited by HamstPan38825, Dec 16, 2024, 4:02 AM

Z K Y

The post below has been deleted. Click to close.

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

69 posts

#17 h Mar 10, 2025, 11:01 AM • 1 Y

Y by alexanderhamilton124

https://youtu.be/Jne2UJVpFps

Z K Y

The post below has been deleted. Click to close.

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

300 posts

#18 h Mar 12, 2025, 10:27 PM

Y by

The answer is $n!,$ constructed by $a_i = i, b_{i} = i + 1.$
Note that we can subtract and divide by the required terms. We get $a_{i + 1}(b_i - a_i) = b_i(b_{i + 1}- a_{i + 1}).$
Furthermore, note that if $g = (a_i, b_i) > 1,$ then by dividing $a_i, b_i$ both by $g,$ it still forms an arithmetic sequence, but with smaller common difference. Thus, we assume $(a_i, b_i) = 1.$
Now, recall that $a_{i + 1}(b_i - a_i) = b_i(b_{i + 1} - a_{i + 1}).$ Dividing by $a_{i + 1}b_i,$ we get $\frac{a_i}{b_i} + \frac{b_{i+1}}{a_{i + 1}} = 2.$ However, since $(a_n,b_n) = 1,$ we get $b_i = a_{i + 1}.$ Thus, $a_{i} + b_{i + 1} = 2a_{i + 1}.$ Rearranging, $a_i + a_{i + 2} = 2a_{i + 1}.$ This forms an arithmetic sequence, and it is obvious our minimum is what we stated earlier.

Z K Y

The post below has been deleted. Click to close.

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

34 posts

#19 h Mar 17, 2025, 8:30 PM

Y by

The answer is $n!$ , with the construction $a_i = i$ and $b_i = i + 1$ . We now show that $n!$ is the minimum possible common difference.

Let $\frac{b_1}{a_1} = \frac{x + y}{x}$ for some relatively prime positive integers $x$ and $y$ . We see that $\frac{b_i}{a_i} = \frac{x + iy}{x + (i - 1)y}$ . The numerator and denominator of this fraction are both clearly relatively prime, and therefore $a_i \geq x + (i - 1)y$ .

We now compute the common difference of our sequence, which is $\begin{align*} (b_1 - a_1)a_2a_3\dots a_n. \end{align*}$
Because $b_1 - a_1 \geq y$ , this is clearly bounded by $\begin{align*} y\prod_{i = 1}^{n - 1} (x + iy). \end{align*}$
Obviously, when $x$ and $y$ are minimized, this product is minimized. Hence, the minimum possible value of this expression occurs when $x = y = 1$ , in which case the product is $n!$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a