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