Dynamic problems

Question

A natural number n represents the initial position in the game. When it is a players turn he/she is allowed to

I)  Subtract 2 from n
II) Subtract 3 from n
III)    Subtract 5 from n

We call the player who begin the game Adam and the other player Berta. The players alternate by applying on of the three rules to the number 0 or a negative number his/her opponent. If a player manages to produce the number 0 or a negative number he/she wins the game.

Here is an example of a game played by Adam and Berta (for n=15)

15 is given to Adam. He decides to subtract 5 leaving 15-5 = 10 to Berta
10 is given to Berta. She decides to subtract 3 leaving 11-3=8 to Beta
8 is given to Adam. He decides to subtract 2 leaving 8-2=6 to Berta
6 is given to Berta. She decides to subtract 2 leaving 6-2=4 to Adam
4 is given to Adam. He decides to subtract 5 producing -1 a negative number, Adam wins!

b) we define a one dimensional array X(1), X(2),X(3),..,X(n)

i)  X(j) =1 if Adam has a method to win when given the number j
ii) X(j)=0 if Adam has no method that guarantees that he wins when the given the number k

Calculate X(1),X(2),X(3)….,X(23),X(25)

What is X(8), X(13) and X(24)? Answer should be of the form boolean boolean boolean so if X(8)=0 , X(13)=1 and X(24)=1 the correct answer is 011 Thus the correct answer is one of the following 000 001 010 011 100 101 110 111

My attempt is

n=8
Adam: 8-5=3
Berta: 3-3 =0
Berta wins  0

n=13 
Adam=13-5=8
Berta: 8-3=5
Adam 5- 5
Adam wins 1

I get really stuck with 24, so far I have 01 

Is there a method for this type of problem, i have been stuck on it for ages now. Thanks in advance

Answer 1

Your attempt is flawed in both cases. Adam can guarantee a win from $n=8$ by subtracting $2$ instead of $5$. Similarly for Berta in the $n=13$ case.

Adam can obviously always win when $n\le5$ by simply subtracting $5$. But that means that Berta has a winning strategy for $n=6$ and $7$, because whatever Adam subtracts leaves Berta with a "winning" remainder. And then it starts over: $8\le n\le12$ are winning numbers for Adam, because he can always subtract something that leaves Berta with either $6$ or $7$, while $n=13$ and $14$ are losing numbers for Adam because whatever he subtracts leaves Berta in the winning range between $8$ and $12$. And so forth. Do you see from this how the pattern continues?

Added later: The OP asked for more explanation. To summarize what we've found so far, the pattern of who has the winning strategy, from $n=1$ to $n=14$, is $5$ numbers for Adam followed by $2$ for Berta followed by $5$ for Adam followed by $2$ for Berta. Let's prove this pattern persists.

Any time five consecutive numbers are winning positions for the first player (Adam), the next two numbers are losing positions, because whatever Adam subtracts ($2$, $3$ or $5$) leaves one of the five winning positions.

On the other hand, any time two consecutive numbers, say $n-1$ and $n$, are losing positions for the first player, the next five are winning positions:

• $n+1$ is winning because $(n+1)-2=n-1$ is losing,
• $n+2$ is winning because $(n+2)-2=n$ (alternatively $(n+2)-3=n-1$) is losing,
• $n+3$ is winning because $(n+3)-3=n$ is losing,
• $n+4$ is winning because $(n+4)-5=n-1$ is losing, and
• $n+5$ is winning because $(n+5)-5=n$ is losing.

Because we start with $5$ winning positions, the pattern of $5$ wins and $2$ losses is established. So the pairs of consecutive losing positions are $\{6,7\},\{13,14\},\{20,21\},\{27,28\},\{34,35\},\ldots$, and all other numbers are winning positions.