[Japan 1998] 

Let n be a positive integer. At each of 2n points around a circle we place a disk with one white side and one black side. We may perform the following move: select a black disk, and flip over its two neighbors. Find all initial configurations from which some sequence of such moves leads to a position where all disks but one are white. 

If we can find a move that progressively converts one disk after the other to the desirable color, then we can go around the circle and stop at the one with the black. Why do we want a progression because we are only allowed to select one disk at a time and our goal is to ensure the same snd state configuration all around the circle. Moreover, if we are able to achieve a progression, then we don't have to concern the direction we traverse around the circle or the number of times we go around the circle, reassuring ourselves that each disk can be visited and tested.

Also note that while the question asks for all initial configuration, we can generalize it to saying if we can tackle one with an arbitrary number of disks that we can select to perform flips, then the strategy of using a progression will work for any number of such disks, in this case, black disks, around the circle.

Finally the termination condition is given by the fact that we stop short when there is only one black disk around the circle. If we had started out with all white, then there are no moves possible and would not contribute to the end goal, hence our assumption that there are arbitrary number of black disks around the circle to begin with holds true.

With the initial condition established, the progression required and the same final goal, we have the premise for an algorithm that can steadily decrease the number of blacks around the circle proving that such an algorithm will work.

All that the algorithm needs to focus on now is to make sure that each disk traversed in one direction  around the circle is flipped to white if it is not already white and stopping when there is only one black.

[Origin unknown]

Given 2n points in the plane with no three collinear, show that it is possible to pair them up in such a way that the n line segments joining paired points do not intersect.

Since the n line segments joining the paired points are not intersecting, let us draw n horizontal lines. They could be n vertical lines too but we pick horizontal so that it is easier to visualize.

Next assume that the linear segments are of equal lengths, then we have all the n points on one side collinear and all their paired counterpart also collinear.  This forms a ladder.

Since the points are not supposed to be collinear, we increase the distance between each pair gradually as we go up from the bottom of the n pairs to the top leading to a two divergent curves that are narrower at the bottom and flared up at the top. We can adjust the shape of the curve depending by evenly distributing the range between the n-points. If the curves flare up too apart, they tend to form semicircles. Instead we take the curves as divergent quarter circles and then space the n points on them.

Clearly we can picture the solution so the proof exists.

[Russia 2005]

100 people from 25 countries, four from each country, sit in a circle. Prove that one may partition them onto 4 groups in such way that no two countrymen, nor two neighboring people in the circle, are in the same group.

If no two countrymen are in the same group, then they are each in each group. That means that each group has one member for each country. Therefore all the four groups are identical

Now we arrange the four groups one after the other as a quarter circle to form a circle, no two countrymen are in the same group. However, no two neighboring people in the circle should be in the same group.

Assume that each group consists of members 1 through 25  where each number belongs to a country.

Then we interleave twelve from one group with twelve from a reversed group and leave the number 13 from one group at one end.

1 14 2 15 …12 25 13

Now we can create another similar group with the remaining halves and ending with 1 and 13.

We can do the same for the other two groups as we did with this pair. Now the ends of the semi-circles will be 1 and 13 for the group pairs

Now we connect the two pairs into a circle with the 1 and the 13 together thus leading to a solution.

[Bulgaria 2001] 

Problem: Given a permutation of the numbers 1, 2, …, n, one may interchange two consecutive blocks to obtain a new permutation. For instance, 3 5 4 8 9 7 2 1 6 can be transformed to 3 9 7 2 5 4 8 1 6 by swapping the consecutive blocks 5 4 8 and 9 7 2. Find the least number of changes required to change n, n-1, n-2, …, 1 to 1, 2, …, n. 
Solution: One way to do this would be to 
take the tail of the given descending series and start the block swapping
For eg. seq = 4321
Iteration 1: From tail, block size = 2 ^ 0 = 1
     4321
-> 4312
Interation 2 From tail, block size = 2 ^ 1 = 2
-> 1243
-> -> Repeated nested Iteration 1 1234
Similarly for 87654321
Iteration 3,  From tail, block size = 2 ^ 2 = 4
we start from above 87651234

-> Then we would get 12348765

->-> Repeat nested iteration 1 12348756

->-> ->Repeat nested iteration 2 12345678

This works well for even numbers. For odd numbers we would have one digit on the left still remaining to move over to the last. Therefore we will have to additionally swap it with one number each to the right until the last

Note that we are not able to apply the increasing subsequence dynamic programming to the above. That technique relies on the presence of an increasing subsequence in the given permutation so that those elements that participate in the increasing subsequence need not be moved at all and can remain in their positions while the others are exchanged to arrive in sequence with them.  In the above, every element is not at the  position it should be in and therefore has to move. Hence the minimum number of moves must be the length of the given sequence - 0 since there are no elements in increasing subsequence. But we are allowed to move as part of blocks. So we do this in a greedy way
The number initially moves by itself but after the first swap, it becomes part of an increasing sequence and hops the number of elements equal to the length of its current block.
Since the blocks can be formed only with the exchange of two adjacent sub-blocks, each hop is a multiple of two. This gives an increasing sequence of block lengths to hop and reduces the number of linear individual moves to the correct position.
The last element that remains is however a single element on the left that has to move all the way to the right when the sequence is odd. For this the last element the block size is unfortunately one and has to exchange positions with at most one element.

The total number of moves for any element is therefore a logarithm of the length of the sequence of elements

[Russia Olympiad 1961]
Real numbers are written in an m × n table. It is permissible to reverse the signs of all the numbers in any row or column. Prove that after a number of these operations, we can make the sum of the numbers along each line (row or column) nonnegative.

Real numbers can be positive, negative or just about any number that is not imaginary or hold special meaning such as infinity.

We make the following observations:
1) Note that the size of the board is not a square. So the conclusion doesn't depend on the size of the rows or the columns to be equal. In other words, the sum of the elements along each line can be assumed far greater than any one element.

2)When we pick a row and reverse its sign, one cell of all column changes sign. After this turn, each column sum still remains positive because the sum of the elements of the other cells is still positive
If we repeat this operation twice, the cells are returned to their original sign leaving the sum positive.
The same holds true if we substitute the column for the row in above. Even if the values changing sign is the largest in their respective orthogonal lines, the sum along these lines does not change sign from 1) above
So any number of operations on the same line does not alter the sign of the sum of the numbers along each line.

3)When a row or a column is picked alternatively and reversed once there is only one element that returns to the sign of its original. If the same row and column is reversed again and again only the sign of this element changes to negative. If we repeat this N times for this row or column pair, the sum will be greater than zero when N is even.

4) When we pick different rows incrementally and flip their signs, the sum of the numbers along each line becomes negative but as we do a number of these operations, the rows wraparound and we have all the rows positive again

5) when all the rows and columns both change , after every alternate turn at most 2m elements such as from the diagonals  will have flipped their sign unfavorably where m > n. Therefore, we will have the board again favorably 

A marker is placed at the origin of an integer lattice. Calvin and Hobbes play the following game. Calvin starts the game and each of them takes turns alternatively. At each turn, one can choose two (not necessarily distinct) integers a and b, neither of which was chosen earlier by any player and move the marker by a units in the horizontal direction and b units in the vertical direction. Hobbes wins if the marker is back at the origin any time after the first turn. Determine whether Calvin can prevent Hobbes from winning. 

Here Hobbes can return to the origin at any time by 'undoing' the displacements from the origin.
Suppose Calvin can moves include (a,b), followed by (-c,-d) by Hobbes and (e,f) by Calvin again . Then Hobbes can move back to the origin by (a+e-c, b+f-d).
We observe the following:
 1) the Hobbes tries to move back towards origin while Calvin tries to move away.
 2) none of the moves repeat that is a, e, c are all distinct and so are b, d, f
 3) for every positive move that Calvin makes, there is a negative move that Hobbes can make which is distinct and non-repeating. Hence the origin is a P-Position. A P-position is one where the player who has just played can force a win. A position is called an N-position if the player whose turn it is can force a win and Hobbes uses it to his advantage. Therefore Calvin must find a P position other than the origin.
 4) when the moves are strictly horizontal or strictly vertical, Hobbes cannot reset back to the origin because one of the co-ordinates is 0 and it will have to be repeated to get back to the P-position.
Therefore Calvin can find P-positions by either moving horizontally only or vertically only
For example, Calvin can move (1,0) in the first move and Hobbes is forced to move  in the vertical direction, say (-1, -1), then Calvin can undo the vertical direction by flipping the marker to the opposite side with (2,-2) In other words Calvin forces two of the diagonals to be P-positions and maintains his moves to these diagonals with non-repeating numbers.
5) Since the numbers are incrementing by 1 and Calvin uses up both the positive and negative of the same integer, Calvin has a winning strategy.
6) the axes can be the players N positions since moving to the axes can let them use the diagonal.
7) once both players arrive at the diagonal they can remain on the diagonal  by alternating

Example 10 [China 2010, Problem 5] 
There are some (finite number of) cards placed at the points A1, A2, …, An and O, where n ≥ 3. We can perform one of the following operations in each step: 

(1) If there are more than 2 cards at some point Ai, we can remove 3 cards from this point and place one each at Ai-1, Ai+1 and O (here A0 = An and An+1 = A1) 

(2) If there are at least n cards at O, we can remove n cards from O and place one each at A1, A2, …, An. 

Show that if the total number of cards is at least n2+3n+1, we can make the number of cards at each vertex at least n + 1 after finitely many steps. 

Solution : The total number of cards stays the same.

(a) if we balance out the cards at each Ai, then there won't be disproportionate cards at any one point.
(b) We can make each of the Ai's have 0, 1, or 2 cards.
(c) from observation b, we can have 1,2 or 3 cards from the stage where they have 0,1 or 2 cards, by applying operation 2.
(d) based on observation c, we can make each of the Ai's have 1, 2, or 3 cards. Suppose x of the Ai's have one card, y of the Ai's have 2 cards and z of the Ai's have 3 cards. The number of cards at O is (n2+3n+1)-(x+2y+3z) Since (x+y+z) = n, the latter component is <= 2n if x >= z and O will have n2+n+1 cards. Then all of Ai's will now have at least n+1 cards and O will have n2+n+1-n2 cards and we are done.
Based on observation d(), we can start with points on the perimeter having 1,2 or 3 cards and ends in a position having 1, 2 or 3 cards but the number of points having 3 cards is not more than those with 1 card. We can do this by ensuring that any two points having three cards has a point with one card in between.

We can do this by applying 1 on all consecutive 3's  to transform the set (x,3, ... 3,y) to (x+1, 1, 2 ... 2, 1, y+1) and there are no adjacent 3's. Now suppose there are two 3's with only 2's in between them like (x,3,2,2, ... 2, 3, y).  Then we can do operation 1) on the first 3 to covert its adjacent to 3 and then again to the next adjacent 3. This we can please repeat as long as there are no adjacent 3's. 

IMO 2007
In a mathematical competition some competitors are friends; friendship is always mutual. Call a group of competitors a clique if each two of them are friends. The number of members in a clique is called its size. It is known that the size of the largest clique(s) is even. Prove that the competitors can be arranged in two rooms such that the size of the largest cliques in one room is the same as the size of the largest cliques in the other room.
Let M be one of the cliques of largest size. It is given that the largest size is even, therefore abs(M) = 2m. Let's put all of them in the same room A and all the others in room B. Now if c(A) and c(B) denotes the size of the largest cliques in rooms A and B at a given point in time. Since M is a clique of the largest size, we initially have c(A) >= c(B)
Now our task is to balance them and so we move members from room A to room B. As we break the clique membership in room A, we decrease its size by 1. In the other room the clique size may or may not increase by 1. In other words, it may increase by at most 1. Therefore while the clique size of A is greater than B, keep sending one member to room B.
The Balance happens when c(A)<=c(B)<=c(A) +1. In other words they are just about the same or exactly the same. At this point the size of the clique in room A has to be at least m. We can argue the contrary and see that we prove this. If there were less than m in A, then there would be m+1 in B and at most m-1 in room A, implying c(B)-c(A) >= (m+1)-(m-1) = 2. But we just now argued that they should be just about the same or exactly the same when we stop balancing.
if c(A) = c(B), we are done. At this point the required proof holds already.
So far we have covered the cases when the they are unbalanced or overbalanced or exactly the same.
All that is left now is when they are just about balanced which is the case when the clique sizes in the two rooms differ by one member.
Let us say c(A) = k and c(B) = k + 1. Now if there is a competitor in B who is also in M but is not in the biggest clique in B then by sending her to A we increase the clique size there by 1 but do not affect the clique size of B. At this point again we are done.
Now suppose that there is no such competitor. This case remains to be handled. For this case, we take a member from the clique of B and send it to A. The clique size reduces in B but it does not increase the size of A. How do we guarantee that ? Well suppose there is no competitor in B who is also in M but not in the biggest clique of B This would mean that the all the members of the intersection B and M would be in the cliques of sizes k+1 That means the competitor would have no membership in cliques of A and therefore no increase in the size of A.