I've been reading about the use of invariants in contest math. I saw the following problem (in my own words):

There are $N = 2n$ numbers placed on a circle. Then we increase two any consecutive numbers by 1. Is it always possible repeating this procedure to get all numbers to be equal to $SomeNumber$?

The solution is to build an invariant $I = a_1-a_2+a_3-a_4...$. $I$ will always remain constant. For example, the initial numbers are 1,5,2,3 and we want all numbers to be 11. Then $I = 1 -5 + 2 -3 - = -5$ and if all the numbers were $11$ the invariant $I$ would be $0$. Which shows that it's impossible to make all numbers be $11$.

Q: I've been asking myself what invariant we would have to use if we were allowed to change $3$ consecutive numbers instead of $2$. The previous invariant doesn't work in this case because it would change by $\pm 1$.

  • 1
    $\begingroup$ For the two-consecutive-number case, we need $N$ even. $\endgroup$ – Travis Nov 1 '15 at 22:20
  • $\begingroup$ @Travis you are totally right! I will correct my question. $\endgroup$ – Kirill Nov 1 '15 at 22:21
  • $\begingroup$ I actually meant that, in order for this invariant argument to work, one needs $N$ to be even. But in saying so I assumed that the $1$st and $N$th numbers count as consecutive (after all, if they weren't, "placed on a circle" apparently doesn't entail any information). If this is the case, note that if $N$ is odd, then the coefficients of $a_1$ and $a_N$ are both $+1$, so if one chooses those numbers the "invariant" increases by $2$. $\endgroup$ – Travis Nov 1 '15 at 22:47
  • $\begingroup$ When changing 3 numbers in consecutive position the sum modulo 3 is invariant. So if N is divisible by 3 and the original sum isn't, then it's impossible. In other cases, I d.k. $\endgroup$ – DanielWainfleet Nov 2 '15 at 1:06

Hint In the first version of the problem, in which one adds $1$ to two consecutive numbers, the residue of $\sum_{i = 1}^N a_i$ modulo $2$ (i.e., the parity of the sum) is also an invariant under the operation. (Indeed, this is just the parity of $I$.)

  • $\begingroup$ This invariant would help us only if the initial sum is an odd number. If the initial numbers were for example $1,2,4,1$ then we would have to use my invariant. $\endgroup$ – Kirill Nov 1 '15 at 23:12
  • 1
    $\begingroup$ Yes, that's true, but the phrasing "Is it always possible..." in the question means it's enough to find an some invariant that isn't the same for all initial configurations. (Do you mean to claim that your invariant is also sufficient? That is, that it is zero for precisely the initial configurations for which all of the values are the same after some number of steps?) Provided this really is the question you're asking, one can approach the "$3$ consecutive numbers" version of the problem in a similar way to the hint. $\endgroup$ – Travis Nov 1 '15 at 23:41
  • $\begingroup$ (There's also a nice generalization of the invariant $I$ you describe to the "$3$ consecutive numbers" problem, but as per my previous comment it doesn't seem necessary to invoke it.) $\endgroup$ – Travis Nov 1 '15 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.