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(log_{2}*x*)+1, and the
ratio asked for converges to *x*^{log(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*(*i*_{1})+...+*H*(*i*_{k}),
that satisfies for each *j* that
*f*(*H*(*i*_{j}))<*H*(*i*_{j+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 *x*^{1/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 αlog^{2}(α).