Maths Olympiad Prep

Library / /41 of 48

Combinatorics Difficulty 7.0 National olympiad, round 2 Prove it Greece

In the blackboard are written some positive integers. We define the following movements:

(α) Every two successive numbers, say n,n+1n, n+1, can be deleted by writing the number n2n-2.

(β) Every two numbers having difference 4, say k,k+4k, k+4, can be deleted by writing the number k1k-1.

In the case we cannot apply any of the above movements the process finishes.

Determine the maximal possible value of the integer cc with the following property: Irrespectively with the numbers are written at the beginning in the table, at all process, all the numbers written in the table are greater than or equal to cc.

Solution

**The answer is that that maximal possible value of cc is 3-3.**

In fact, this value is obtained if we start with the numbers 1,2,3,4,51,2,3,4,5, and following the process:
1,2,3,4,5α0,1,4,5α0,1,2α1,0β3.() 1, 2, 3, 4, 5 \xrightarrow{\alpha} 0, 1, 4, 5 \xrightarrow{\alpha} 0, 1, 2 \xrightarrow{\alpha} -1, 0 \xrightarrow{\beta} -3. \quad (*)
We will prove now that no matter which are initially the numbers, we cannot have a number smaller than 3-3 during the process.

To this end, we will find an invariant under the movements. Let ww be the real root of the polynomial
Px=x3+x21.P x = x^3 + x^2 - 1. Then,
w3+w2=1wn+1+wn=wn2.(1) w^3 + w^2 = 1 \Rightarrow w^{n+1} + w^n = w^{n-2}. \quad (1)
Moreover, the polynomial PxP x divides Qx=x5+x1Q x = x^5 + x - 1, so
Qw=0w5+w=1wk+4+wk=wk1(2). Q w = 0 \Leftrightarrow w^5 + w = 1 \Leftrightarrow w^{k+4} + w^k = w^{k-1} \quad (2).
From (1) and (2) we observe that if we consider one extra board which will have the numbers of our board raised to the ww power, then the sum of the numbers in the new board is invariant under α\alpha) and β\beta). For example, for the sequence in (*) the extra board will have the numbers,
w1,w2,w3,w4,w5αw0,w1,w4,w5αw0,w1,w2αw1,w0βw3. w^1, w^2, w^3, w^4, w^5 \xrightarrow{\alpha} w^0, w^1, w^4, w^5 \xrightarrow{\alpha} w^0, w^1, w^2 \xrightarrow{\alpha} w^{-1}, w^0 \xrightarrow{\beta} w^{-3}.
We observe, for example, that after the first movement the sum remains the same since w3+w2=w0w^3 + w^2 = w^0.

It is then enough to start with the minimal sum in the extra board, which is of course bigger than
w1+w2+w3+w4+=w1w=ww5=w4. w^1 + w^2 + w^3 + w^4 + \dots = \frac{w}{1-w} = \frac{w}{w^5} = w^{-4}.
So, in the initial board all the numbers are bigger than 4-4, so c3c \ge -3.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.