Αφαίρεση Τετραγώνων & Ακολουθία Sprague–Grundy: Παρτίδες και Στρατηγική

Δύο παίκτες παίζουν εναλλάξ αφαιρώντας κάθε φορά έναν θετικό τέλειο τετράγωνο από έναν αρχικό φυσικό αριθμό n (π.χ. 1, 4, 9, 16, …), με την προϋπόθεση ότι το αποτέλεσμα παραμένει μη αρνητικό. Χάνει όποιος δεν μπορεί να κινηθεί.

Η ακολουθία Sprague–Grundy $(g(n))$ για αυτό το παιχνίδι ορίζεται αναδρομικά:

• $g(0)=0$.

• Για κάθε θέση $n>0$, το $g(n)$ είναι ο μικρότερος μη αρνητικός ακέραιος που δεν εμφανίζεται στο σύνολο $\{\,g(n-s)\mid s \text{ τέλειο τετράγωνο},\, s\le n\,\}$.

Ενδεικτικά, για τις πρώτες θέσεις ισχύει:

$$\begin{aligned} &g(0)=0,\quad g(1)=1,\quad g(2)=0,\quad g(3)=1,\quad g(4)=2,\\ &g(5)=0,\quad g(6)=1,\quad g(7)=0,\quad g(8)=1,\quad g(9)=2,\quad g(10)=0. \end{aligned}$$

Παράδειγμα: Αν ξεκινήσουμε από $n=74$, ο παίκτης A μπορεί να αφαιρέσει $64$ και να φέρει το παιχνίδι στο $10$, μια θέση με $g(10)=0$. Από εκεί και πέρα, ό,τι κι αν παίξει ο B, ο A διατηρεί το πλεονέκτημα (π.χ. αν ο B πάει σε $9$ ή $1$, είναι προφανές· αν πάει σε $6$, ο A απαντά σε $5$, που επίσης έχει $g(5)=0$, κ.ο.κ.).

Άσκηση:
Ποια είναι η νικηφόρα στρατηγική όταν ο αρχικός αριθμός είναι $n=200$; Και όταν είναι $n=500$; (Να περιγράψετε τη λογική της κίνησης του πρώτου παίκτη.)