Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2023 IMO Problems/Problem 3"

(→‎Solution)
(→‎See Also)
 
(35 intermediate revisions by the same user not shown)
Line 7: Line 7:
 
https://www.youtube.com/watch?v=JhThDz0H7cI [Video contains solutions to all day 1 problems]
 
https://www.youtube.com/watch?v=JhThDz0H7cI [Video contains solutions to all day 1 problems]
  
−
https://www.youtube.com/watch?v=SP-7LgQh0uY [Video contains solution to problem 3]
+
https://www.youtube.com/watch?v=CmJn5FKxpPY [Video contains another solution to problem 3]
 +
 
 +
Let <math>f(n)</math> and <math>g(j)</math> be functions of positive integers <math>n</math> and <math>j</math> respectively.
 +
 
 +
Let <math>a_{n}=a_{1}+f(n)</math>, then <math>a_{n+1}=a_{1}+f(n+1)</math>, and <math>a_{n+k}=a_{1}+f(n+k)</math>
 +
 
 +
Let <math>P=\prod_{j=1}^{k}\left ( a_{n+j} \right ) = \prod_{j=1}^{k}\left ( a_{n}+g(j)) \right )</math>
 +
 
 +
If we want the coefficients of <math>P(a_{n})</math> to be positive, then <math>g(j)\geq 0</math> for all <math>j</math> which will give the following value for <math>P</math>:
 +
 
 +
<math>P=a_{n}^{k}+C_{k-1}a_{n}^{k-1}+...+C_{1}a_{n}+\prod_{j=1}^{k} g(j) = P(a_{n})</math>
 +
 
 +
Thus for every <math>j</math> and <math>n</math> we need the following:
 +
 
 +
<math>a_{n}+g(j)=a_{n+j}=a_{1}+f(n+j)</math>
 +
 
 +
Solving for <math>g(j)</math> we get:
 +
 
 +
<math>g(j)=a_{1}+f(n+j)-a_{n}=a_{1}+f(n+j)-a_{1}-f(n)</math>
  
−
https://www.youtube.com/watch?v=CmJn5FKxpPY [Video contains another solution to problem 3]
+
<math>g(j)=f(n+j)-f(n)\geq 0</math> for all <math>n</math> and <math>j</math> because <math>g(j)</math> needs to be greater than or equal to zero for all coefficients to be non-negative.
 +
 
 +
This means that <math>f(n)</math> needs to be increasing with <math>n</math>, or staying constant, and also with <math>f(1)=0</math> because <math>a_{1}=a_{1}+f(1)</math>.
 +
 
 +
In addition, since we need all coefficients to be integer, then all <math>f(n)</math> and <math>g(j)</math> must also be integers.  We also need <math>g(j)</math> to not be dependent of <math>n</math>, so in the expression <math>f(n+j)-f(n)</math>, the <math>n</math> needs to cancel.  This mean that the rate of change for <math>f(n)</math> with respect to <math>n</math> needs to be constant.  This can only be achieved with <math>f(n)</math> be the equation of a line with slope being either zero or positive integer.
 +
 
 +
So, we set <math>f(n)</math> to be the equation of a line as <math>f(n)=mn+b</math> with <math>m</math> being the slope with a non-negative value and with <math>b</math> the intercept at <math>n=0</math>.  We know that <math>f(1)=0</math> so <math>f(1)=m+b=0</math> which means that <math>b=-m</math> and our function becomes <math>f(n)=mn-m=(n-1)m</math>. Since <math>f(n)</math> needs to be non-negative integer then <math>m\geq 0 \mid m \in \mathbb{Z}</math> then <math>f(n)</math> is increasing or constant, with <math>f(1)=0</math>
 +
 
 +
Then, <math>g(j)=f(n+j)-f(n)=(n+j-1)m-(n-1)m=jm</math>
 +
 
 +
This gives:
 +
 
 +
<math>\prod_{j=1}^{k}\left ( a_{n}+jm \right )=P(a_{n})=a_{n}^{k}+C_{k-1}a_{n}^{k-1}+...+C_{1}a_{n}+k!m^{k}</math>
 +
 
 +
with <math>C_{0}=k!m^{k}</math> and coefficients of polynomial <math>\geq 0</math>
 +
 
 +
Then, <math>a_{n}=a_{1}+f(n)</math>
 +
 
 +
Which provides the solution of all infinite sequences of positive integers as:
 +
 
 +
<math>a_{n}=a_{1}+(n-1)m</math>, <math>\forall m\geq 0 \mid m \in \mathbb{Z}</math> and <math>a_{1} \geq 1 \mid a_{1} \in \mathbb{Z}</math>
 +
 
 +
~ Tomas Diaz. orders@tomasdiaz.com
 +
 
 +
{{alternate solutions}}
  
−
Let <math>a_{n}=a_{1}+f(n)</math>, then <math>a_{n+1}=a_{1}+f(n+1)</math>, <math>a_{n+k}=a_{1}+f(n+k)</math>
+
==See Also==
  
−
Let <math>P=\prod_{i=1}^{k}\left ( a_{n+i} \right ) = \prod_{i=1}^{k}\left ( a_{n}+g(i)) \right )</math>
+
{{IMO box|year=2023|num-b=2|num-a=4}}

Latest revision as of 00:58, 19 November 2023

Problem

For each integer $k \geqslant 2$, determine all infinite sequences of positive integers $a_1, a_2, \ldots$ for which there exists a polynomial $P$ of the form $P(x)=x^k+c_{k-1} x^{k-1}+\cdots+c_1 x+c_0$, where $c_0, c_1, \ldots, c_{k-1}$ are non-negative integers, such that \[P\left(a_n\right)=a_{n+1} a_{n+2} \cdots a_{n+k}\] for every integer $n \geqslant 1$.

Solution

https://www.youtube.com/watch?v=JhThDz0H7cI [Video contains solutions to all day 1 problems]

https://www.youtube.com/watch?v=CmJn5FKxpPY [Video contains another solution to problem 3]

Let $f(n)$ and $g(j)$ be functions of positive integers $n$ and $j$ respectively.

Let $a_{n}=a_{1}+f(n)$, then $a_{n+1}=a_{1}+f(n+1)$, and $a_{n+k}=a_{1}+f(n+k)$

Let $P=\prod_{j=1}^{k}\left ( a_{n+j} \right ) = \prod_{j=1}^{k}\left ( a_{n}+g(j)) \right )$

If we want the coefficients of $P(a_{n})$ to be positive, then $g(j)\geq 0$ for all $j$ which will give the following value for $P$:

$P=a_{n}^{k}+C_{k-1}a_{n}^{k-1}+...+C_{1}a_{n}+\prod_{j=1}^{k} g(j) = P(a_{n})$

Thus for every $j$ and $n$ we need the following:

$a_{n}+g(j)=a_{n+j}=a_{1}+f(n+j)$

Solving for $g(j)$ we get:

$g(j)=a_{1}+f(n+j)-a_{n}=a_{1}+f(n+j)-a_{1}-f(n)$

$g(j)=f(n+j)-f(n)\geq 0$ for all $n$ and $j$ because $g(j)$ needs to be greater than or equal to zero for all coefficients to be non-negative.

This means that $f(n)$ needs to be increasing with $n$, or staying constant, and also with $f(1)=0$ because $a_{1}=a_{1}+f(1)$.

In addition, since we need all coefficients to be integer, then all $f(n)$ and $g(j)$ must also be integers. We also need $g(j)$ to not be dependent of $n$, so in the expression $f(n+j)-f(n)$, the $n$ needs to cancel. This mean that the rate of change for $f(n)$ with respect to $n$ needs to be constant. This can only be achieved with $f(n)$ be the equation of a line with slope being either zero or positive integer.

So, we set $f(n)$ to be the equation of a line as $f(n)=mn+b$ with $m$ being the slope with a non-negative value and with $b$ the intercept at $n=0$. We know that $f(1)=0$ so $f(1)=m+b=0$ which means that $b=-m$ and our function becomes $f(n)=mn-m=(n-1)m$. Since $f(n)$ needs to be non-negative integer then $m\geq 0 \mid m \in \mathbb{Z}$ then $f(n)$ is increasing or constant, with $f(1)=0$

Then, $g(j)=f(n+j)-f(n)=(n+j-1)m-(n-1)m=jm$

This gives:

$\prod_{j=1}^{k}\left ( a_{n}+jm \right )=P(a_{n})=a_{n}^{k}+C_{k-1}a_{n}^{k-1}+...+C_{1}a_{n}+k!m^{k}$

with $C_{0}=k!m^{k}$ and coefficients of polynomial $\geq 0$

Then, $a_{n}=a_{1}+f(n)$

Which provides the solution of all infinite sequences of positive integers as:

$a_{n}=a_{1}+(n-1)m$, $\forall m\geq 0 \mid m \in \mathbb{Z}$ and $a_{1} \geq 1 \mid a_{1} \in \mathbb{Z}$

~ Tomas Diaz. orders@tomasdiaz.com

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

2023 IMO (Problems) • Resources
Preceded by
Problem 2 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 4
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_IMO_Problems/Problem_3&oldid=204606"