Maulana's personal blog
Main feedMath/PhysicsSoftware Development

IMO 2023 problem 3

16-Jul-2023

I quoted a random tweet about IMO 2023 problem sheet.

The thing that interests me, was that the problem sheets were officially translated in Indonesian. So these students read it in Indonesian instead of English. Initially I thought they read the problem in English.

Then, a friend challenged me to solve problem number 3.

Before you assume anything, I am no formal mathematician, so consider this article as amateur attempt in solving the problem

Problem statement

Since the sheet I read is in Indonesian, I will try to translate back to English. But if you have the English sheet, you should probably refer to those.

For every integer kβ‰₯2k \ge 2, determine every positive integer sequence a1,a2,...a_1,a_2,... so that there is polynomial PP with form P(x)=xk+ckβˆ’1xkβˆ’1+...+c1x+c0P(x)=x^k+c_{k-1}x^{k-1}+...+c_1x+c_0 with c0,c1,...,ckβˆ’1c_0,c_1,...,c_{k-1} each a non-negative integer, so that:

P(an)=an+1an+2...an+kP(a_n)=a_{n+1}a_{n+2}...a_{n+k}

for every integer nβ‰₯1n\ge1

The proof (hopefully)

Initial guess

I don’t know exactly how I can prove it, lol. But the instant I saw this problem, I imagine something like this:

There is no restriction with what the sequence will be. It can be monotonic, cyclic, or constants. It just needs to be an integer. Since it ends with ......, I assume it is infinite.

Assume that there exists a trivial sequence (so that we can learn the behaviour first).

From this trivial sequence, if there exists an operator or function f(x)f(x), there might be a whole class of sequence by applying f(an)=bnf(a_n)=b_n. Thus, we can claim a whole class of sequence by finding this operator.

Since the relation of PP is a factors of the sequence. It is natural to guess that the operator is scalars. Such that:

f(x)=sxf(x)=sx

The relation becomes:

P(f(an))=f(an+1)f(an+2)...f(an+k)P(f(a_n))=f(a_{n+1})f(a_{n+2})...f(a_{n+k})

We can then pick P(x)=xkP(x)=x^k. So we got relation:

skank=san+1san+2...san+k=skan+1an+2...an+kank=an+1an+2...an+k\begin{align} s^ka_n^k=sa_{n+1}sa_{n+2}...sa_{n+k} &= s^ka_{n+1}a_{n+2}...a_{n+k} \\ a_n^k &= a_{n+1}a_{n+2}...a_{n+k} \end{align}

Which is consistent with our initial statements:

P(an)=an+1an+2...an+kank=an+1an+2...an+k\begin{align} P(a_n) = a_{n+1}a_{n+2}...a_{n+k}\\ a_n^k = a_{n+1}a_{n+2}...a_{n+k} \end{align}

Since it was consistent, if we find just one sequence, we will find a whole class of them.

The first thing came to mind is just a sequence of zero. Since any ana_n will just be zero, because of the products.

The next thing is a sequence of 1. Since any ana_n will just be 1.

So, this whole class of solutions is any an=sa_n=s which is a constants for every sequence indices, and it will span infinitely.

Some examples are 1,1,1,1...1,1,1,1... or 2,2,2,2,...2,2,2,2,..., basically all integers.

How to scan all solutions?

Well, I basically told my friend that the solution would be a constant integer sequence.

But he demand that I found all possible solution. Not just the trivial class.

Actually, I’m not sure if the Indonesian wording are descriptive enough. I thought it was obvious if we just pick any polynomial and then using the recurrence relation to find the sequence, forward or backward. It is like a construction, so I’m not really sure what else to proof.

Anyway, in my opinion, there is two different way to approach the problem. Either we define the sequence first and then define which polynomial obey the sequence. Or, we define the polynomial and then find the sequence.

But then again, going from the sequence, it was almost implies that the P(an)P(a_n) doesn’t have to be a polynomial at all. It can just be any function and the recurrence relation of number (3)(3) is just going to be the same.

So the key here is guessing what the sequence looks like. It is probably convenient if we use real number (I mean actual numbers like 1,2,3) to illustrate.

Suppose k=3k=3 (because k=2k=2 is too simple, it might not reveal the real behaviour). Then any P(an)P(a_n) has to be factorized into product of 3 numbers. Using the simplest P(x)=x3P(x)=x^3, we have a hint that any ana_n is a cube root average of the factors.

an3=an+1an+2an+3an=an+1an+2an+33\begin{align} a_n^3&=a_{n+1}a_{n+2}a_{n+3}\\ a_n&=\sqrt[3]{a_{n+1}a_{n+2}a_{n+3}} \end{align}

This is funny because ana_n then has to be in the middle if we order the sequence. If we follow this behaviour, then it implies that the sequence is not monotonic. If it is not monotonic, then it will just ends in cycle, because we can always swaps the order.

To illustrate, let’s use a1=3a_1=3, then the P(a1)=27P(a_1)=27. Factors of 2727 can be 11, 33, and 99. If a2=1a_2=1 sequence will stop, so we have to pick 3. But if we pick 33 it will just be the trivial sequence.

So we have no other way, besides modifying the PP function. If we assume that the sequence always increase (we have to, because integer products always increases), then there is a certain bound with the polynomial function in order to make sure that ana_n is always less than an+1a_{n+1}.

Let’s just say that Pk(x)=xk+Pkβˆ’1(x)P_k(x)= x^k + P_{k-1}(x) with Pkβˆ’1P_{k-1} means a polynomial with degree kβˆ’1k-1. This guarantees that an<an+1a_n < a_{n+1}. In order for Pkβˆ’1P_{k-1} to be always positives, then the coefficient of the polynomial has to be non-negative. This satisfies the problem statements as well.

Although this does proves the sequence exists, my friend probably demands me to show how exactly to construct the sequence.

It’s quite bothersome to write, but the general idea is to just find kk different numbers. This is going to be a subset of the sequence, it doesn’t have to be at the start, it can be in the middle. From the middle of the sequence, using PP relation, we can just iterate backward until it can’t be factorized again. The thing that we need to prove is how to make PP relation shows that it can always be iterated forward, to infinity. (because otherwise, it will just ends in trivial sequence again).

The case if PP can’t be factorized

Since PP was declared to be polynomials. If it can’t be factored into exactly kk integer factors then the sequence will stop, since you have to put 11 as the factor in the sequence.

Not sure if this requires further proof? But to illustrate, let’s say P(x)=x2+1P(x)=x^2+1, which can’t be factored. Well, I guess it can be factored into two complex polynoms, but we are dealing with integer here.

For example, x=3x=3, then P(3)=10=2.5P(3)=10=2.5. Sequence already breaks, since 3 is bigger than 2. If we swap the order, then P(2)=1.5P(2)=1.5. Sequence breaks again, since you need to put 11, because there’s no other integer factors.

Increasing the polynomials to, let’s say P(x)=x2+100P(x)=x^2+100 has no effect because we can always found such counterexample. You can’t forward the sequence because it can’t span infinitely.

There’s no sequence to find if PP can’t be factored.

The case if PP has the same roots

Suppose that P(x)=(x+s)kP(x)=(x+s)^k. This will not form infinite sequence since the sequence will stop when the factors is the same. This is basically the same with how we proves xkx^k except the graph is translated to the left.

The case if PP has different roots

Intuitively for any degree kk, and if the polynomial has kk root, intersected with the x-axis, then we can imagine the graph to be curved up and down, and eventually goes up forever.

Our sequence then must be on the right side of the graph, since we already proves that it must be monotonically increasing.

We will then need a minimum spacing between these sequence, since each member of the sequence has to be integer (difference can’t be less than 1).

Using the same operator concept we use earlier, assume that there exists a basic sequence. Other sequences with the same class is obtained by applying f(x)f(x) operator to each member of the sequence, so that f(an)=bnf(a_n)=b_n with bnb_n being the new sequence.

Since we need a certain interval between sequences, let’s just use f(x)=x+df(x)=x+d. I’m running out of variable, we already uses a,b,ca,b,c and ss, lol.

Also notice that we can’t use (for now) f(x)=sx+df(x)=sx+d because the product of the factors then becomes sxksx^k in the highest degree, meanwhile we want to focus on the polynomial xkx^k with the coefficient being one. Don’t worry though, this is just so that dd becomes integer. If we use scalar ss later, then dd just needs to be divisible by ss.

Anyway, start with the simplest one first.

P(f(an))=f(an+1)f(an+2)...f(an+k)P(an+d)=(an+1+d)(an+2+d)...(an+k+d)P(an+d)=(an+2d)(an+3d)...(an+(k+1)d)P(an+1)=(an+2)(an+3)...(an+k+1)\begin{align} P(f(a_n))&=f(a_{n+1})f(a_{n+2})...f(a_{n+k})\\ P(a_n+d)&=(a_{n+1}+d)(a_{n+2}+d)...(a_{n+k}+d)\\ P(a_n+d)&=(a_n+2d)(a_n+3d)...(a_n+(k+1)d)\\ P(a_{n+1})&=(a_{n+2})(a_{n+3})...(a_{n+k+1})\\ \end{align}

Now this has become interesting. The operator creates a new sequence, but it ended up shifting the indices by one. So, essentially this is the same sequence, it’s just that we start at different indices if we shift by dd interval. For a given dd, if we find kk numbers that is the member of the sequence, then we can use recurrence to find the whole sequence.

Step (8) to step (9) and (10) is intuitive because an+1=an+da_{n+1}=a_n+d and there should be no preference to nn, so this should be applicable to any nn. It means an+2=an+1+d=an+2da_{n+2}=a_{n+1}+d=a_n+2d, and so on.

We can check if this statement is true for very large number ana_n, since we want infinite sequence. We already defined that dd is the smallest integer for the particular operator f(x)f(x). Applying ana_n and an+1a_{n+1} to P(x)P(x) we have:

P(an+1)P(an)=an+1+kan+1an+1+k=an+1P(an+1)P(an)an+1+kβˆ’an+1=an+1(P(an+1)βˆ’P(an)P(an))\begin{align} \frac{P(a_{n+1})}{P(a_n)}&=\frac{a_{n+1+k}}{a_{n+1}} \\ a_{n+1+k}&=a_{n+1} \frac{P(a_{n+1})}{P(a_n)} \\ a_{n+1+k}-a_{n+1}&=a_{n+1} \left( \frac{P(a_{n+1})-P(a_n)}{P(a_n)} \right) \\ \end{align}

Now that previously we already establish for any polynomial, we can define ss such that P(x)=(x+s)kP(x)=(x+s)^k. Since in the right side we have a fraction of polynomial with the same kk degree, there is a limit when we use very large number ana_n. In this situation, the sequence is so large that an+1anβ‰ˆ1\frac{a_{n+1}}{a_n} \approx 1 is some relatively small difference. Using an upper bound of P(x)≀(x+s)k=xk+ksxkβˆ’1+...P(x)\le(x+s)^k=x^k+ksx^{k-1}+.... Then the term P(an+1)βˆ’P(an)P(an)\frac{P(a_{n+1})-P(a_n)}{P(a_n)} can be written as ksan+1kβˆ’1+...ank+...\frac{ksa_{n+1}^{k-1}+...}{a_n^k+...} when approaching this limit. (I’m too lazy to write the full expression).

an+1+kβˆ’an+1≀an+1ksan+1kβˆ’1+...ank+...=ks\begin{align} a_{n+1+k}-a_{n+1} &\le a_{n+1} \frac{ksa_{n+1}^{k-1}+...}{a_n^k+...}=ks \\ \end{align}

But remember that we said dd is the smallest distance for this sequence. If there are kk numbers, then the lower bound gap between the smallest and biggest number is simply kdkd. Then the lower bound of an+1+kβˆ’an+1β‰₯kda_{n+1+k}-a_{n+1} \ge kd. Combine this both we have

kd≀an+1+kβˆ’an+1≀ks\begin{align} kd \le a_{n+1+k}-a_{n+1} &\le ks \\ \end{align}

From this, we can see that the choice of dd and ss is arbitrary, as long as it works in P(x)P(x). So why not just set s=ds=d? Thus, explains the intuition behind step (8), (9), (10).

As a sanity check, let’s try again with k=3k=3, with d=1d=1.

Our polynomial then consists of 3 factors like this P(x)=(x+1)(x+2)(x+3)P(x)=(x+1)(x+2)(x+3). However, it is quite obvious now, that we can set a1=1a_1=1 then, the rests will follow a2=2a_2=2, a3=3a_3=3, a4=4a_4=4.

So, we have found another class of sequences. For any positive integer value of dd, we can construct a polynomial P(x)=(x+d)(x+2d)(x+3d)...(x+kd)P(x)=(x+d)(x+2d)(x+3d)...(x+kd), such that there exists ana_n that becomes the solutions. It also spans infinitely.

From this sequence, we can also find another sequence using the previous operator/function f(x)=sx+df(x)=sx+d. Suppose s=2s=2, so dd needs to be divisible by 2. Suppose d=6d=6. The new sequence b1=8b_1=8, b2=10b_2=10, b3=12b_3=12, b4=14b_4=14. The polynomial becomes: P(x+1)=(x+3)(x+5)(x+7)P(x+1)=(x+3)(x+5)(x+7) or can also be written as P(x)=(x+2)(x+4)(x+6)P(x)=(x+2)(x+4)(x+6)

The formula for the sequence then became an=a1+(nβˆ’1)da_n=a_1+(n-1)d. It is also nicely covers our previous sequence, since if d=0d=0, the sequence is a constant sequence.

So far this is then only possible polynomial roots with always increasing sequence. Any other factorization will lead to a breaking sequence again. We can try to define dd such that it is a function of nn (not a constant gap). The operator function f(x)=x+df(x)=x+d still works for arbitrary factorization function P(x)P(x). However, in the case of polynomials, the roots are fixed. That’s why the gap has to be constant if the factors need to extend infinitely.

There might be an interesting solution if P(x)P(x) is some infinite taylor series or some function that has a transform with infinite series, like a Fourier series.


Rizky Maulana Nugraha

Written by Rizky Maulana Nugraha
Software Developer. Currently remotely working from Indonesia.
Twitter FollowGitHub followers