Today we discuss some more Olympiad problems:
Italy TST 2009
A and B play the following game. First A writes a permutation of the numbers from 1 to n, where n is a fixed positive integer greater than 1. In each player’s turn, he or she must write a sequence of numbers that has not been written yet such that either:
a) The sequence is a permutation of the sequence the previous player wrote, OR
b) The sequence is obtained by deleting one number from the previous player’s sequence
For example, if A first writes 4123, B could write 3124 or 413. The player who cannot write down a sequence loses. Determine who has  a winning strategy.
Let us focus on the endgame. when n = 2, B wins after A's first move B deletes the number 2 and is left with the sequence {1}. Then A has no move. 
With this end game, we now create a progression using induction  Suppose B wins n = k, then we want a strategy for n = k + 1 B's aim is to make A be the first player to delete a number from the sequence. Then from this point the game is reduced to a game with k numbers. How to do this, for every sequence that A writes for k+1 numbers, there will be  a permutation that A has not written because permutations are factorial(k+1) which is even. For example, one such sequence would be to write it backwards.
Another Olympiad question:
The Y2K Game is played on a 1 × 2000 grid as follows. Two players in turn write either an S or an O in an empty square. The first player who produces three consecutive boxes that spell SOS wins. 
If all boxes are filled without producing SOS then the game is a draw. Prove that the second player has a winning strategy.
Let us say an empty square is bad when it leads to the formation of the given pattern SOS.
The claim here is that an empty square is bad only when it occurs in between S empty empty S formation that we denote by S__S.
The claim follows from the configuration that an empty square is bad when it is flanked by an S on one side and an empty on the other. Clearly both the empty squares above is bad.

Today we discuss a Forrester report title Cloud Platforms that will turn Enterprise Architecture Inside Out

The report says that cloud services have been adopted in an adhoc fashion, driven by the opportunity and expediency more than by strategy, hence this report provides a template to develop cloud architecture to balance the needs to be agile while managing risks.

Cloud services are now being added under the mandate to provide competitive edge. This introduces risks to security and business models, the potential for vendor-lockin and other challenges. The trouble with cloud services are that unless they are specifically designed, they get used arbitrarily. Architects therefore spend time developing clear guidelines for cloud adoption and use. And they must develop them differently from the on-premise centric world.  This report discusses the risks associated with the explosion of the cloud services. It proposes the use of architecture zones to manage the cloud agility and risk.  Moreover, cloud is an opportunity for Enterprise Architect (EA) leaders to reinvent enterprise architecture.
Let us take a look at some of these challenges and risks:
Public cloud service providers have unstable pricing models. They regularly decrease the prices of highly visible services but also add new services that increase the costs to enterprises. Architects previously were not concerned with software licensing.
Vendor lockin versus business flexibility - EA pros have always been concerned with vendor - lockin. There are very few examples that prevent this in the cloud as compared with on-premise  Standard and open-source  products like Cloud Foundry and OpenStack help promise to insulate customers from lock-in but are still untested.
The trouble with cloud services is that if you bend it to your needs, you have more pain than the on-premise world. Customization is not what the cloud services provider was pushing and if you do decide to go with it, the CSP was probably not a truly offering cloud services to begin with.
Security and confidentiality concerns - even though major applications and services are building on public cloud, architects are rarely involved from the start to determine the security policies, procedures and controls.
If you design your own private cloud, guidelines for security  may have to be explained even more.
The right approach for the EA depends on the CSP business models.
Hosting companies that focus on infrastructure as a service and hybrid is one such model. Most CSPs make their money by renting infrastructure capacity.  They often invest more in capital equipment, infrastructure administration, and software management. For example RackSpace differentiated itself early on as an IaaS provider.
Integrators that focus on delivering the solution and not the means is another such model.  This is typically the consulting company at the core.  They have strongest background in managing, customizing, and integrating commercial off-the-shelf COTS software.  The Accenture duck-creek  suite, supported on Microsoft Azure is a good example.
Software companies that put their solution front and center. Independent software vendors (ISV) led cloud services providers have their own applications, middleware, tools or other code.  Their model centers on licensing and renting of this IP and the expansion of their software portfolios.
Pure cloud CSPs that focus on subscription growth is another such model. They shift the focus to low entry points and pay-per-use business models, but long term customer commitments are driving these vendors. Leading SaaS vendors are massively multi-tenant.
This paper proposes the use of architecture zones. A simple template with well defined zones can help EA professionals to provide business related guidance.
The core business zone maintains the on-premise status quo - they provide the administrative backbone of the organization. This is considered the systems of record.
The intermediate zone is where change is less dynamic.  Systems of automation and systems  of design are  appropriate for an intermediate zone. This is considered the systems of automation.
The business agility zone is where the change is the norm.  Innovative new capabilities using cloud technologies enters this agility zone. This is considered the system of insight.

A and B get an unlimited number of identical circular coins. A and B take turns placing the coins on a finite square table, in such
a way that no two coins overlap and each coin is completely on
the table (that is, it doesn’t stick out). The person who cannot
legally place a coin loses. Assuming at least one coin can fit on the
table, prove that A has a winning strategy.
Like in the previous problem the winning strategy can be defined if there is an advantage for the final move that can be determined before hand. We can do this by assuming pairs of moves to be copies of each other bit the beginning and last moves to be different. By copies, we mean that if one player puts a coin on the table, then the other player puts the coin on the symmetrically opposite side of the table. The one place that is unique is the center and that should be the first move.

Tic Tac Toe for mathematicians:
On a 5 x 5 board, A and B take turns marking squares. A always writes an X in a square and B always writes O. No square can be marked twice. A wins if she can make one full row, column or diagonal containing only Xs. Can B prevent A from winning ?
The answer to this question is yes. We will see how if we use the cheatsheet in Pranav Sriram's explanation. The board is marked as follows:
5  9  11  9  6
8  1   1  2   7
12 4      2  12
8  4   3  3   7
6 10 11 10 5

Since each number from 1 to 12 appears in 2 squares, B can ensure that he always marks at least one square of each number ( if A marks an X in a square with number i, B puts an O in the other square marked i). Each row, column and diagonal contains a pair of squares having equal numbers. This equal number guarantees that B will make a mark in every row, column and diagonal thus preventing A from winning.
The numbering may strike one as having come out of a wild permutation guess but in fact,  this is one of those solutions that has a very intuitive explanation.  There are 5 rows,  5 columns and two diagonals for a total of 12 winning lines.  We can only make 12 pairs of numbers. since there are twenty five squares. With a pairing strategy that keeps one pair in each row, column and diagonal, we can use a similar number as shown above. We can start with the inner 3 x 3 square, covering its border and then fill the outer perimeter Furthermore, the game of Tic Tac Toe can be generalized to getting k squares in a row on a m x n board In all these cases, the player B can  have a similar winning strategy. However whether the player making an opening move has a winning strategy is an open problem.

There are other games also possible with the same 5 x 5 board and two players. For example, take the problem that appears in IMO shortlist 1994
A and B play alternatively on a 5 x 5 board. A always enters a 1 into an empty square, and B always enters a 0 into an empty square. When the board is full, the sum of each of the nine 3 x 3 sub board is calculated and A's score is chosen as the highest among them all. What is the largest score A can make, regardless of the responses of B
The intuitive answer here is the score of 6. How do we say so ? Because for every move that A makes in a sub board, B can pair a 0. This takes up two sets of rows leaving the fifth row untouched in the board. Since any three by three sub board contains at least two of the row pairs, B can force at least three zeros leaving the maximum score for A to be 6.

USAMO-2004

Alice and Bob play a game on a 6 x 6 grid. On his or her turn, a player chooses a rational number not yet appearing in the grid and writes it in an empty square of the grid. Alice goes first and then the players alternate. When all of the squares have numbers written in them, in each row, the square with the greatest number in that row is colored black. Alice wins if she can then draw a path from the top of the grid to the bottom of the grid that stays in the black squares, and Bob wins if she can’t.(A path is a sequence of squares such that any two consecutive squares in the path share a vertex). Find, with proof, a winning strategy for one of the players.

The intuition here is that any path from top to bottom can be broken with a diagonal that does not comprise of black squares. Since there are only two such diagonals and they are symmetric, the winning strategy is simply the one that can maintain a diagonal of non-black squares. To form such a diagonal the opponent must be forced into the adjacent corners from each diagonal tip. In other words the black squares occupy the vicinity of two corners opposite from each other without meeting in the center where the diagonal of non-black runs through. How does Bob force the opponent into these two corners and maintain his winning strategy ? For any given row, Alice can either choose a small number in which case it cannot be a black or a big number in which case it will be a black. Since Alice is picking a square with her number, we can choose the opposite -  a big number for her small or a small number for her big forcing her number or ours to be a black and determining the position of the black in the row. Given that we already have mapped where the blacks should fall, we can play this kind of moves for all rows, thereby clustering the blacks around two corners without meeting each other in the center where the diagonal runs through.

Let us try a different problem now.
Saint Petersburg 1997 The number N is the product of k different primes (k ≥ 3). A and B take turns writing composite divisors of N on a board, according to the following rules. One may not write N. Also, there may never appear two coprime numbers or two numbers, one of which divides the other. The first player unable to move loses. If A starts,who has the winning strategy?
Solution: since we want to determine the win, we only have to split the number N into two prime factors p and q and write down pq.  This way we can reserve one move at the end for the person starting the game which is A. Then as the other player writes a number qm, A can write qn in a move that copies the attempt of B. Finally A has one move left.

We continue discussing Olympiad problems and their solutions.
A natural number is written in each square of an m x n chessboard. The allowed move is to add an integer k to each of the two adjacent numbers in such a way that non-negative numbers are obtained (two squares are adjacent if they share a common side). Find a necessary and sufficient condition for it to be possible for all numbers to be zero after finitely many operations.

The chessboard happens to be black and white alternatively with equal numbers of black and white. If we pick adjacent numbers one will be on a black square and another will be on a white square. Since we add equally at each step, the sum of the numbers on the black square must be the same as the sum of the numbers on white square at any point of time! - at the beginning, at the end  and every step of the progressive conversion to zero in between the beginning and the end.
But how do we pick these adjacent squares ? For the progression, the choice of squares don't matter because any two adjacent squares we pick we should be able to make them both zero and if we don't revisit the squares we have made zero, we can progress towards the end. If we can make two adjacent squares in a row zero in each step, then we can repeat this for all the rows while leaving only the last two in each row. Then we can descend down the last two columns a row at a time, thus sweeping the chessboard without revisiting the squares. By symmetry of a chessboard, the same can be done by sweeping columns at a time until the last two rows and then sweeping the last two rows.
Having discussed the way to progress without revisiting the squares converted to zero, let us now look at how to convert each pair of adjacent squares. Let us call the two adjacent squares in a row a and b. If a < b then we can add -a to both and make one zero. if a > b and b is adjacent to c, then we can add a-b to both b and c . b becomes a at this point and both a and b can become zero by adding -a. Thus we convert one square or both squares to zero. Since a-b is a positive number and the numbers on the chess board were natural numbers to begin with, we don't diminish the squares we have not covered and we progress towards the goal.

#codingexercise
Node GetSecondLargestInBST ( node root){
Node largest = GetRightmost (root);
Return  GetPredecessor(largest);
}

Olympiad Question [ Russia 2005, Indian TST 2012, France 2006]: 

In a 2 x n array, we have positive reals such that the sum of the numbers in each of the n columns is 1. Show that we can select one number in each column such that the sum of the selected numbers in each row is at most (n+1)/4 

In this problem each column consists of a pair of numbers that total to 1.0   The sum (n+1)/4 can be violated easily when  we pick the higher fractions in each column. Therefore, one strategy could be to pick the smallest numbers in each column. Unfortunately that also breaks the limit of (n+1)/4 in some cases such as for instance when the smaller fractions are all 0.4 and appear in the top row. Let the numbers in the top row be sorted in non-decreasing order as a1,a2, … an with their bottom counterparts as b1, b2, .. bn. The sum of the top row is assumed to be smaller or equal to that of the bottom row. 

One algorithm suggested by the book Olympiad Combinatorics is as follows: Starting from a1, keep choosing the smallest remaining element in the top row as long as possible. In other words, select a1, a2, …ak,  such that a1 + a2 + … + ak  <= (n+1)/4 but a1 + a2 + … + ak  + ak+1 > (n+1)/4. Now we cannot select any more from the top row. And so from the bottom row we choose the remaining elements.  All that is left to prove at this point is that the sum of the chosen elements in the bottom row is at most (n+1) /4 . 

The k+1 th element in the top row in the top row is at least the average of the k+1 elements including itself which is  more than (n+1)/4(k+1) . 

Therefore the bottom element for k+1th column has to be 1- ak+1  = 1 – (n+1)/4(k+1) but bk+1 is the largest of the chosen elements  in the bottom row (because we sorted the upper row in ascending order, the bottom row is in decreasing order and the first element we  picked is this one. So the sum of the chosen elements in the bottom row cannot exceed  b at k+1 times (n-k).  which if we simplify and substitute from the value above we get : 

                (1 – (n+1)/4(k+1)  ) (n-k)  

        =   (n – k – (n+1)(n-k)/4(k+1)) 

        =  ((n+1)/4) (4(n-k)/(n+1) – (n+1)(n-k)/4(k+1)) 

          <= (n+1)/4  

In a graph G with V vertices and E edges, show that there exists an induced subgraph H with each vertex having degree at least E/V. In other words, a graph with average degree d has an induced subgraph with minimum degree at least d/2. 

The degree of a graph is the number of edges incident to the vertex with loops being counted twice. The total degree for all the vertex therefore adds up to twice the number of edges because the same undirected edge counts twice for both the vertices. Therefore the average degree of a vertex is 2.E/V 

To get a subgraph with degree at least E/V, we start with the graph G and start deleting vertices with degree < E/V. In other words, we try to get rid of bad vertices. However in the process of doing so, we are also eliminating edges and vertices that were once good on the basis of their degree might now become bad. This is quite ok as long as there is at least one vertex left. In this case we satisfy the problem’s condition. However what happens if there are no vertex left. Fortunately such a possibility does not exist because the ratio of edges to vertices is strictly increasing on every delete. It starts at E/V and each time we deleted a vertex, less that E/V edges were deleted by the condition of our algorithm. Hence it is impossible to reach a stage when only 1 vertex is remaining, since in this case the edges to vertices ratio is 0. Since there will at least be more than one vertex, where each of them have a degree at lease E/V, we are guaranteed that the number of deletes is bounded and a valid solution will remain at that point. 

A set of three non-negative integers {x,y,z}  with x < y < z satisfying {z-y, y-x} = {1776, 2001} is called a historic set. Show that the set of all non-negative integers can be written as a disjoint union of historic sets.

We can rewrite the historic set of the form {x, x+a, x+a+b} where a and b are interchangeable and therefore lead to 'small' and 'big' sets. We use the integers from the number line because it is sorted.
Every number must be covered but no number must be covered twice. We use the following guidelines:
1: The smallest number not yet covered is the most "unsafe". We should choose x as the smallest "unsafe" number
2: Since we prefer small numbers, we should prefer "small" sets to "big" sets.
Now we can prove by contradiction where we suppose it fails and show that it doesn't.

Let us suppose the algorithm to pick the smallest number not yet covered and the subsequent step to pick the ‘small’ set first or the big set fails when we are in iteration n+1. At this time, the value of (Xn+1) + a + b will not be covered because it is greater than all the covered numbers. So Xn+1 + a or Xn+1 +b must have been covered which is why the process is failing. Further Xn+1 + a  is smaller than Xn+1 +b so the latter must be the largest number in the set and the smallest number in the set would be Xn+1+b-(a+b) = Xn+1-a  but at this stage the small set should have been used and xn+1 should have been in that set which is  a contradiction.

 we discuss a few Olympiad Combinatorics problems from the chapters of the book by the same title.  

In a graph G with n vertices, no vertex has a degree greater than delta. Show that one can color the vertices using at most delta + 1 colors, such that no two neighboring vertices are the same color. 

History: As with most graph coloring problems, the chromatic number of a graph refers to the smallest number of colors for which a coloring of the vertices exists such that adjacent vertices receive different colors. In addition, we are reminded of the four color theorem which states that every planar map can be colored with four colors such that adjacent countries receive different colors. Laszlo Lovasz is accredited with bringing this graph theory to the forefront by introducing a complex geometry to a graph in such a way that the topology of the complex provides some information about the chromatic number of the graph. 

Problem understanding : The degree of a graph is the number of edges incident to the vertex, with loops counted twice. A regular graph is one where each vertex has the same number of neighbors i.e. every vertex has the same degree. In this problem we arrange the colors as 1,2,3… and use a greedy algorithm as follows. 

We arrange the vertices in an arbitrary order and color the first vertex with color 1. Then in each stage, we take the next vertex in the order and color it with the smallest color that has not yet been used on any of its neighbours. The greedy choice makes sure we are using the smallest number for the colors. Since any vertex cannot have more than delta neighbors  and the greedy choice is picking a color different from the node, we are guaranteeing the following two properties: 

1. No two adjacent vertices will have the same colors 

2. At most delta + 1 colors are used. 

The latter property follows from the fact that when a vertex v is colored different from the delta neighbors, there will be one color in the delta + 1 set that has not been used. Since the minimum of such colors is used for the vertex v, all the vertices are colored using colors in the set {1,2,3,…. Delta + 1} 

By saving the larger number colors when we really need them, we are using the colors from the smallest numbers and therefore they are bounded by the set 1,2,3, … delta + 1. 

The greedy choice property solves this problem while proving that the delta + 1 color suffices. 

void ChromaticColoring (Node vertex, int[] colors ) 

{ 

     If (vertex != null) 

    { 

        usedColors = [] 

foreach (Node v in vertex.adjacents()) 

{ 

   if (v.color != UNKNOWN) 

     usedColors.Add(v.Color); 

} 

Sort(usedColors); 

Var availableColors = Colors.except(usedColors); 

vertex.color = availableColors.min(); 

Foreach (Node v in vertex.adjacents()) 

{ 

ChromaticColoring(v, colors); 

} 

 } 

}