This problem gave people a hard time at MOP-as far as I know, no red, blue or black people got it, but I am not too sure about black. notes from grader; one should build a primitive programming language in terms of nim style language, and program "x is power of 2"; There is a harder version of the problem, with x prime when first person has winning strategy. Every move should be forced.

As far as I know, no one in black got it either (I was sitting with the black group).

Can anyone on AoPS provide a solution? I heard there was a mindblowing one presented at MOP

Some random stuff I've been discussing with math_explorer: If $S$ may be infinite, the problem is solved (very generally). If $A$ is the set of $n$ where the first player wins (with $0 \not\in A$), then $k = 2$ and $S = \{(-a, 1) : a \in A\} \cup \{(-t, -1) : t \in \mathbb{Z}^+\}$ is the solution. (The first player wins immediately by playing $(-n, 1)$; otherwise, whatever the first player does, the second player can reduce the tuple to $(0, 0)$ in the next move.) Back to the original problem: We believe it's impossible to force all the moves. There must be a move in the form $(-a, \text{something})$ to take account of $n$, otherwise the game is always first player win or always second player win. There must also be another move that can be played after $(-a, \text{something})$ is done (for the same reason; if there's none, then $n$ is still not considered). But for large enough $n$ ($n \ge 2a$), both of these moves will be available. However, forcing some certain multiset of moves to occur, even though not necessarily in order, might still be possible.

I think I've got it, although I'm struggling to describe in a way that's both intuitive and rigorous. We will use $k = 9$. $a_1$ and $a_2$ will be the "registers" of our program, and the remaining 7 numbers will be the "state". Most of the time, exactly one of the state numbers will be 1 and the others will be 0; the state number that's 1 will correspond to the current state of our program. Here's a high-level description of the six states and the possible moves in each state in our program: State S1: Go to F1. State F1: (-2, +1) and go to S1. Go to S2. (-1, 0) and go to S3. State S2: (-1, 0) and win. (0, -1) and win. State S3: (-1, 0) and win. Go to F4. State S4: Go to F4. State F4: (+1, -1) and go to S4. Go to S5. State S5: Go to F1. (0, -1) and win. The letters in the state labels indicate whose turn it must always be when that state is reached. Since every go-to from a state targets a state with a different letter, it's obvious that this is preserved. Instructions of the form "($p$, $q$) and go to X" indicate the tuple formed by putting $p$ in the first position (so it affects register $a_1$), $q$ in the second position (so it affects register $a_2$), $-1$ in the position corresponding to the current state (so this tuple can only be used when the current state is what we expect it to be, and clears the state), $+1$ in the position corresponding to state X (so the state numbers are set to state X after this tuple is used), and 0 elsewhere. Instructions of the form "Go to X" are as above where $p = q = 0$. Instructions of the form "(p, q) and win" will be explained later; for now assume that, when the state allows this instruction and the second player can change the registers $a_1$ and $a_2$ by $p$ and $q$ without making either negative, s/he can claim victory immediately. We assign the seven states in that order to the last seven numbers in our tuple. In addition to the instructions indicated above, we provide a starting move (-1, 0, 1, 0, 0, 0, 0, 0, 0) that enables the first player to activate state S1 from the initial state. Now, we may prove the conditions at each state under which the first player has a winning strategy: (W0) When there is no state, i.e. the state numbers are all zero, the first player has a winning strategy iff $a_1 + 2a_2$ is a power of two and $a_1$ is positive. (W1) At positions S1 and F1, the first player has a winning strategy iff $a_1 + 2a_2$ is one less than a power of two. (W2) At position S2, the first player has a winning strategy iff $a_1 = a_2 = 0$. (W3) At position S3, the first player has a winning strategy iff $a_1 = 0$ and $a_2$ is one less than a power of two. (W4) At positions S4 and F4, the first player has a winning strategy iff $a_1 + a_2$ is one less than a power of two. (W5) At position S5, the first player has a winning strategy iff $a_1$ is one less than a power of two and $a_2 = 0$. This is straightforward verification, really: (W0) When there is no state, the only possible move is the starting move so it forces the first player to move into S1. Thus (W0) is implied by (W1). (W1) The move at S1 is forced. At F1, if $a_1 = a_2 = 0$ (so $a_1 + 2a_2$ is one less than $2^0$), the first player can win by going to S2; but otherwise, s/he can't go to S3 while $a_1$ is 2 or more, so s/he is effectively forced to repeatedly convert 2 in $a_1$ into 1 in $a_2$, preserving $a1 + 2a_2$, and the second player can only move back to F1. This occurs until $a_1 < 2$; thus (W1) is implied by (W2) and (W3). (W2) If either $a_i$ is nonzero, the second player wins right away; otherwise, s/he has no move and the first player wins. (W3) Clearly, the second player wins right away if $a_1$ is positive. If not, s/he is forced to move to F4; thus (W3) is implied by (W4). (W4) Analogous to W1: The move at S4 is forced. At F4, the first player can't go to S5 as long as $a_2$ is 1 or more, so s/he has to move to S4 and repeatedly convert $a_2$ to $a_1$ while preserving their sum. So (W4) is implied by (W3). (W5) Clearly, the second player wins right away if $a_2$ is positive. If not, s/he is forced to move to F1; thus (W5) is implied by (W1). Of course, the "proof" as stated above is 100% circular logic, but if you separate each statement into statements that depend on a specific $a_1$ and $a_2$, you can set up a mathematical induction. The details of this are left to the reader as an exercise (or I'll fill them in when I find the time) We have two things left to explain: how we implement the instruction "(p, q) and win" and why we can pretend to maintain that for most of the time, our program is in a unique state; after all, the latter condition is easily disrupted if either player were to decide to play the starting move as anything other than the first move of the game. (So, in accordance with the above discussion with chaotic_iak, essentially none of our moves are actually forced even when I used that word.) In fact, these are created through the same mechanism. All you have to do is make a bunch of moves available under those conditions that reset all the state numbers and also decrease $a_1$ and $a_2$ by varying amounts; all combinations of subtracting 0 to subtracting 4 should suffice. Specifically: for implementing "(p, q) and win", add 25 tuples of the form $(p - i, q - j, \ldots, -1, \ldots)$ for $i, j \in \{0, 1, 2, 3, 4\}$ (with the $-1$ placed on the same position as usual to require the current state to be what we want it to be). For preventing reusing the starting move, add a bunch of tuples that subtract 2 from the first state number or subtract 1 from two state numbers, and subtract variable $i$ and $j$ from the two registers. These are only usable if there are somehow two positive state numbers or the first state number was increased twice, which indicates somebody abused the starting move. Any of these "escape clause" tuples will reset the state numbers to all zero. Furthermore, because the powers of two are rare enough and there are sufficiently many options for decreasing $a_1$ and $a_2$, whoever is able to pick one can always pick one that leads to $a_1 + 2a_2$ not being a power of two. Thus, whoever can activate an escape clause can win by (W0) --- however, this shows that this statement must also be inductively proved alongside the others.

I have a rather complicated construction, hopefully someone else can find a simpler solution. We have $k=9$, and $S$ consists of $S_1=$ (-1,0,0,1,0,0,0,0,0) and (-1,1,0,-1,0,0,0,0,0) $S_2=$ (0,-1/-2/-3,0,-1,0,0,1,0,0) and (0,-1,1,0,-1,0,-1,0,0) $S_3=$ (-1,0/-1/-2,0,0,-1,0,0,0,0) and (-2,1,0,0,-1,0,0,0,0) $S_4=$ (0/-1,0,0,-1,-1,0,0,0,0) $S_5=$ (-1,0/-1/-2,0,0,0,0,-1,0,0) and (-2/-3,0,0,0,0,0,-1,0,0) $S_6=$ (-1/-2,0,0,-2,0,0,0,0,0) and (0,0/-1/-2,0,-2,0,0,0,0,0) and for each of the above 9-tuple also take the two other "cyclic within triplet" permutations, i.e.: (123456789) $\rightarrow$ (312645978) and (231564897). The / above means "and". So for example $S_4$ consists of 6 elements (0,0,0,-1,-1,0,0,0,0); (-1,0,0,-1,-1,0,0,0,0); (0,0,0,0,-1,-1,0,0,0); (0,-1,0,0,-1,-1,0,0,0); (0,0,0,-1,0,-1,0,0,0); (0,0,-1,-1,0,-1,0,0,0).

Firstly we note that (1,0,0...) is winning, since P1 (player 1) can play the first k-tuple in $S_1$ to reach (0,0,0,1,0...), and P2 has no legal move. Next we proceed inductively in a few parts. In all inductions we induct by decreasing the total sum of all elements in the k-tuple. Note that since our construction is "cyclic within triplet", all induction statements are also true for "cyclic within triplet" permutations. Part 1: (a,b,0,0...) is losing for player 1 when a is odd, except for when (a,b) = (1,0). Proof: All the k-tuples in $S$ decrease some of the 4th to 9th number in the k-tuple except for those in $S_1$. So P1 only has two possible choices: Case 1: He goes to (a-1,b,0,1,0...). If $a\ge 3$ P2 then plays from $S_1$ to reach (a-2,b+1,0,0...) and we are done by induction. If $a=1$ then P2 plays from the first k-tuple in $S_2$ to reach (0,c,0,0,0,0,1,0,0) where c<b is either 0 or any odd number $\ge 3$ (possible as P2 can choose to decrease b by 1,2 or 3, and $b\neq 0$ as a=1). Now P1 has lost when c=0 & otherwise can only play from $S_1$ to reach (0,c-1,0,0,1,0,1,0,0). P2 plays from 2nd k-tuple in $S_2$ to reach (0,c-2,1,0,0...) and by induction this is losing. Case 2: He goes to (a,b-1,0,0,1,0...). If $a=1$ P2 plays from the first k-tuple in $S_3$ to reach (0,c,0,0...) where c<b is either 0 or any odd number $\ge 3$, and by induction this losing. If $a\ge 3$ then P2 plays from the second k-tuple in $S_3$ to reach (a-2,b,0,0...) and we are done by induction (note b$\neq 0$ is implied in case 2). Part 2: (a,b,0,0...) is losing for player 1 when a is even, $a\ge 2$ and $a+2b$ is not a power of 2. Proof: Similarly, we know that P1 must play some k-tuple in $S_1$, so there are two possible options: Case 1: He goes to (a-1,b,0,1,0...). P2 plays from $S_1$ again to reach (a-2,b+1,0,0...). If $a\ge 4$ we are done by induction as a+2b remains not a power of 2. If $a=2$ and b+1 is odd we are done by part 1 (note $b\neq0$ as a+2b not power of 2), while when b+1 is even we know that $\frac{a+2b}2=b+1$ is also not a power of 2 and we are done by induction. Case 2: He goes to (a,b-1,0,0,1,0...). P2 plays from first k-tuple in $S_3$ to reach (a-1,b-1,0,0...) and by part 1 we are done (note (a,b) is not (2,1) as that gives a+2b=4). Part 3: (a,b,0,0...) is winning for player 1 when a is even, $a\ge 2$ and $a+2b$ is a power of 2. Proof: P1 plays from $S_1$ to reach (a-1,b,0,1,0...). P2 has four options. Case 1: He plays from $S_1$ to reach (a-2,b+1,0,0...). We are done by induction since either $a\ge 4$ and a+2b remains a power of 2, or a=2 and b+1 is a power of 2 (b=0 reduces to trivial base case as well) Case 2: He plays from $S_1$ to reach (a-1,b-1,0,1,1,0...). P1 now plays from $S_4$ to reach (a-1,b-1,0,0...) and by part 1 we are done. If a=2,b=1, player 1 goes to (a-2,b-1,0,0...) instead. Case 3: He plays from $S_1$ to reach (a-2,b,0,2,0...). If $a\ge 4$ P1 plays from first k-tuple of $S_6$ to reach (a-3,b,0,0...) and we are done by part 1, except when a=4,b=0 where he goes to (a-4,b,0,0...) instead. If $a=2$ he plays from second k-tuple in $S_6$ to reach (0,c,0,0...) where c$\le$b is either 0 or an odd number $\ge 3$ and we are done by part 1. Case 4: He plays from $S_2$ to reach (a-1,b-1/2/3,0,0,0,0,1,0,0). If $a\ge 4$ P1 plays from the second k-tuple in $S_5$ to reach (a-3,b-1/2/3, 0,0...) and we are done by part 1, except when a=4 and b-1/2/3=0, where he goes to (0,0,0...) instead. If $a=2$ P1 plays from the first k-tuple in $S_5$ to reach (0,c,0,0...) where c<b is either 0 or an odd number $\ge 3$ and we are done by part 1.

Solution by just implementing python. Refer to positions in the $k$-tuple as registries. Let Input refer to the first registry. We notational abuse $(A, B, C)$ to only refer to part of a subtuple affecting those registries. Claim: We can force Alice to take moves from a subset $N \subset S$ and force Bob to wait. Proof. Take two registries $A$ and $B$ who track whose turn it is. Alice moves $N$ add $-1$ to $A$ and $1$ to $B$, while Bob's sole move adds $1$ to $A$ and $-1$ to $B$. Now take another registry called $Death$. We also define an Init move that adds $1$ to $B$ and $1$ to $Death$, and subtracts $1$ from Input. Define $Death1$ and $Death2$ as well. Evidently, Init must be ran first. How do we prevent players from calling Init twice though? By adding $9$ police moves as follows: the first component is $\{(-1, 0), (0, -1), (-1, -1)\} \subset (A, B)$ and the second component either consists of $\{(-2, 1), (-1, 1), (1, -1)\} \subset (Death, Death1, Death2)$. In this case, if Init is ever ran twice, the next player can simply run these police moves to repeatedly clear out $\{A, B\}$ till input becomes $0$. In either case, after the first initial move, Bob can't do anything (minus other police moves defined later) and Alice has choices. $\blacksquare$ Claim: It is possible to turn a move $M$ into one such that when run gives a win. Call such moves terminating. Likewise, it is possible to turn a move $N$ into a losing one when ran twice. Call such a move global. Proof. Copy the $Death$ registry idea with clearing both $A$ and $B$. This forces spamming Init which loses. Then add the $Death$ component to $N$. $\blacksquare$ We now define registry states $A_1, A_2, \dots, A_n$. A move for Alice with registry component $A_i$ of $-1$ and $A_j$ of $1$ is said to transition from $A_i$ to $A_j$. All our following definitions are transitions. Claim: We can define a keep move that transitions from $A_i$ to itself $A_i$ as well. Proof. Define a dummy registry $A_n'$, then have keep moves be duplicated with a component $\{(-1, 1), (1, -1)\} \subset (A_n, A_n')$. $\blacksquare$ We now use these transitions to lay out a programming language and force Alice to order her moves. If not specified as a keep move, a move is likely a transition. Naturally, we can also nest registry states. First, some housekeeping we add a global move that sets $A_1$ to $1$. Next we add a CleanInit move which adds $1$ to Input and transitions from $A_1$ to $A_2$. Claim: We can force Alice to only transition from $A_n$ to $A_{n+1}$ to only run if and only if some registry $R$ is $0$. In other words, we can check zero a registry. Proof. Add a terminating move for Bob that subtracts $1$ from $R$. $\blacksquare$ Claim: We can create copy statements that make Alice copy one registry $R$ into another $S$. Proof. Create a dummy registry $D$ and suppose we are on registry state $A_n$. Then give Alice a keep move of $(-1, 1, 1) \subset (R, S, D)$ and a transition move to $A_{n+1}$. Give Bob a check zero on $R$ when in the state $A_{n+1}$ to force Alice to fully copy $R$ to $S$ and $D$. Then do the same thing with $(1, -1) \subset (R, D)$ to leave $R$ unchanged. $\blacksquare$ Claim: We can create clear statements that clear a registry $R$. Proof. Let the current state be $A_n$. Then give Alice a transition move as well as a keep move that decrements $R$ by $1$. Have Bob check that the registry $R$ is zero in $A_{n+1}$ as well. $\blacksquare$ Claim: We can define subroutines / functions that take in a fixed number of arbitrary registries $R_1, \dots, R_N$ and adds outputs into registries $S_1, \dots, S_M$. Proof. Fix input registries $I_1, \dots, I_N$ and output registries $O_1, \dots, O_M$. Copy all the input registries from $R_i$ to $I_i$. Flag another registry $IsRunning$ with $1$. Give the subrountine its own registry states and required dummy states, with last registry state $L$. When the subrountine transitions to $L$, make Alice clear all registries used in the process after copying into output registries. $\blacksquare$ Claim: At registry $A_n$, We can make Alice that jumps to registry $A_{n+k}$ for $k > 1$ if some registry $R$ is zero. In other words, we have if statements. Proof. Let Bob check zero for $A_{n+1}$ and the registry $R$. $\blacksquare$ Claim: We can invert a registry from $0$ to $1$ and $1$ to $0$. In other words, $!$ operator. Proof. Set another registry to a constant of $1$, subtract this registry from it until this registry is $0$, then copy that registry to this registry. $\blacksquare$ Claim: We can check if two registries $A$ and $B$ have the same value and write the value as $1$ if True and $0$ if False to a registry $C$. We can also check $>, <, \le, \ge$. Proof. Copy the registries into dummy ones $R$ and $S$. Force Alice to run $(-1, -1) \subset (R, S)$ while possible. Then make her report her result to registries $Equal$ or $NotEqual$, and let Bob check that is actually the case using check zero and not. Then depending on which registry is nonzero, transition again and potentially add to $C$. Finally, clear both registries. The other relational operators are handled similarly. $\blacksquare$ Claim: We can create while statements that run a function while something is not true. Proof. Let $A_n$ be the current registry step. Force a transition to $A_{n+1}$ if a condition holds, else jump to $A_{n+2}$. At $A_{n+1}$, run a function then jump back to $A_n$. $\blacksquare$ We now give a complete program in Python that can be emulated which works when taking in input $n$, with a winning termination being a terminating move, and a losing termination giving Bob a terminating move. n += 1 def remainder2(n): while (n > 2): n -= 2 r = n return r def quotient2(n): q = 0 while (n > 2): n -= 2 q += 1 return q while (n != 1): if (remainder2(n) == 1): TerminateBad() n = quotient2(n) TerminateGood() Remark: At this point, we can actually just implement Conway's FRACTRAN and get Turing Completeness as fun bonus. So the problem statement might as well have been enumerating over primes or perfect numbers or any other enumeratable set.

Name the players Alice and Bob in that order. We view the problem with elements of the tuple as named variables (all zero-initialized except for one) and elements of $S$ as named "functions" acting on the variables. To differentiate, we will refer to variables in capital letters and functions in lowercase. We will name the first tuple element $\text{NUM}(1)$ and define the rest as we go. If not specifically specified, a function does not change the values of a given variable. Finally, all inputs are to be taken modulo how many possible numbers they can equal, except for in the definition of $\text{beginkill}(i,j)$. Our first two moves will be unique, setting up the rest of the process. We define the variables $\text{INIT}(1),\text{INIT}(2),\text{INIT}(3)$ along with $\text{TURN}(1),\text{TURN}(2)$. We define functions $\text{begin}(1),\text{begin}(2)$ and $\text{beginkill}(i,j)$ for each $(i,j) \in \{1,2\} \times \{1,2,3\}$ as follows: $\text{begin}(1)$ decreases $\text{NUM}(1)$ by $1$ and increases all $\text{INIT}(i)$ by $1$. $\text{begin}(2)$ increases $\text{NUM}(1)$ by $1$, decreases $\text{INIT}(1)$ by $1$, and increases $\text{TURN}(1)$ by $1$. $\text{beginkill}(i,j)$ decreases $\text{INIT}(1)$ and $\text{INIT}(i+1)$ by $2$ and decreases $\text{TURN}(j)$ by $1$ (if $j=3$ then nothing happens for the last part). We now split the rest of $S$ into two sets of functions $A,B$ such that: Every function in $A$ doesn't change any $\text{INIT}(i)$, decreases $\text{TURN}(1)$ by $1$, and increases $\text{TURN}(2)$ by $1$. Every function in $B$ doesn't change any $\text{INIT}(i)$, increases $\text{TURN}(1)$ by $1$, and decreases $\text{TURN}(2)$ by $1$. Clearly the first two moves must be $\text{begin}(1)$ and $\text{begin}(2)$ in that order. Now suppose that $\text{begin}(1)$ is called at some later point; clearly we cannot have called $\text{begin}(2)$ (except at the start) or any $\text{beginkill}(i,j)$ before this. When this happens both $\text{INIT}(2)$ and $\text{INIT}(3)$ become $2$, and the other player can call some $\text{beginkill}(1,j)$ with $j \in \{1,2\}$ (based on player), which makes $\text{TURN}(1)=\text{TURN}(2)=\text{INIT}(1)=0$. After this, the only option left for the original caller of $\text{begin}(1)$ is to call $\text{begin}(1)$ again, and the other player can call $\text{beginkill}(2,3)$. Then this repeats, with the other player alternating between $\text{beginkill}(1,3)$ and $\text{beginkill}(2,3)$ until the original $\text{begin}(1)$ caller decreases $\text{NUM}(1)$ to negative. Hence calling $\text{begin}(1)$ after the start is a guaranteed loss, so $\text{begin}(2)$ and $\text{beginkill}(i,j)$ will not be called after the first two turns. In particular, for the rest of the game Alice will always call functions from $A$ and Bob will always call functions from $B$. We set up the rest of the functions and variables now. Along with $\text{NUM}(1)$, define $\text{NUM}(2)$ and $\text{NUM}(3)$. Then for each $i \in \{1,2,3\}$ and $j \in \{1,2\}$ we define $\text{STATE}(i,j)$. Finally, we define the variable $\text{WIN}$. We modify $\text{begin}(2)$ to also initialize $\text{STATE}(1,1)$ to $1$. The idea is that during normal gameplay exactly one of these will equal $1$, and the rest $0$. If $\text{STATE}(i,j)$ is currently $1$, then the current player is $j$ and the value of $i$ reflects the fact that $\text{NUM}(i)$ is "active". During player $j$'s turn, we normally (i.e. unless otherwise stated) decrement some $\text{STATE}(i_1,j)$ and increment some $\text{STATE}(i_2,3-j)$ ($i_1=i_2$ is allowed). For convenience we will define a tracker $\text{CUR} \in \{1,2,3\}$ (with values taken modulo $3$, so $0=3$), corresponding to the value of $i$ such that $\text{STATE}(i,j)=1$; note that this is not a tuple element. In some situations we will change (i.e. decrement) the only $\text{STATE}(i,j)$ equal to $1$ to $0$. In this case we let $\text{CUR}=\text{null}$; note that this requires $\text{CUR} \neq \text{NULL}$ to begin with. This therefore has the effect of depriving the other player of any moves, making them instantly lose. Now we define functions for Alice; the modification of $\text{STATE}(i,j)$ is omitted and we instead provide a description of how $\text{CUR}$ changes: $\text{basic}()$ will keep $\text{CUR}$ and decrease $\text{NUM}(\text{CUR})$ by $1$. To be explicit, we actually have three functions $\text{basic}(i)$ for $i \in \{1,2,3\}$ that decrease $\text{NUM}(i)$ by $1$, decrease $\text{STATE}(i,1)$ by $1$, and increase $\text{STATE}(i,2)$ by $1$. Thus note that "maintaining" $\text{CUR}$ actually means there is a decrement and an increment as usual, despite the fact that it sounds like nothing is happening to the $\text{STATE}$ variables. Since we can only ever run $\text{basic}(\text{CUR})$, for convenience we just refer to all three with $\text{basic}()$. $\text{advance}()$ will increase $\text{CUR}$ by $1$, then decrease $\text{NUM}(\text{CUR})$ by $1$. $\text{claimwin}()$ will maintain $\text{CUR}$, decrease $\text{NUM}(\text{CUR})$ by $1$, and increase $\text{WIN}$ by $1$ (hence we cannot have $\text{CUR}=\text{null})$. $\text{claimkill}()$ will decrease $\text{WIN}$ by $1$, decrease $\text{NUM}(\text{CUR}-1)$ by $1$ and then set $\text{CUR}=\text{null}$. Here are functions for Bob: $\text{basic}()$ will decrease $\text{NUM}(\text{CUR})$ by $1$ and increase $\text{NUM}(\text{CUR}+1)$ by $1$. $\text{advancekill}()$ will decrease $\text{NUM}(\text{CUR}-1)$ by $1$ and then set $\text{CUR}=\text{null}$. $\text{claimwin}()$ will increase $\text{WIN}$ by $1$, increase $\text{CUR}$ by $1$, and then decrease $\text{NUM}(\text{CUR})$ by $1$. $\text{claimkill}()$ will actually refer to three separate "functions" (although each "function" corresponds to $3$ actual functions based on $\text{CUR})$ that for $i \in \{1,2,3\}$, decrease $\text{WIN}$ by $1$, decrease $\text{NUM}(i)$ by $1$, and set $\text{CUR}=\text{null}$. Note that: Alice cannot call $\text{advance}()$ unless $\text{NUM}(\text{CUR})=0$, else Bob wins with $\text{advancekill}()$. Likewise, Bob can only call $\text{advancekill}()$ after Alice improperly calls $\text{advance}()$. Alice cannot call $\text{claimwin}()$ unless we have $\text{NUM}(\text{CUR})=1$ and the other two $\text{NUM}$ variables $0$, else Bob can call some $\text{claimkill}()$ and win. However, if she validly calls $\text{claimwin}()$ then Bob has no moves and loses. Finally Bob clearly cannot call $\text{claimkill}()$ unless Alice calls $\text{claimwin}()$ first. Bob cannot call $\text{claimwin}()$ unless we have $\text{NUM}(\text{CUR})=0$ (with $\text{CUR}$ defined pre-increment) and $\text{NUM}(\text{CUR}+1)>0$; the latter is necessary to run it in the first place, but if the former doesn't hold then Alice can call $\text{claimkill}()$ to win. Finally Alice clearly cannot call $\text{claimkill}()$ unless Bob calls $\text{claimwin}()$ first. Thus all moves are actually fixed, and proceed as follows: While $\text{NUM}(\text{CUR}) \geq 2$, Alice and Bob must call $\text{basic}()$ once each and repeat. This increases $\text{NUM}(\text{CUR}+1)$ by $1$. If during Alice's turn we have $\text{NUM}(\text{CUR})=0$, then she must call $\text{advance}()$. When this happens, the previous value of $\text{NUM}(\text{CUR})$ (i.e. before we started performing the previous step with the old value of $\text{CUR}$) will have been even, and for a brief moment mid-function call our new value of $\text{NUM}(\text{CUR})$ (with the new value of $\text{CUR}$) will be exactly half of the previous one. Then it decreases by $1$ in the second half of the function call, so we essentially start over with the value of $\text{NUM}(\text{CUR})$ exactly halved. If during Alice's turn we have $\text{NUM}(\text{CUR})=1$ and $\text{NUM}(\text{CUR})>0$, then it must have "originally" (i.e. right after $\text{CUR}$ was last changed to its current value) been odd and not $1$, i.e. $n$ would not have been a power of $2$. Then Alice is still forced to call $\text{basic}()$, but now Bob can run $\text{claimwin}()$ and win. If instead during Alice's turn we have $\text{NUM}(\text{CUR})=1$ but $\text{NUM}(\text{CUR})=0$, then $n$ was originally a power of $2$. Although Alice is still forced to call $\text{basic}()$, Bob can no longer run $\text{claimwin}()$; nor can he call anything else, so he loses. This finishes the problem. $\blacksquare$ Remark: The $\text{STATE}(\bullet,j)$ variables essentially mirror $\text{TURN}(j)$ at all times, so the $\text{TURN}(j)$ existing might not be necessary. However, I think it's easier to think about these two parts of our "program" as separate. Remark: Our final program can be viewed as an implementation of the following pseudocode: int n; int q = 0; while (true) { if (n >= 2) { n -= 2; q++; } else if (n == 1) { if (q == 0) EndAliceWin(); else EndBobWin(); } else if (n == 0) { n = q; q = 0; }; }; I mentioned this in the writeup, but it's quite confusing so I'll repeat it again: in the $n=0$ case, our while loop actually ends with the incrementing of $\text{CUR}$ in $\text{advance}()$, and the next iteration of the loop begins with the decrementing of $\text{NUM}(\text{CUR})$.