It seems easy but hard to do. Need help.

Where can I find contest collections of Tuymaada?

Hint: Take mod $x^2 + x + 1$.

Math-wiz wrote: Where can I find contest collections of Tuymaada? Contests Collections / International Contests / Tuymaada Olympiad

Then someone plz compile the problems there

2019 https://artofproblemsolving.com/community/c911162_2019_tuymaada_olympiad

fattypiggy123 wrote: Hint: Take mod $x^2 + x + 1$. Can you provide a solution?

It should be $S \geq x^n + x - 1$ instead of strict inequality. Check that you are always either $X = \{x,x+1,x^2,x^2+1 \}$ when taken mod $x^2+x+1$. On the other hand $x^n + 1$ is either $X' = \{ 2,x+1, x^2+1 \}.$ Then check that the difference between elements of $S$ and $S'$ is at least $x-2$ and so $S$ will be at least $(x^n + 1) + (x-2) = x^n + x - 1$.

What motivates you to consider it modulo $x^2 + x + 1$?

fattypiggy123 wrote: It should be $S \geq x^n + x - 1$ instead of strict inequality. Check that you are always either $X = \{x,x+1,x^2,x^2+1 \}$ when taken mod $x^2+x+1$. On the other hand $x^n + 1$ is either $X' = \{ 2,x+1, x^2+1 \}.$ Then check that the difference between elements of $S$ and $S'$ is at least $x-2$ and so $S$ will be at least $(x^n + 1) + (x-2) = x^n + x - 1$. Wonderful proof. I have tried to mod $x,x-1,x+1$ but failed.

RevolveWithMe101 wrote: What motivates you to consider it modulo $x^2 + x + 1$? With the benefit of hindsight: the process is equivalent to substituting $x$ with $x^2$ or $x^2+2x+1$ at each step, and you want the $x$ to stay invariant.

We consider all the numbers modulo $x^2 + x + 1.$ If the number in the calculator is congruent to $x,$ then the number at the next step is congruent to $x^2$ or $x+1 \equiv {-x}^2.$ The number congruent to $x^2$ transforms either to $x^4 \equiv x$ or to $x^2+1 \equiv {-x}$. The numbers congruent to ${-x}^2$ and $-x$ are obtained by adding $1,$ so they can be only squared; This transforms them into numbers congruent to $x$ and $x^2,$ respectively. Thus we always get numbers congruent to $\pm x$ or $\pm x^2$ modulo $x^2 + x + 1,$ or, equivalently, congruent to $x,$ $x + 1,$ $x^2,$ $x^2+1$ modulo $x^2 + x + 1.$ Note that if $n$ gives the remainder $r$ when divided by $3,$ then: $$x^n+1 \equiv x^r+1 \ (mod\ x^3-1)$$and therefore $x^n + 1 \equiv x^r + 1\ (mod\ x^2 + x + 1).$ Thus $x^n + 1$ can leave only remainders $2, x + 1$ or $x^2 + 1$ when divided by $x^2 + x + 1.$ On the other hand, the numbers in the calculator can leave only remainders $x, x + 1, x^2$ or $x^2 + 1.$ It is easy to check that if $S$ (which gives one of the remainders $x, x + 1, x^2 , x^2 + 1$) is greater than $x^n + 1$ (which gives one of the remainders $2, x + 1, x^2 + 1$), then the difference is at least $x-2.$ It follows that if $S > x^n + 1,$ then $S>x^n+1+(x-2)=x^n+x-1.$