Hello Codeforces! Some months ago I wrote tutorial about basics of recurrent sequences. This blog, my second tutorial is about mine another favorite topic — Invariants and Monovariants. These are useful concepts which will help you solving problems, especially, constructive ones. Even if you are not familiar with this topics, I'm sure that you solved problems with use of invariants and monovariants without knowing it, continue reading, you will understand my point :) There will be hard problems which are based on old IMO problems, so I will try my best to explain solutions of examples.

So, what are Invariants and Monovariants? An invariant is a quantity that doesn't change. A monovariant is a quantity that changes monotically (that is, non-decreasing or non-increasing). Seems simple, yes?

Let's start with a few easy examples which you will better understand its point. I suggest you to try solving problems by your own before reading solution. Example 0.1: All numbers from 1 to 100000 are listed in the board. For each number in this board, we replace that number with its sum of digits while resulting number is bigger than 9. At the end, obviously, all numbers will be in range of [1, 9]. Determine which is bigger, number of 1's in new sequence or number of 2's?

Solution 0.1: It is a standard and easy problem, maybe you solved this type of problem before. We will use one well known fact to solve problem — S(n) - n is invariant in modulo 9, it is always 0 (where S(n) donates sum of digits of n). So, resulting number will be old number modulo 9 (if this value is 0, it will be 9). For example, take number 1234, if we do given operation, resulting number will be f(1234) = f(1 + 2 + 3 + 4) = f(10) = f(1) = 1, which is indeed equal to 1234 modulo 9 (let f(n) show given operation). Finally, new sequence will be like this: 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...., 1, 2, 3, 4, 5, 6, 7, 8, 9, 1. You can see that count of 1's here is one greater than count of 2's, finding count of them is easy from this sequence also.

Example 0.2: You are given 20 cards which all numbers from 0 to 9 appears in these cards exactly 2 times. Can you rearrange this cards such that, there will be i cards between cards which i is written on them (that is, cards of 0's will be adjacent, there will be 1 card between cards of 1's and so on).

Solution 0.2: This problem is a little trickier. Let the first position of card of i be a_i (position of first card is 1 and last card is 20) (that is, a₀ is first position of card of 0, a₁ is first position of card of 1 and so on). Therefore, second position of card of i will be a_i + i + 1. Sum of a_i + (a_i + i + 1) would be equal to sum of all numbers from 1 to 20, because there are all positions in union of a_i's and a_i + i + 1's. That sum is, (a₀ + a₀ + 0 + 1) + (a₁ + a₁ + 1 + 1) + ... + (a₉ + a₉ + 9 + 1) = 2 * (a₀ + a₁ + ... + a₉) + (1 + 2 + ... + 10) = 2 * (a₀ + a₁ + ... + a₉) + 55 = 1 + 2 + ... + 20 = 210. From there, 2 * (a₀ + a₁ + ... + a₉) = 155 which is impossible, since 155 is odd number.

Remark: As you can see from this problem, there is no very special things in invariant. We used being even of 2 * x as invariant. In next example, we will solve harder problem, which it can be used as competitive programming problem.

Example 0.3: There are 2n people (let them be 1, 2, 3, ..., 2n) and some of them are enemy to each other. It is guaranteed that, each of 2n people have at most n - 1 enemies. Initially, they sat on circular table in given order (i is neighbor of i - 1 and i + 1 for 2 ≤ i ≤ 2n - 1 and 1 is neighbor of 2n). Print finite list of moves which will rearrange people such that enemies will not be neighbor, or determine rearranging them is not possible. Here move is printed like: "1 l r" which means reverse places of people in segment [l, r] taken clockwise and "2 l r" which means reverse places of people in segment [l, r] takes counter-clockwise. Here is an sample for understanding problem better: Let n = 2 and enemies are {1, 2}, {3, 4} (that means 1 and 2 are enemy to each other, also 3 and 4 are enemy to each other). Order of sitting is {1, 2, 3, 4} shown as in the picture:

We want to rearrange that positions with moves such that people with same color will not be neighbor. For that, we simply reverse [2, 3] taken clockwise order. New positions will be:

Which satisfies our condition.

Solution 0.3: We will prove that that finite list of moves are always exists. Let A and B be enemies who are neighbor, for simplicity, consider A is on the left side of B (in aspect of B).

There are at most n - 1 enemy of A, so there will be at least n people who is not enemy of A, let them be C₁, C₂, ..., C_n. For each 1 ≤ i ≤ n, mark D_i as right neighbor if C_i (from aspect of C_i). Enemy count of B is at most n - 1, so all of D_i's can't be enemy of B, let D = D_k be one of them. Say that C = C_k and X₁, X₂, ..., X_t be persons who is sitting between B and C. Now, reverse [B, C] taken counter-clockwise, shown in the picture:

See, nobody expect A, B, C, D changed neighbors. A and C are not enemy, neither are B and D, so number of neighbor enemy pairs decreased at least one and it is our monovariant in this problem. Obviously, after finite moves, count of neighbor enemy pairs will be 0 as wanted in statement.

Remark: Did you see that problem on any judge before? If yes, please write it in comments, otherwise I'm planning to put this problem in SPOJ. Now, we have one more interesting problem, but without solution :) Try to solve it and share your solution with us in the comments.

Example 0.4: Equilateral triangle with side n divided into n² little equilateral triangles of sides 1 with parallel line to big triangle's sides. For better understanding, see the picture for n = 3:

In the given one of the vertices of little triangles, there is written -1, and 1 to all other vertices. For example, we write -1 to point A in the picture, and 1 to all other vertices. Or, we write -1 to point in the middle of picture, and 1 to all others. Check if we can make all numbers 1 with limited number of moves. Here, move is selecting one little triangle and changing signs of numbers on its vertices (that is, -1's will be 1, and 1's will be -1).

Now, we will move to more advanced problems. Next problem is one of the my favorite problems in this topic.

Example 1.1 [Based on IMO shortlist 1989]: A natural number is written in each square of an mxn chessboard. The allowed move is to add an integer k to each of two adjacent numbers in such way that non-negative numbers are obtained (two squares are adjacent if they share a common side). Check if we can make all numbers 0 after finitely many moves (Numbers written on chessboard are given, and we can choose k any number which will not violate given rules).

Solution 1.1: In our problem, it gives us "chessboard" word which is very big hint as chessboard is colored in 2 colors. It could say just board, and it would be harder problem as we would color board in 2 colors (it is called Coloring technique in combinatorics). So, why it is big hint? Let's see. In each move, we are adding the same number to 2 squares, one of which is white and one of which is black. If S_b and S_w denote the sum of numbers on black and white squares, respectively, then S_b - S_w is an invariant, because change of both S_b and S_w is same. Thus if all numbers are 0 at the end, S_b - S_w = 0 at the end and hence S_b - S_w = 0 in the beginning as well. This condition is thus necessary; now we will prove it is also sufficient which will solve problem. Suppose a, b, c are numbers in cells A, B, C respectively, where A, B, C are cells such that A and C are both adjacent to B. If a ≤ b we can add  - a to both a and b, making a 0. If a ≥ b, then add a - b to b and c. Then b becomes a, and now we can add  - a to both of them, making them 0. Thus we have an algorithm for reducing a positive integer to 0. Apply this in each row, making all but the last 2 entries 0. Now all columns have only zeroes expect the last two. Now apply the algorithm starting from the top of these columns, until only two adjacent non-zero numbers remain. These last numbers must be equal since S_b = S_w. Thus we can reduce them to 0 as well. Also, we can print list of moves with this algorithm.

Example 1.2 [Based on IMO shortlist 1994, C3]: Peter has 3 accounts in a bank, each with an integral number of dollars. He is only allowed to transfer money from one account to another so that the amount of money in the second one is doubled. Check if Peter can transfer all his money into two accounts. If so, print list of transfer.

Solution 1.2: We will prove it is always possible and provide algorithm for transferring money. Let A, B, C with A ≤ B ≤ C be the number of dollars in the account 1, account 2 and account 3 respectively at a particular point of time. If A = 0 initially, we are done so assume A > 0. As we perform any algorithm, the values of A, B and C keep changing. Our aim is to monotonically strictly decrease the value of min(A, B, C). This will ensure that we eventually end up with min(A, B, C) = 0 and we will be done. Now, we know a very simple and useful algorithm that monotonically reduces a number — the Euclidean algorithm. So let B = qA + r with 0 ≤ r < A. Our aim now is reduce the number of dollars in the second account from B to r. Since r < A, we would have reduced min(A, B, C), which was our aim. Now, since the question involves doubling certain numbers, it is a good idea to consider binary representations of numbers. Let q = m₀ + 2m₁ + …. + 2^km_k be the binary representation of q, where m_i = 0 or 1. To reduce B to r, in step i of our algorithm, we transfer money to account 1. The transfer is from account 2 if m_i - 1 = 1 and from account 3 if m_i - 1 = 0. The number of dollars in the first account starts with A and keeps doubling in each step. Thus we end up transferring A(m₀ + 2m₁ + …. + 2^km_k) = Aq dollars from account 2 to account 1, and we are left with B–Aq = r dollars in account 2. We have thus succeeded in reducing min(A, B, C) and so we are done.

I have one more interesting problem, again without solution. It is easier than 1.1 and 1.2, so I believe you can solve it by yourself! Anyway, I added hint in spoiler :)

Example 1.3: Several positive integers are written in a row. Iteratively, Alice chooses two adjacent numbers x and y such that x > y and x is to the left of y, and replaces the pair (x, y) by either (y + 1, x) or (x - 1, x). Prove that she can perform only finitely many such iterations.

Thanks for Kerim.K for providing us following problem and solution with invariant. I let you to solve this problem by your own.

UPD Example 1.4: There are n numbers on the board. In each move, Kerim selects two numbers (let them be a and b) and writes instead of them (that is, he deletes a and b and writes given number). After n - 1 moves, there will remain just one number. If all n numbers were 1 in the beginning, prove that last number will remain after n - 1 moves is greater or equal than 1/n.

So, it is end of tutorial. Hope you learned many things from this. If you have and doubts or suggestion, please declare it on comments. Thanks to AoPS for containing IMO shortlists and Pranav A. Sriram for his book "Olympiad Combinatorics".