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.