Using your Head is Permitted

February 2013 riddle

This riddle is a follow-up, with a novel twist, to the classic problems from last month's puzzle. (Readers will do well to tackle the previous challenge first. This month's riddle and its subsequent solution are spoilers to last month's solution.)

Consider the following generalization to last month's "Part 4":

Once again, we refer to a turn-based game where two players, taking alternate turns, each removes, in her turn, a chosen number of elements from a pile. The initial pile-size is N, a positive integer.

On the first turn, the first to play can take any integer amount that is less than N. On any subsequent turn, each player can take any positive integer amount that is no more than α times what was taken (by the other player) in the preceding turn, for some constant α.

The player to lose is the first to have no legal moves left. (For example, if the pile is completely emptied.)

Let S(x) be the number of N values in the range 1≤Nx for which the second player has a winning strategy.

The question: characterize the limit of x1/S(x) as x tends to infinity.

To receive credit, describe, as a function of α, a polynomial (other than the zero polynomial) that has this value as one of its roots (or prove that no such polynomial exists).

Bonus mentions will be given to solvers who do this with a low-degree polynomial. As usual, all answers should be accompanied by proofs.

List of solvers:

Radu-Alexandru Todor (*) (19 February 11:58)
Liubing Yu (*) (19 February 18:51)
Thomas Mack (28 February 03:16)

Elegant and original solutions can be submitted to the puzzlemaster at Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.


To solution

Back to main page