In the previous post we brought up a question as follows:
[Czech and Slovak Republics 1997]
Each side and diagonal of a regular n-gon (n ≥ 3) is colored blue or green. A move consists of choosing a vertex and switching the color of each segment incident to that vertex (from blue to green or vice versa). Prove that regardless of the initial coloring, it is possible to make the number of blue segments incident to each vertex even by following a sequence of moves. Also show that the final configuration obtained is uniquely determined by the initial coloring.
Lets take the four sided square now as n = 4. At each vertex we have two edges and a diagonal incident on it. Let us say the edges are alternatively blue and green and the diagonal is also alternatively blue and green. We again have the same condition that at a vertex, we have a simple majority of one color or all colors the same.and there will be another vertex with the colors switched.
 Let us say the simple majority was green and the number of blue segments to this vertex is odd.
The initial configuration is therefore
X G r e e n Y
G B         G B
r     l       r    l
e       u  e     u
e       e  e     e
n    n       x   x    
Z B  l   u  e W

Where X, Y, Z and W are vertices. As noted earlier vertex X has 1 blue while W has all three blues.
If we make a move at X, the two greens become blue and the diagonal XW becomes green leaving leaving the total count of blues even at any given vertex.
The total number of edges in a square is 4 and with diagonals the count is 6 an even number, the blues and greens can be divided in sets (1,5)(2,4)(3,3). Therefore permitting them to switch the colors at a vertices will not add or subtract the total count but  it can be made even because there will be odd number of vertexes with opposite number of colors. While the initial coloring configuration is unique and the flipping sequence to make the coloring at a vertex even and blue is also unique.
Since we verified for both n = odd and n = even, we can state the same for all n>= 3. Formal proof may be shown by induction method.

We conclude the review of the book "Anticipate" with the following summary:

The final part is about our visionary self and how to improve it. 

This section asks you to begin by trying to write your own obituary so that we can gain clarity about our own beliefs and values as a critical step. Another exercise in this way would be to ask a friend to interview you and respond with honest answers. Questions could include say, describe three different situations in which you were truly at the best.  

Then the section asks us to lead by example. Being mindful of these values helps us observe what may have been overlooked.  Another practice is to deliberately break your normal pattern of working, communicating, thinking, reacting or responding. Get radical exposure by engaging with folks who are different from us. And finally try opinion swap such as adopting the opinion of someone you don’t necessarily agree with. 

This is where we use the power of language. We use verbs to carry sentences. We can use a predefined list of verbs that attract attention. Similarly show picture. This evokes imagination and helps them envision a different world.  Also metaphors make the message stick. If you give an example with a metaphor, it’s much easy to relate to. Likewise analogies can be drawn to something that is actionable. If you say you want something to be the ivy league in its industry, it becomes clearer. Finally, stories inspire. They are catchy and heighten our natural curiosity. 

#Olympiad_problem
[Czech and Slovak Republics 1997]
Each side and diagonal of a regular n-gon (n ≥ 3) is colored blue or green. A move consists of choosing a vertex and switching the color of each segment incident to that vertex (from blue to green or vice versa). Prove that regardless of the initial coloring, it is possible to make the number of blue segments incident to each vertex even by following a sequence of moves. Also show that the final configuration obtained is uniquely determined by the initial coloring.

Let us take the example of a triangle. Since there are three vertices a, b and c in a triangle , any vertex has two edges incident on it. It doesn't have any diagonals. If we choose edges ab and ac to be blue and bc to be green as an initial configuration, then b and c don't have any even number of blues.

If we flip the color of edges incident on b, then ab becomes green and bc becomes blue, leading the colors of c to be even and blue.

If instead we flip the color of edges incident on c, the edges of b become both blue.

Since a already had even number of blue edges to begin with, all the vertices of the triangle have each been able to make their incident edges blue.
The total number of edges in a triangle is 3 and because its an odd number, the blues and greens are divided unequally. Therefore permitting them to switch the majority with each move. Futhermore the majority can be even. Lastly all the moves at a vertex can be the same for all the vertices since they are all the same. But the initial coloring configuration is unique and therefore the flipping to make the coloring at a vertex even and blue is also unique.

A book review of Anticipate – by Rob - Jan de Jong.

In order to be successful with a campaign, leaders must have a vision argues Rob-Jan de Jong in his book Anticipate.  Heis a strategy and leadership expert and he says usually a vision is not compelling or one that inspires or energizes their people. Vision is not exclusive to anyone.

To develop vision, one must sharpen two skills – The first is the ability to see things clearly – spotting the first hints of change on the horizon. The second is the power to connect the dots – turning those clues into a gripping story.With these skills, we will be able to frame the big picture, provide a direction and communicate our vision. When we anticipate change before our competitors, we create enormous strategic advantage.

The author leads us into this self-help book with the following structure:

Find the purposes and ingredients of a personal vision

See things clearly and connect the dots

Find core values to develop our vision.

A company’s vision is different from a personal vision. We focus on the latter.  A personal vision improves our leadership abilities because we are exciting the people to look to us for leadership.

Powerful visions have four fundamentals:

A vision shows the path forward: A vision provides guidance and direction to what lays ahead

A vision stretches the imagination: It takes us beyond the obvious to the unknown.

It changes the status quo and breaks through existing paradigms forcing us to tap into unseen opportunities

It energizes and mobilizes by galvanating those we lead.

In order for a vision to be persuasive, it must have emotional and intellectual appeal. When we use our imagination, we lend pathos to our vision so that its more engaging. For example, the idea of a pizza slicer evokes expectations of a speedy delivery, frozen pizzas and specialized utensils. It tethers some ideas for customer satisfaction.

Sometimes we can even use others as an example to think differently. For example, the expression WWGD stands for what-would-google-do? Start by selecting a number of iconic companies that everyone has strong brand association with.

To grow your visionary capacity, we should have the ability to see things clearly – the first signs of change often manifest as random noise or faint warning signals. And second, the ability to connect the dots to frame a bigger picture.

The author mentions categories for where we may stand with respect to these abilities: These are :

Followers, Trend Hoppers, Historians, the visionary etc.  He warns however that we are not trying to predict the future. Instead we are developing an increased awareness to push the future in a direction different from the one we currently see.

The author developed his own technique called a “Future Priming” to help executives improve their ability to see things early. Its about writing our own “FutureFacts” which is a manifestation of a possible changing reality.

And he mentions four simple rules to do this practice:

Scope for relevant and time – it should be just wide enough to include relevant signals.

Don’t make your own company – part of your future fact.

Explore the area between the conventional and the absurd by asking more “what if”

Describe an event not a trend – it may have memorable hooks to news events that transpire.

The second aspect to vision other than seeing things clearly is to connect the dots.

To connect the dots means to frame a coherent story for the path ahead. We should avoid what the author calls as Frame blindness and overconfidence.  He says make uncertainity a part of your vision. Embrace it instead of trying to quell it or to get rid of it.

The final part is about our visionary self and how to improve it.

#codingexercise
Int flip_disks_around_circle(disk disks,  int start, int count){
If start > count  or one_black_left return 0;
If disks [i] .color == black flip_adjacents (i);
Return flip_disks_around_circle (start+1);
}

In the previous post about the following question:

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. 
we proved the premise for an algorithm.
Now let us see the steps involved. 
When we select a disk O that is black, we want to convert it to white and proceed to the next one in a given direction say counterclockwise on the circle.
Let us say the neighbors of this selected disk O are X and Y. When we flip X and Y, both could have become black but we can ignore X since we move in the direction of Y leaving X to be the one to satisfy termination condition. O is unchanged and black.
Now Y is black, we proceed flipping, this will make O white while Y's neighbor in the chosen direction say Z could may also become black. Thus O has become white but Y and Z are black.  In order to flip Y we select Z and flip Y and the disk following Z thus making Y white.  This is acceptable since Y and Z are both black. but what if Z is white. In this case both O and Z as Y's neighbors are white and flipping Y would result in undoing what we did with O to begin with. But let us say this undoing O is ok given that Y has now become the new O. In other words we pushed O forward by one position while leaving blacks in our wake. So let us make O black again and Z black.
Now we have X O Y Z black
Now we know that O was not only black disk in the circle otherwise we would not have commenced flipping. Besides we let X be the termination condition should it have become black with our flipping.
Since we will have to skip Y if we don't want to undo O, we might as well have skipped O.
Therefore the only condition in which we can move forward is the configuration in which O and Z are both black.
Moreover since we want the propagation to finish at or before O, the neighbour before X must also be black. In other words,  the configuration where such moves can propagate and leave behind one black is one where black and white alternate. 

[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.


 

There are 2n people seated around a circular table, and m cookies are distributed among them. The cookies can be passed under the following rules:

(a) Each person can only pass cookies to his or her neighbors

(b) Each time someone passes a cookie, he or she must also eat a cookie
Let A  be one of these people. Find the least m such that no matter how m cookies are distributed initially, there is a strategy to pass cookies so that A receives at least one cookie.

Let us denote the people with symbols such as A-n, A-n+1, A-n+2, ...A-1, A0, A1, ... An where A-n and An are the same person since it is a circular table.

A weight 1/2^abs(i) is assigned to each cookie held by a person Ai. Thus for example if A3 passes a cookie to A2, the cookie's weight increases from 1/8 to 1/4. Since A3 must also eat a cookie of weight 1/8 in this step, we see in this case, the sum of the weights of all the cookies has remained the same.  The sum of the weight of all the cookies has remained the same. If Ai has ai cookies for each i, then the total weight of all cookies is Sum of i from -n+1 to n is ai / 2^ abs(i).

Whenever a cookie is passed towards A0, (from Ai to Ai-1 or the reverse direction), one cookie is eaten and another cookie doubles its weight, so the total weight remains invariant. If a cookie has passed away from A0, then the total weight decreases. Thus the total weight is indeed a monovariant.

If m >= 2^n, we can always ensure that the A0 gets a cookie.  Any of the directions could be chosen but it should not pass A0 because the weight would reduce. In each step therefore a cookie progresses towards A0 from either side of the diametrically opposite end. We use a new quantity to indicate the direction. Let W+ be the sum of the weights of the cookies held by A0, A1 ... An and let W be the sum of the weights of cookies held by A0, A-1, A-2 ...  and we can suppose W+ >= W=. Then this suggests An can pass cookies to only An-1 and we use only this semi-circle containing non-negative indices, since this is the semi-circle having more weight. In each step, as m any cookies are passed as possible to An-1 and similarly forwarded. This works only if and only if W+ is > 1 which is necessary as W+ is a monovariant.
To show that this is sufficient, we note that the algorithm leaves the W+ an invariant.  The algorithm terminates when we cannot pass anymore cookies from any of the Ai with i positive, and A0 does not have any cookies.A1, A2, ... An all have at most one cookie at the end. If they had more, they would eat one and pass one and the algorithm would not have terminated. Then W+ would sum upto 1/2 + 1/4 + ... + 1/2 ^ n < 1, contradicting the fact that W+ is an invariant and >= 1. Thus W+ >= 1 is  a sufficient condition for the algorithm to work. Finally we prove that we indeed have W+ > 1  We assumed W+ > W-. Now simply note that each cookie contributes at least 1 / 2 ^(n-1) to the sum(W+ and W-), because each cookie has weight at least 1/2^(n-1) except for cookies at An. However, cookies at An are counted twice since they contribute to both W+ and W-, so they also contribute 1/ 2^n-1 to the sum. Since we have at least 2 ^ n cookies, W+ and W- >= 2, so W+ >= 1 and have proved that this is both necessary and sufficient.

Note that the use of a geometric progression ensures that the cookie can be consumed and passed along and using the property of the sum of this progression we bound it at the diametrically opposite end of the table because that suffices to have everyone get a cookie.

The criteria for weights on a semi-circle to be more than 1 is therefore of a consequence of the above.

IMO Shortlist 1994

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 latter is doubled. Prove that Peter can always transfer all his money into two accounts. Can he always transfer all his money into one account? 

Let A, B, C be the number of dollars in the account 1, account 2 and account 3 respectively and A <= B <= C. If A = 0, we are done. At any time we want to reduce min(A,B,C) to the point where it is 0. The values of A, B and C can keep changing

Euclidean theorem monotonically reduces a number by using form B = qA + r with 0 <= r < A. We use this form. With this form if we can reduce B to r then we are done. Since r < A, we would have reduced min(A,B,C) which was our aim.

The question however says we have to double so we use binary representations. Let

q =  2M^k + ... + 2M1 + M0 be the binary representation of q and where Mi is 0 or 1. To reduce B to r, in step i of the algorithm, we transfer money to account 1. The transfer is from account 2 if Mi-1 = 1 and from account 3 if Mi-1 = 0.  The number of dollars in the first account starts with A and keeps doubling in each step. Thus we transfer Aq dollars from account 2 to account 1, and we are left with B-Aq = r dollars in account 2. At this point we have reduced min

The answer to the last question is that it is not possible when the number is odd.

Lets try this out with sample numbers

We have accounts with 2, 5, 16

B = 2* A + 1

so q =2 and it can be written as 0 + 2 * 1 for the binary representation of 2

We transfer Aq = 2 * 2 = 4 dollars to 1 and now have 6, 1,16

Now A, B, C has changed and we have A = 1, B= 6, C = 16
now B has q=6 and r = 0 and since m1 was 1 and m2 is 1, we have the transfer again from B.
 This leaves us with A=0, B=7 and C=16.

Note that we cannot reduce any further.

Today we discuss another Olympiad problem.
[IMO Shortlist 2009]
Five identical empty buckets of 2-liter capacity stand at the vertices of a regular pentagon. Cinderella and her wicked Stepmother go through a sequence of rounds: At the beginning of every round the Stepmother takes one liter of water from the nearby river and distributes it arbitrarily over the five buckets. Then Cinderella chooses a pair of neighboring buckets, empties them into the river, and puts them back. Then the next round begins. The Stepmother’s goal is to make one of these buckets overflow. Cinderella’s goal is to prevent this. Can the wicked Stepmother enforce a bucket overflow?

Let us take the volumes as V1, V2, V3, V4 and V5. Cinderella (C) can only empty adjacent buckets. If the alternate buckets are more than 1 liter, she will not be able to empty both. Therefore she prevents this condition. For each i = 1 to 5, C must ensure that Vi + Vi+2 is at most one on each of her turn. She maintains this 'good' state.

The good configuration enforces return to good state. For example, if two buckets are empty, V4=V5=0, Then V1 + V3 <= 1 and V2 <= 1 because V2 + V4 <= 1 After the step mothers turn,  V1  + V3 + V4 + V5 <= 2. Therefore either V5 V3 <=1 or V4 + V1 <=1  So C empties both V1 and V2 and the new configuration is still good V4 <=1 and V5 + V3 <=1

Since at the end of each turn for C, we have a good configuration, C has a winning strategy.

####################  Paper Review #####################

Today we discuss "Ontology based text summarization - The case of Texminer".
This paper talks about Texminer which does summarization by a combination of summarization techniques.Before delving into the techniques, it might be a good reminder to go over the summarization techniques.

One technique is to use the structure of the discourse to generate abstracts. The Rhetorical Structure Theory, for example, attempts to identify the internal structure of the text and the relations of the discourse formed within it, giving priority to the nuclear components of these relations.On the other hand, Marcu segments the text into small units of discourse. He then proceeds to build a rhetorical structure in the form of a tree by analyzing the set of relations that exist  between the units. Once the discourse structure has been created, he assigns weight and an order to each element of the structure. - the higher the element within the structure the greater its weight.

Different ways of using the text discourse structure has been shown. Some have used the rhetorical status of affirmations contained in documents to identify their internal structure. The main contribution of these authors lies in the algorithm that deals with the non-hierarchical structure : given seven fixed catagories (aim, textual, own, background, contrast, basis and other) it is capable of distributing the contents of the articles within each category.

Another way has been to use templates to generate summaries and retrieve information.  This technique can only be applied when the text is previously structured. Information retrieval systems include Fies that extracts financial information from digital articles.

Mateo combined superficial with deep structure analysis to enhance the coherence and cohesion of the abstract. Alonso and Fuentes for example combine lexical chains plus the rhetorical and argumentative structure, derived using discourse markers.

Using combination of complex linguistic techniques, Aretoulaki developed a model for automatic summarization that selects sentences using content features of a pragmatic and rhetorical nature, obtained by means of superficial linguistic analysis such as the Theory of Speech Acts, the Rhetorical structure Theory and the theories centered on cohesion and coherence.

Automatic production of abstracts was initially based on statistical methods. in the wake of research by Luhn and now uses diverse methodologies. With the extraction of terms or strings of significant words, systems build discourse models. These systems have been used to identify rhetorical structures highly related with the content of the documents and their organizational scheme.

The growth of cognitive science has allowed the incorporation of semantic-conceptual models.Together with the use of knowledge bases, these models vastly improve the process of summarizing texts on a specific topics.

The demand for domain knowledge has seen exceptional growth recently.  Models for extraction and disambiguation of text has changed recently. It may even have become harder to find tools to help with such narrow domain texts. The lack of specific dictionaries, the absence of a defined theory and the dire need for professionals in the sector to have summarization tools to carry out their work has become pervasive. Documentation, Terminology and Natural Language Processing (NLP) indicate that there is a demand here in this narrow-domain texts.

This is where TexMiner may help solve the problem. It is based on the conviction that summarizing texts within a specialized domain requires a model capable of processing its semantic and socio-cognitive components.

The socio-cognitive user paradigm aspect of TexMiner takes into account the historic, social and cultural factors. These techniques consider a domain as the mindshare in terms of concepts, terms and knowledge from a community.
It uses ontologies as algebraic descriptions of a conceptual network in which the elements are binary relations established through concepts.
Lastly it uses three agents for processing information.
The first is a reading agent that reads the documents and labels them in XML. Here the goal is to discern if a document belongs to a particular domain based on the count of words that fall in the domain.
The second is a summarization agent that carries out automatic tagging of the syntactic discourse structure of the text. The design of the tags is governed by
- the sequence in which the levels are tagged in practice
- the symbols used to denote cohesive elements of the text, and
- the presence in the text of geographic elements, verbs statistical data formulae and processes.
The last agent is the Information retrieval agent. Texminer allows for the searches to be made through the ontology, as well as the lexical databases developed to take advantage of the functionalities of summaries for the purpose of text retrieval.

User API or Account Management

Most internal organizations maintain their registered users in a database. As an identity provider, this suffices to maintain the current users However, different applications and services may need read only access to the registered users, their id, name and email with or without the direct access to the database. This is typically because the applications work with a single database at any time not many databases at the same time. If the database, happens to be different some form of dependency injection may be required for the application to continue with the assumption that it can reach the list of registered users.

Active Directory is a superset of all such users and is the final authority for knowing if the user is a valid entity or not.  To check if the registered user is still current, we can defer to the AD. However, AD does not come with its own API other than LDIF.

Companies often have API wrappers around the AD to facilitate such function as creating and deleting groups. But users listing is not necessarily provided by an API.

Therefore an API access to registered users should  be no surprise and a way to facilitate the addition or deletion of users may very well be required in certain cases.

It may even be helpful to separate out read-only access from read-write access to this users list.

As an example,

class UserViewSet(generics.ListAPIView):

    serializer_class = UserSerializer

    queryset = User.objects.all()

The Read-Write access can include checking for existing users and adding a new user or deleting an existing user.  The attributes for user information typically involve status, email, full name, password,  created, modified etc.  There may be additional qualifications such as type or group, comments, last login time etc. It must be noted that we assume the registered users table to be unique for the application or organization we are considering. That is why such a centralized table requires an API for programmatic access. If the table can be different for different applications, then there is no need to write an API for each and instead import it directly  into the database. Said another way, we are enforcing the sharing because we want to keep one master copy up to date instead of relying on copies, replicate, merge and sync between databases.

APIs in service oriented architecture model are very useful for exporting such data to be used in different applications or services. 

[IMO Shortlist 2004]
Problem: A and B take turns writing a number as follows. Let N be a fixed positive integer. First A writes the number 1, and then B writes 2. Hereafter, in each move, if the current number is k, then the player whose turn it is can either write k + 1 or 2k, but no player can write a number larger than N. The player who writes N wins. For each N, determine who has a winning strategy.

Solution:

Step 1) if N is odd, A can win. This is because A can always write an odd number after which B has to write an even number and N becomes a P position

Step 2) All even numbers greater than N/2 are P-positions. This is because until N/2, we have the ability to double the number but not beyond that otherwise it will exceed N. After N/2 both players will have to increment the number by 1.

Step 3) If N = 4K or N = 4K + 2, then K is a P-position. This is because if X writes k, Y must write k+1 or 2K Then X writes 2k + 2 if Y writes k and X writes 4k if Y writes 2K. X has thus written an even number greater than N/2 and by step 2, X wins. X can be either A or B and Y is the other of the two.

Step 4) If X has a winning strategy for N = k, then X has a winning strategy for N = 4k and N = 4k + 2
Proof: Consider a game where N = 4K or 4K + 2. Based on the previous step, the goal can now be modified to write K first. How can player Y prevent X from writing K ? The answer is to jump over K. After k/2, the number can be doubled. But X can double the number again resulting in an even number that is at least equal to 2(k + 1) > N /2. So X wins by step 2.

The recursive method for defining the answer for even N is as follows:
The answer for N is the same as that for floor(N/4). To convert this recursion into an explicit answer, write N in base 4. The floor(N/4) is the same as removing the last digit when N is written in base 4. We keep removing the last digit and the resulting numbers will all be winning for the same player by the same recursion. If at some point the number obtained is odd, then A wins for this number and hence A wins for N. If the N has only 0s and 2s in its base 4 representation, then with recursion we end up with number 2. B wins in this case and therefore for N.

The moves for A involve :
Write 1 at the beginning
check if B's move has exceeded N
if N is odd, write the next odd number
if N is even and equal to 4K or 4K+2, recurse floor(N/4) as say c till you get c as odd or 0 or 2
if c is odd, then arrive at c by playing odd
if c is 0, then keep playing odd
if c is 2, then declare B winner

The moves for B similarly involve
Write 2 at the beginning
If N is odd, write the current number + 1 or current number * 2
if N is even, follow the same strategy as A

B wins only when the recursion stops at 2.  Otherwise A wins with winning strategy as above.