Difference between revisions of "2023 IMO Problems/Problem 3"
(→Solution) |
(→Solution) |
||
Line 29: | Line 29: | ||
<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. | <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>. | + | 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. | 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. |
Revision as of 07:45, 4 October 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
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.