jump to navigation

Problem of the Day #127: A Silly Number Game July 24, 2011

Posted by Alex in : potd , trackback

Al and Bert are playing a number game in which they take turns modifying a number $n$. Whenever it is Al’s turn, he replaces $n$ with $n – a$, where $n$ and $a$ are relatively prime and $1 < a < n$. Whenever it is Bert's turn, he replaces $n$ with $n - b$, where $n$ and $b$ are not relatively prime and $1 < b < n$. If a player cannot make a move on a given turn, then that player wins. An initial value for $n$ is albert if whoever goes first is guaranteed to win, assuming both players play optimally. How many initial values of $n$ from $1$ to $1,000,000$ are albert?


no comments yet - be the first?