Some positive integers are initially written on a board, where each $2$ of them are different. Each time we can do the following moves: (1) If there are 2 numbers (written in the board) in the form $n, n+1$ we can erase them and write down $n-2$ (2) If there are 2 numbers (written in the board) in the form $n, n+4$ we can erase them and write down $n-1$ After some moves, there might appear negative numbers. Find the maximum value of the integer $c$ such that: Independetly of the starting numbers, each number which appears in any move is greater or equal to $c$
Problem
Source: Greece team selection test problem 4
Tags: algebra, invariant
OlympiadCombo
03.05.2017 22:00
Nice problem, though I'm not sure it is truly combinatorics.
Part 1: Moves for $c=-3$:
$$1,2,3,4,5$$$$0,2,3,4$$$$0,1,2$$$$-2,2$$$$-3$$Part 2: There can be no integer $n\le -4$.
Let the "A-power" of an integer $n$ be defined as the value of the term $a_n$, where $a_0=1$ and $a_n+a_{n+1}=a_{n-2}$ for all integers $n$. Furthermore, let the A-power of a board $C$ be the sum of the A-powers of the numbers written on it. Clearly, the A-power $P_a(C)$ of the board does not change when we perform move (1).
Similarly, let the "B-power" of an integer $n$ be defined as the value of the term $b_n$, where $b_0=1$ and $b_n+b_{n+4}=b_{n-1}$ for all integers $n$. Furthermore, let the B-power of a board $C$ be the sum of the B-powers of the numbers written on it. Clearly, the B-power $P_b(C)$ of the board does not change when we perform move (2).
The characteristic polynomials of the linear recurrences $a_n$ and $b_n$ are, respectively:
$$f_a(x)=x^3+x^2-1$$$$f_a(x)=x^5+x-1$$A quick sketch of $x^3+x^2-1=0$ shows that it has exactly one real root - lets call this root $r$. Since $(x^3+x^2-1)(x^2-x+1)=x^5+x-1$, and $x^2-x+1$ has no real roots, $x^5+x-1=0$ also has exactly one real root - the same root $r$ as $x^3+x^2-1=0$. Thus, $a_n=b_n=r^n$, where $r$ is the single real root of the previously described equations.
Then, A-power and B-power are in fact the same thing, so we may just call it "power" as there is no longer any point in differentiating between the two. That is, given any board $C$ with a set of starting numbers, the power of the board, $P(C)=\sum_{i\in (\text{numbers on board})} r^i$, is an invariant. The power after any number of moves will not differ from the power when we have the starting numbers.
Then, for all boards $C$, $$P(C)<\sum_{i=1}^{\infty} r^i$$$$\Longrightarrow P(C)<\frac{r}{1-r}$$
Now, suppose there is some number $n\le -4$ on the board. Then, since the power of every integer must be positive (as clearly $0<r<1$), this implies that $P(C)\ge r^{-4}$. However, note that:
$$r^5+r-1=0$$$$\Longrightarrow r^5=1-r$$$$\Longrightarrow 1=\frac{r^5}{1-r}$$$$\Longrightarrow r^{-4}=\frac{r}{1-r}$$Then, $P(C)\ge \frac{r}{1-r}$, which directly contradicts our above result. Thus, there can be no integer on the board with value less than or equal to $-4$, so $\boxed{c=-3}$ and we are done.$\blacksquare$
Borbas
03.05.2017 22:26
Perfect!