In the blackboard are written some positive integers. We define the following movements:
(α) Every two successive numbers, say n,n+1, can be deleted by writing the number n−2.
(β) Every two numbers having difference 4, say k,k+4, can be deleted by writing the number k−1.
In the case we cannot apply any of the above movements the process finishes.
Determine the maximal possible value of the integer c 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 c.
Solution
**The answer is that that maximal possible value of c is −3.**
In fact, this value is obtained if we start with the numbers 1,2,3,4,5, and following the process: 1,2,3,4,5α0,1,4,5α0,1,2α−1,0β−3.(∗) We will prove now that no matter which are initially the numbers, we cannot have a number smaller than −3 during the process.
To this end, we will find an invariant under the movements. Let w be the real root of the polynomial Px=x3+x2−1. Then, w3+w2=1⇒wn+1+wn=wn−2.(1) Moreover, the polynomial Px divides Qx=x5+x−1, so Qw=0⇔w5+w=1⇔wk+4+wk=wk−1(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 w power, then the sum of the numbers in the new board is invariant under α) and β). 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αw−1,w0βw−3. We observe, for example, that after the first movement the sum remains the same since w3+w2=w0.
It is then enough to start with the minimal sum in the extra board, which is of course bigger than w1+w2+w3+w4+⋯=1−ww=w5w=w−4. So, in the initial board all the numbers are bigger than −4, so c≥−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.