What should be the winning strategy for Bob?

Question

Alice and Bob are playing a calculator game in which the calculator can only display positive integers and is used like this: starting with the integer $x$ one player types an integer $1<=y<=99$ in and if $y\%$ of $x$ (meaning $\frac{xy}{100}$) is again an integer the calculator shows that result, otherwise the job fails and the one whose turn it was loses. How many starting numbers $1<=x<=2017$ guarantee a winning strategy for Bob who plays second?

Answer 1

In my answer I will argue that the given game is indeed about alternatingly taking away colored balls from a basket.

To see what I mean, first note that the prime factor decomposition of $100$ is $$ 100 = 2^2 \cdot 5^2. $$ Let $x = x_0 \cdot 2^i \cdot 5^j$ be the starting number of the game, where $x_0$ is not divided by $2$ or $5$. Now, suppose at her first turn Alice chooses the number $a_1 = \alpha_1 \cdot 2^k \cdot 5^l \in [1, 99]$. Then in order to ensure that $$x \cdot {a_1 \over 100} = x_0 \cdot 2^i \cdot 5^j \cdot {{\alpha_1 \cdot 2^k \cdot 5^l} \over {2^2 \cdot 5^2}}$$ is an integer it has to be $i+k \geq 2$ and $j+l \geq 2$. However, Alice cannot choose $k=l=2$ since her number must not exceed $99$.

The above shows that Alice and Bob have only to care about the power of $2$ and $5$ that the starting number contains and that they manipulate. Therefore, it suffices to keep track of exactly those powers to understand the game. The starting number $x$ leads to a pair $(i_0, j_0)$ of integers where $x = x_0 \cdot 2^{i_0} \cdot 5^{j_0}$ and $2 \not \mid x_0$ and $5 \not \mid x_0$. Then Alice chooses a pair $(a_{11}, a_{12})$ of integers and the new state of the game is $(i_1, j_1) := (i_0+a_{11}-2, j_0+a_{12}-2)$. Alice lost if one of those two numbers is less than $0$. The requirement that Alice's number be in $\{1, \dots, 99\}$ translates to the condition $2^{a_{11}} \cdot 5^{a_{12}} < 100$ which leaves the possibilities $$ (a_{11}, a_{12}) = (0,0), (1,0), (2,0), (3,0), (4,0), (5,0), (6,0), (4,1), (3,1), (2,1), (1,1), (0,1), (0,2), (1,2). $$ Of course, in his first turn Bob has the same possibilities to choose for his first move $(b_{11}, b_{12})$ which leads to the next state of the game which is $(i_2, j_2) = (i_1+b_{11}-2, j_1+b_{12}-2)$.

Intuitively this is the same situation as in a game where a basket is given that contains blue and red balls. In every step, two red and two blue balls are taken away but Alice and Bob can add a specified number of balls (which depends on the color). The player loses who doesn't leave at least two red and two blue balls in the basket after his turn.

Now, let's analyze the game using the basket picture where a red ball means a power of $2$ and a blue ball a power of $5$. Then I say the state of the game is $(i,j)$ if there are $i$ red and $j$ blue balls in the basket. Netting with the balls the player can add and the two balls of every color that are taken away, Alice or Bob can

• add between $-2$ and $4$ red balls if he removes two blue ones
• add between $-2$ and $2$ red balls if he removes one blue ball
• add $-2$ or $-1$ red balls if he doesn't touch the blue balls.

(Adding a negative number of balls means what you think it does.) Note that neither Alice nor Bob can't stop the decreasing number of blue balls.

Which states do immediately lead to the player losing who has to move? Certainly, in the state $(0,0)$ the moving player loses because either the number of red balls or the number of blue balls has to decrease. If there is no blue ball i.e. the state is $(\cdot, 0)$ the player has to leave the number of blue balls unchanged and can remove $1$ or $2$ red balls. Hence of all states with no blue ball only in $(0,0)$ does the player lose immediately. Similarly, if there is no red ball and the state is $(0, \cdot)$ the player loses immediately only if the number of blue balls is zero as well. Thus $(0,0)$ is the only state where a player loses immediately.

Let's have a closer look at states of the form $(x,0)$ where Alice has to move. In $(0,0)$ Alice loses as discussed above. It turns out Alice only loses if $3 \mid x$ otherwise she wins. We show that by induction. The base case has been done above. Suppose $x > 0$ and is not divided by $3$. Then Alice and Bob both know that every player in order not to lose must not touch the blue balls and hence can either remove $2$ or $1$ red balls (and nothing else). Thus by choosing between the two Alice can make sure that the the following state is $(y,0)$ where $y$ is divided by $3$. Then the induction hypothesis says that Bob loses (since then Bob is in Alice's shoes), so Alice wins. However, if $3 \mid x$ then both options for Alice (remove one or two red balls) will lead to a situation $(y,0)$ where $3 \not \mid y$. Hence the hypothesis says that Bob will win and Alice loose.

So we covered the states of the form $(\cdot, 0)$. Now, consider states of the form $(x, 1)$. Then Alice - who doesn't want to lose - can choose between removing $1$ blue ball and adding $-2, -1, 0, 1$ or $2$ red balls or she can let the blue balls as they are and remove either $1$ or $2$ red balls. Certainly, it is desirable to get into one of the states of the form $(y, 0)$ where Bob loses i.e. where $3$ divides $y$. Alice can achieve this for any given state $(x,0)$ (you see why?) and therefore in every state of the form $(\cdot, 1)$ Alice has a winning strategy.

Let's go on to states of the form $(x,2)$. From this position Alice can remove two blue balls and a suitable number of the red balls such that the following state is $(y,0)$ where $3 \mid y$. But then Bob loses and Alice wins as discussed.

The states $(x,3)$ are a bit more difficult. If Alice removes any blue ball there will be either $1$ or $2$ blue balls left. We showed that this will lead to a loss of Alice, so she can't change the number of blue balls. Instead, she has to remove either $1$ or $2$ red balls. This is exactly the situation we had for the states $(\cdot, 0)$, hence Alice loses only if $3 \mid x$ and otherwise she wins.

Now, the arguments would repeat themselves over and over again for an increasing number of blue balls. We conclude that for a starting state of $(x,y)$ Alice wins

• if $3 \not \mid y$ or
• if $3 \mid y$ and $3 \not \mid x$.

On the other hand, Bob wins

• if $3 \mid y$ and $3 \mid x$.

What does that mean besides baskets and balls? If $x = x_0 \cdot 2^i \cdot 5^j$ is the starting number, Bob has a winning strategy iff $3 \mid i$ and $3 \mid j$.

A computer calculation resulted in $930$ numbers between $1$ and $2017$ having this property.

Answer 2

We classify numbers x into "winners" and "losers". x is a loser if for every 1 < y < 99 either (x * y) / 100 is not an integer or it is a winner; x is a winner if there is an y such that (x * y) / 100 is an integer and a loser.

If x is a multiple of 2 or 5 then I can enter y = 50 or y = 20 and survive the next round; if x is neither a multiple of 2 or of 5 then (x * y) / 100 is not an integer for any y < 100. Any x not divisible by either 2 or 5 is a loser.

If x is divisible by 2 or 5, then replacing x with (x * y) / 100 MUST remove one factor 2 or 5, and can remove factors up to 2^2, and up to 5^2, but not both at the same time. So unless x is divisible by 8 or 125 or 100, the player can leave a loser. Any x divisible by 2 or 5, but not divisible by 8, 125 or 100 is a winner.

If x is divisible by 8 but not 16 or 5, or divisible by 125 but not 625 or 2, or divisible by 100 but not 200 or 500, then the player is forced to leave a winner, so any such x is a loser. We continue this and classify all x as "winners" or "losers", then we count the number of "losers" from 1 to 2017.

Answer 3

Let $x = 2^a \cdot 5^b$ and $y = 2^c \cdot 5^d$, each round the calculator does $\frac{xy}{100} = 2^{a+c-2} \cdot 5^{b+d-2}$. The goal is to either reduce both exponents to zero so the opponent can't reach another integer or to reduce them just enough so the opponent can't win in the next move. Essentially there are $14$ moves (or $y$-values):

$$\begin{array}{c|c|c} y & c-2 & d-2 \\ \hline 1 & -2 & -2 \\ 2 & -1 & -2 \\ 5 & -2 & -1 \\ 10 & -1 & -1 \\ \hline 4 & \pm 0 & -2 \\ 20 & \pm 0 & -1 \\ 25 & -2 & \pm 0 \\ 50 & -1 & \pm 0 \end{array} \qquad \begin{array}{c|c|c} y & c-2 & d-2 \\ \hline 8 & +1 & -2 \\ 16 & +2 & -2 \\ 32 & +3 & -2 \\ 64 & +4 & -2 \\ 40 & +1 & -1 \\ 80 & +2 & -1 \end{array}$$

If the starting number is not divisible by $2$ or $5$, Alice would lose on the first move. There are only $33$ tuples $(a,b)$ for which $x<2017$ and the only ones where Bob has a guaranteed winning strategy are

$$(3,0) \to x = 8 \quad (6,0) \to 64 \quad (9,0) \to 512 \quad (0,3) \to 125 \quad (3,3) \to 1000$$

In the words of gnasher729's answer, call them "losers" for Alice. All other tuples can be reduced in one move to these and become therefore "losers" for Bob. So the starting numbers from the tuples above for which Bob can win are $n \cdot 2^a \cdot 5^b$ with $n$ not divisible by $2$ or $5$, and according to my calculations there are $123$ of them