Xerox

Pe baza urmatoarelor observatii, vom reduce problema la a rezolva jocul NIM:

  • Pentru o foaie data, pozitiile punctelor nu conteaza. Intr-adevar, atat timp cat punctele sunt distincte, vom putea duce intotdeauna o curba inchisa, suficient de subtire, pe langa celelelalte puncte.
  • Considerand o foaie cu N puncte, dupa selectarea unei curbe, vom putea lasa celuilalt jucator o foaie cu 0, 1, ..., sau N-1 puncte. Acest lucru se poate face trasand curba prin N, N-1, ..., respectiv 1 punct. Asadar, dintr-o stare cu N puncte, putem ajunge in oricare din starile 0, 1, ..., N-1.
  • Prin obtinerea unei stari din alta, putem rearanja punctele pe foaie (am observat ca pozitiile punctelor nu conteaza). Asadar, geometria foii nu conteaza, chiar daca dupa selectare forma dreptunghiului se distruge.
  • Dintr-o stare cu N puncte se poate ajunge si in alte stari prin scindarea foii in alte doua, selectand pe o curba i puncte, ingloband in interiorul ei alte j puncte si lasand in afara ei restul de N-i-j. Totusi, nu vom face astfel de scindari, fiind suficiente observatiile de la punctul 2.

Problema devine: avem N foi (gramezi), fiecare cu cate un numar Mi de puncte (pietre) pe (in) ea. Fiecare foaie (gramada) cu Mi puncte (pietre) poate ajunge intr-o stare cu 0, 1, ..., sau Mi-1 puncte (pietre) prin trasarea unei curbe prin (luarea unui numar de) puncte (pietre). Aceasta este chiar problema jocului NIM.