Saint Petersburg 2001

The number 1000000 is written on a board. A and B take turns, each turn consisting of replacing the number n on the board with n-1 or floor((n+1)/2). The player who writes the number 1 wins. Who has the winning strategy ?

Answer:

The intuition here is that A wins for any even number as the numbers are replaced by something smaller. 

Take n = 2, it can be replaced by one of the two given transformations 2 -1 or floor((2+1)/2)  in the first move itself by A. Take n = 4 and it can be replaced as 3 by A given that 2 is the desirable state for A. We call the position 2 as N-position because the player whose turn it is to play can win. We call the position 3 as P-position because the player who has just played it can force a win. In this case, A having played 3 forces B to write 2 either by 3-1 or floor((3+1)/2) and in both cases A wins. Similarly we can show that A wins for n = 6.

In other words, all even numbers are positions where A can play first and force a win.  To formalize this, we can experiment incrementally for the first few multiples of 2 . At some point 2k when we are satisfied, we say that all the even numbers less than 2k are N-positions.

With this assumption , we now have to show that 2K is also an N-position. If we are able to do so, we can progressively claim all 2K positions going forward are also going to be N-positions and therefore prove that all even numbers are N-positions. So how do we prove 2k is an N-position. We can show that 2K is an N-position because k is either a P position or an N position.  For example k can be odd as when k=3 and A can write k directly and win. If k is a N position, A can write 2k-1 in the first move. B is then forced to choose either 2k-2 or floor((2k+1)/2) both of which results in k and A wins. Thus we have proved that all even numbers are N positions.

At this point the given input is an even number and as A goes first in the turns, A has the winning strategy.
If A removes kn stones where k < n and B removes jn where j < n then N - kn - jn is a P position because we assumed B wins. But A could have removed kn +jn so Acould have won contradicting our assumption

Russia 2011 adapted
There are N > n^2 stones on a table. A and B play a game. A begins,
and then they alternate. In each turn a player can remove k stones,
where k is a positive integer that is either less than n or a multiple
of n. The player who takes the last stone wins. Prove that A has a
winning strategy.

Here either A or B can have a N or a P position which by the description is a winning strategy for turn of the next player or the one having just now played respectively
Let us suppose to the contrary that B has a winning strategy.
However it is not sufficient to show that B cannot win in a few cases. We have to show it also in cases where B and A respond to each others moves. Thankfully these are also similar in nature to what we described.
Let A remove kn stones in the first move. Then B removes f (k) stones in response. Then N - kn - f (k) is a P position. Now kn can be the same as jn for eliciting the same response from B because the distribution covers the same range uniformly between 1 and n-1. Therefore, N-jn-f(k) is also a P position. But suppose k < j and A removes kn stones followed by B who removes f (k) stones then A removes (j-k)n stoned leaving N-jn-f (k) and that would be a P position as seen earlier. In that case A would win and it would contradict the assumption we made.

2014 IMO problem

Let n >= 2 be an integer. Consider an n x n chessboard consisting of n ^ 2unit squares. A configuration of n rooks on this board is ‘peaceful’ if every row and every column contains exactly one rook. Find the greatest positive integer k such that, for each peaceful configuration of n rooks, there is a k x k square which does not contain a rook on any of its k ^ 2 squares.

Let us suppose that k = [sq.rt(n)] – 1 where [n] is the ceiling function of n.

Each n x n chessboard with a peaceful configuration of n rooks contains a valid k x k square. How do we prove this ? Take a rook and place it at the top most row. This column can be part of k consecutive columns, only one of which contains rook R. The consecutive columns can be chose including those on the left of R or to the right of R or both. There are n-k+1 of such consecutive columns and therefore as many k x k squares.

Now, n-k+1 = n- [sq.rt(n)] +2

=  n-sq.rt(n)+2

> n – sq.rt(n) + 1

= sq.rt(n)(sq.rt(n) -  1)  + 1

                                       > (sq.rt(n)-1)(sq.rt(n)-2)+1

                                   = k(k-1) + 1

From the above expression, from these many in the k x k squares in C, there exists a k x k square not covered by any rook. We say this because we can distribute those many squares above such that we leave the k x k square unoccupied. And so our supposition is a valid choice.

Now we have to mutually exclude this region and show that its still possible to have a chess board as required. Without this (k+1) times (k+1) square, we can still arrange the chess board if we proceed this way. First place a rook at the upper left corner of the board. Next place a rook at one square to the right and k+1 spaces down of the second rook. Repeat until the position is outside the bounds of the chessboard in which case wrap around to the top and continue placing the other rooks. Indeed such a board exists and the arrangement of the rooks is clearly peaceful

Because (k+1)^2 > n, it has the property that any (k+1)x(k+1) square in the board will be occupied by at least one rook. This complete the proof.

 [Lithuania 2010]
Problem: In an m × n rectangular chessboard there is a stone in the lower leftmost square. A and B move the stone alternately, starting with A. In each step one can move the stone upward or rightward any number of squares. The player who moves it into the upper
rightmost square wins. Find all (m, n) such that A has a winning strategy.
Solution: Note that in this problem, the moves possible are either one up or to the right. To move diagonally, you need to exchange turns.
Therefore the winning strategy would be to occupy the diagonals ourselves. Moreover, the diagonal is  only for the square portion of the chessboard of size say m x m not the rectangular portion of the m x n. In the rectangular portion, the moves will be linear since we would have already reached the top row and the squares will be equally and alternatively occupied.

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);
}