Also, Part 3 of the January riddle solves the case α=1 (and, in fact, any α in the range 1≤α<2): the second player wins on a power of 2, meaning that S(x)=floor(log2x)+1, and the ratio asked for converges to xlog(2)/log(x)=2.
More interesting is the case α>1 (or, more to the point, α≥2). A more general result than the one actually needed was described by Schwenk. This deals with the case where each player is allowed to remove up to f(x) elements after the other player takes x, where f(x)≥x and is monotone increasing. Schwenk gives a complete characterization of the numbers, N for which the second player has a winning strategy. It is as follows:
Denote the sequence of (increasing) N values for which the second player has a winning strategy by H(1), H(2), H(3), etc.. Then H(1)=1 and each subsequent value in the sequence is
where m is defined by being the minimum value for which f(H(m))≥H(k).
Let us re-prove this result, briefly.
First, note that there is a unique representation for any N as the sum of some subset of the H values, N=H(i1)+...+H(ik), that satisfies for each j that f(H(ij))<H(ij+1). We'll call this a "base-H" representation.
A winning strategy is to always remove the least H value that appears in the base-H representation. This lowers the number of elements appearing in the representation. By construction, the next player cannot do the same, but the winning player, in her next turn, once again will. The player following the strategy will ultimately remove the final element and win the game. The strategy only fails when the initial N belongs to the H sequence (in which case it advises the player to remove the entire pile), which is why these are the losing positions.
We therefore have a recursive definition for the H sequence via Equation (1). We claim that k-m never decreases and is bounded from above. That being the case, it will ultimately reach a final value.
To see that it does not decrease, note first that for every element in the sequence we have H(k+1)≥H(k)(1+1/α). This comes from Equation (1) and the fact that αH(m)≥H(k).
A decrease in k-m happens if H(k+2)=H(k+1)+H(n), with n≥m+2. For this to happen, we must have, by definition, αH(m+1)<H(k+1). This gives us the equation H(m)(1+1/α)≤H(m+1)<H(k+1)/α. By plugging in Equation (1), this can be simplified to αH(m)<H(k), contradicting our previous result.
To bound k-m from above, let t be the maximal value for which (1+1/α)t≤α. t is an upper bound, because if k-m>t we have H(k)≥H(m)(1+1/α)k-m>αH(m)≥H(k): a contradiction.
Let u be the final value of k-m. Once this value is reached, the H sequence begins to follow the rule H(k+1)=H(k)+H(k-u). The solution for these H values (all but the first finite number) is that H(i) is a linear combination of βi, where the β are the solutions to the polynomial
The ratio H(k+1)/H(k) ultimately converges to the β with the highest absolute value, given that its absolute value is unique among all β.
Reordering Equation (2) we get
There actually is a unique real solution for X in the range X≥1. This can be seen, for example, by noting that X-1 is a monotone function that rises from 0 to infinity in this range, but X -u, also monotone, drops from 1 to 0 in the same range.
Given the value of u, the greatest real solution to Equation (2), which we denote β, is the ratio to which consecutive H values converge. Their total number in the range 1≤N≤x, defined as S(x), is therefore logβ(x) up to an additive error term.
Let us re-write x1/S(x), our target function, as exp(log x/S(x)), then this converges to exp(log x/logβ(x)) = β.
If we were to find u, the solution to the riddle is therefore Equation (2). The remaining question is therefore which u value the system ultimately reaches.
Unfortunately, I do not know of any closed form formula that guarantees finding u. However, to solve the riddle we merely need to use the upper bound we have for u, namely t=floor(log(α)/log(1+1/α)). A polynomial that solves the riddle is the product of all polynomials of the type shown in Equation (2) for all potential u values up to t.
On the other hand (if we want to get the bonus mention), we can lower the degree of the polynomial by giving lower bounds for u.
The best lower bound I know for u is derived from the fact that ultimately the ratio of two consecutive H-values converges to a constant, β. I claim that this constant is smaller than 1+1/(α-1). To see this, consider again Equation (1). We know that H(k)>αH(m-1), so H(m)/H(k) is bounded from above by β/α. The ratio H(k+1)/H(k), which should be β, is therefore bounded from above by 1+β/α. Rearranging the formula we get the desired bound.
This places u in the range
This gives us a much lower-degree polynomial which solves the riddle.
To further make the point that this polynomial is of relatively low degree, note that the original polynomial of Equation (2) is of degree u+1. This should serve as a lower bound for the degree of the polynomial that can form a solution. For a large α the lower bound for u, from Equation (4), is on the order of (α-1)log(α) and the upper bound is approximately αlog(α). The minimal polynomial is therefore of degree approximately αlog(α), whereas the degree of the polynomial we actually found is of the order αlog2(α).