Let's start with rules of the game:
There is one pile of n chips. The first player to move may remove as many chips as desired, at least one chip but not the whole pile. Thereafter, the players alternate moving, each player not being allowed to remove more chips than $f(x)$ where $x$ is the number of chips that opponent took on the previous move.
$f:\mathbb{N}\to\mathbb{N} \text{ non-decreasing and }f(x)\ge x$.
1) For which $k$ player II has winning move, if $f(x)=x+2$?
2) Which player has winning move if $f(x)=x^2$?
I know that I have to find general form of the sequence $\{H_n\}\subset\mathbb{N}$ such that $H_0=1$ and $H_{k+1}=H_k+\min_{i\le k}\{H_i: f(H_i)\ge H_k\}$ but i dont see any property :(
Problem 2.
On the table lies a pile of $n$ chips. The first player can take any number of chips, at least one, but not the whole stack. Then players make turns in turns, at what each player must take at least one piece and at most: - as many chips as the player in the previous move, if he took an even number of chips, - one chips more than the player in the previous move, if he took the odd number of chips.
The player who makes the last move wins. Indicate the winning move (if any) for the player starting the game, if n = 105. For which values n can the other player win?
what is the solving algorithm when we have two conditions?
The first one is fairly straightforward. Calculate the first few losing positions:
$$\begin{array}{c|cc} n&0&1&2&3&4&5&6&7&8\\ H_n&1&2&3&4&6&10&20&40&80 \end{array}$$
At this point it’s pretty easy to see what’s going on: if $H_n>H_{n-1}+2$, then $H_{n+1}=2H_n$. The winning positions for Player II are the positions $H_n$, and they can be described by listing $H_0$ through $H_4$ individually and then giving a general formula for $H_n$ with $n\ge 5$.
I don’t at the moment see a general form for the $H_n$ in the second problem, though it is at least clear that Player I wins if the initial position is odd and greater than $1$.