Difference between revisions of "2023 IMO Problems/Problem 3"
(→Solution) |
(→See Also) |
||
(36 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= | + | 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> | ||
+ | |||
+ | <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}} | |
− | + | ==See Also== | |
− | + | {{IMO box|year=2023|num-b=2|num-a=4}} |
Latest revision as of 01:58, 19 November 2023
Problem
For each integer , determine all infinite sequences of positive integers
for which there exists a polynomial
of the form
, where
are non-negative integers, such that
for every integer
.
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 and
be functions of positive integers
and
respectively.
Let , then
, and
Let
If we want the coefficients of to be positive, then
for all
which will give the following value for
:
Thus for every and
we need the following:
Solving for we get:
for all
and
because
needs to be greater than or equal to zero for all coefficients to be non-negative.
This means that needs to be increasing with
, or staying constant, and also with
because
.
In addition, since we need all coefficients to be integer, then all and
must also be integers. We also need
to not be dependent of
, so in the expression
, the
needs to cancel. This mean that the rate of change for
with respect to
needs to be constant. This can only be achieved with
be the equation of a line with slope being either zero or positive integer.
So, we set to be the equation of a line as
with
being the slope with a non-negative value and with
the intercept at
. We know that
so
which means that
and our function becomes
. Since
needs to be non-negative integer then
then
is increasing or constant, with
Then,
This gives:
with and coefficients of polynomial
Then,
Which provides the solution of all infinite sequences of positive integers as:
,
and
~ 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 |