OFFSET
1,2
COMMENTS
For many n (1 <= n <= 100), optimal play leads to a draw.
LINKS
Michael S. Branicky, Table of n, a(n) for n = 1..200
Michael S. Branicky, Python program for generating b-file
EXAMPLE
For n = 2 there are 4 valid states of the game: (A=1,1 B=1,1) starts the game. There is only one valid move, leading to (A=1,1 B=1,2). Now A also has only one choice (A=1,2 B=1,2), and B ends the game in the state (A=1,2 B=2,2) and wins. A has no valid move, since then one of his numbers would be larger than 2.
PROG
(Other) #include <climits> #include <iostream> #include <map> class State; typedef unsigned char byte; typedef std::map<State, int> ScoreMap; static inline int min(int a, int b) { return a < b ? a : b; } static inline int max(int a, int b) { return a > b ? a : b; } static inline int compare(int a, int b) { return a - b; }
static int MAX = 0; static ScoreMap score; struct State { byte a, b, c, d; State() : a(0), b(0), c(0), d(0) {} State(byte a, byte b, byte c, byte d) : a(min(a, b)), b(max(a, b)), c(min(c, d)), d(max(c, d)) {} int getChildren(State *children) { int n = 0; if (a + c <= MAX) children[n++ ] = State(c, d, a + c, b); if (a + d <= MAX && c != d) children[n++ ] = State(c, d, a + d, b);
if (a != b && b + c <= MAX) children[n++ ] = State(c, d, a, b + c); if (a != b && c != d && b + d <= MAX) children[n++ ] = State(c, d, a, b + d); return n; }; int getScore() { ScoreMap::iterator it = score.find(*this); if (it != score.end()) return it->second; State children[4]; int nchildren = getChildren(&children[0]); int iscore; if (nchildren == 0) { iscore = compare(a + b, c + d); } else { iscore = INT_MIN; for (int i = 0; i < nchildren; i++) iscore = max(iscore, -children[i].getScore()); } score.insert(ScoreMap::value_type(*this, iscore)); return iscore; }; };
static bool operator< (State a, State b) { if (a.a < b.a) return true; if (a.a > b.a) return false; if (a.b < b.b) return true; if (a.b > b.b) return false; if (a.c < b.c) return true; if (a.c > b.c) return false; if (a.d < b.d) return true; if (a.d > b.d) return false; return false; } int main() { std::cout << "max\tscore\tnstates" << std::endl; for (int max = 0; max < 1024; max++) { MAX = max; score.clear(); int iscore = State(1, 1, 1, 1).getScore(); std::cout << max << "\t" << iscore << "\t" << score.size() << std::endl; } return 0; }
(Python)
from collections import deque
def a(n):
reach, pq = {((1, 1), (1, 1))}, deque([((1, 1), (1, 1))])
while len(pq) > 0:
qa, qb = pq.pop() # first tuple, qa, is player-to-move
for i, j in [(0, 0), (0, 1), (1, 0), (1, 1)]:
if qa[i] + qb[j] <= n:
qn = (qb, tuple(sorted((qa[i] + qb[j], qa[1-i]))))
if qn not in reach:
pq.append(qn)
reach.add(qn)
return len(reach)
print([a(n) for n in range(1, 41)]) # Michael S. Branicky, Jan 30 2023
(Python) # see link for faster generation of initial segment of sequence
CROSSREFS
KEYWORD
nonn
AUTHOR
Roland Illig (roland.illig(AT)gmx.de), Jun 12 2009
EXTENSIONS
a(39) and beyond from Michael S. Branicky, Jan 30 2023
STATUS
approved