= Solution
\b[For $N\ge3$, depth and history-<tree> size can be infinite, while a sufficient finite state bound is $2\cdot5^N$.] The number of possible completed histories also becomes unbounded. With <variables> $p,q,r$, first let $A$ assign $p$ and $B$ assign $q$. Both can then keep flipping their own <variable>, leaving $r$ unassigned. After four such flips the same assignment, ownership and player-to-move recur. Arbitrarily many repetitions can precede assignment of $r$, so there are infinitely many distinct finite complete histories as well as legal infinite plays.
A state must now record ownership: for each <variable> the possibilities are unassigned, $A$-owned false, $A$-owned true, $B$-owned false, and $B$-owned true. Include the player to move, since flips break the old link between turn parity and the number assigned. This gives
$$
\boxed{|V|\le2\cdot5^N.}
$$
Many encoded positions are unreachable, so this is an upper bound. Each nonterminal state has at most $2N$ legal moves: two assignments per unassigned <variable> and one flip per <variable> owned by the acting player. Thus the finite <directed graph> has at most $2N|V|$ <edges> even though its unrolled <game tree> is infinite. The $2^N$ possible final <Boolean valuations> are unchanged, but they no longer count distinct plays or complete ownership states. For $N=1,2$, no player gets a legal opportunity to flip before all <variables> are assigned, so the original finite bounds still apply.
Back to article page
