On an Erdős-Szekeres Game

Questo articolo analizza un gioco a due giocatori ispirato al teorema di Erdős-Szekeres sulle permutazioni, determinando il vincitore e fornendo una strategia vincente per i parametri $a \geq b$ quando $b$ assume i valori 2, 3, 4 o 5.

L'essenziale

Immagina di essere seduto a un tavolo da gioco con un amico. Non state giocando a carte o a dadi, ma a un gioco di logica basato su una sequenza di numeri. Questo è il cuore del paper di Lara Pudwell, che prende un famoso teorema matematico (quello di Erdős e Szekeres) e lo trasforma in una sfida tra due giocatori.

Ecco la spiegazione in italiano, semplice e colorita.

1. Il Gioco: Costruire una Torre di Numeri

Immagina di dover costruire una torre usando dei mattoni numerati da 1 a $n$.

• Le regole: Due giocatori, A e B, prendono a turno un numero e lo aggiungono alla fine della loro torre.
• L'obiettivo (o meglio, la trappola): Il gioco finisce quando qualcuno crea involontariamente una "cattiva" sequenza.
  • Se la torre contiene una sequenza di numeri che salgono (come 1, 3, 5, 7) di una certa lunghezza (diciamo $a$), il giocatore che ha messo l'ultimo numero perde.
  • Se la torre contiene una sequenza di numeri che scendono (come 9, 6, 3, 1) di una certa lunghezza (diciamo $b$), anche in questo caso il giocatore che ha messo l'ultimo numero perde.

È come se steste cercando di evitare di creare una "scala" troppo lunga o una "discesa" troppo ripida. Chi crea la prima scala o discesa proibita, perde la partita (questa versione si chiama misère, ovvero "al contrario", perché di solito chi completa la sequenza vince, ma qui vince chi la evita).

2. La Mappa Magica: Il Tabellone a Griglia

Il problema è che tenere a mente tutti i numeri e le loro relazioni è difficile per il cervello umano. La genialità di questo articolo sta nel trasformare il gioco dei numeri in un gioco di ombreggiatura su un foglio a quadretti.

Immagina una griglia rettangolare:

• Le colonne rappresentano quanto è lunga la sequenza crescente che finisce con l'ultimo numero.
• Le righe rappresentano quanto è lunga la sequenza decrescente che finisce con l'ultimo numero.

Ogni volta che un giocatore aggiunge un numero alla sua torre, deve "colorare" una casella su questa griglia.

• Se il numero è più grande di tutti i precedenti, colora una casella a destra (aumenta la sequenza crescente).
• Se il numero è più piccolo, colora una casella in alto (aumenta la sequenza decrescente).

La regola d'oro: Non puoi colorare una casella qualsiasi. Devi colorare una casella che sia "attaccata" al bordo della zona già colorata. È come se la zona colorata fosse un'invasione di muffa che si espande: puoi solo espanderti dove la muffa tocca il muro bianco.

3. La Strategia: Chi vince?

L'autrice ha scoperto che, a seconda delle dimensioni della griglia (che dipendono dai parametri $a$ e $b$), c'è sempre un modo per vincere, a patto di giocare perfettamente.

• Il caso semplice ($b=2$): Immagina una griglia alta solo una riga. È come una corsa a ostacoli lineare. Chi arriva alla fine perde. La vittoria dipende solo se il numero totale di caselle è pari o dispari. È come giocare a "chi arriva per primo alla porta" ma devi essere l'ultimo a toccarla per perdere.
• Il caso medio ($b=3$ e $b=4$): Qui la griglia ha due o tre righe. L'autrice ha trovato una "danza" perfetta. Se il giocatore 1 (quello che inizia) segue una sequenza precisa di mosse (ad esempio, se l'avversario colora in basso, tu colora in alto, e viceversa), può sempre costringere l'avversario a fare la mossa sbagliata. È come se il giocatore 1 avesse una mappa del tesoro nascosta che l'avversario non vede.
• Il caso complesso ($b=5$): Qui la griglia ha quattro righe. È molto più complicato, come un labirinto con molte più diramazioni. L'autrice ha usato un computer per analizzare milioni di partite e ha scoperto un insieme di "stati sicuri". Se il giocatore 1 riesce a mantenere la griglia in uno di questi stati speciali dopo ogni suo turno, l'avversario è destinato a perdere, indipendentemente da cosa fa. È come se il giocatore 1 tenesse sempre il controllo del centro del labirinto, costringendo l'avversario a correre verso i muri.

4. Perché è importante?

Questo non è solo un gioco divertente.

1. Visualizzazione: Trasforma un problema astratto di numeri in qualcosa di visivo (colorare caselle), rendendolo più facile da capire e insegnare.
2. Strategia: Dimostra che in molti giochi di logica apparentemente caotici, esiste una strategia vincente matematica se si conosce la struttura nascosta.
3. Educazione: È un ottimo strumento per insegnare ai ragazzi come funzionano le sequenze e la logica combinatoria senza spaventarli con formule complicate.

In sintesi

Immagina due giocatori che costruiscono una torre di numeri. L'autrice del paper ci dice: "Non preoccupatevi dei numeri! Guardate invece la mappa a scacchiera che rappresentano. Se sapete come muovervi sulla scacchiera per mantenere il controllo del bordo, potete sempre costringere il vostro avversario a fare la mossa che lo fa perdere".

È come se l'autrice avesse scoperto che, in questo gioco, chi ha la mappa giusta vince sempre, anche contro un avversario molto intelligente.

Sommario tecnico

Ecco una sintesi tecnica dettagliata del paper "On an Erdős-Szekeres Game" di Lara Pudwell, presentata in italiano.

1. Il Problema

Il paper analizza un gioco a due giocatori ispirato al celebre Teorema di Erdős-Szekeres (1935). Il teorema afferma che qualsiasi permutazione di lunghezza $n \ge (a-1)(b-1)+1$ contiene necessariamente una sottosequenza crescente di lunghezza $a$ o una sottosequenza decrescente di lunghezza $b$.

Il gioco si svolge come segue:

• Obiettivo: I giocatori prendono a turno numeri da un insieme per costruire una permutazione.
• Condizione di sconfitta (Misère): Il primo giocatore che completa una sottosequenza crescente di lunghezza $a$ (indicata come $I_a$) o una decrescente di lunghezza $b$ (indicata come $J_b$) perde.
• Parametri: Il gioco è definito da due interi positivi $a$ e $b$. L'articolo si concentra sul caso in cui $a \ge b$ e $b \in \{2, 3, 4, 5\}$.
• Contesto: Sebbene versioni precedenti del gioco siano state studiate (Harary, Sagan, West, 1983; Albert et al., 2009), l'analisi precedente era limitata dalla potenza di calcolo o si concentrava sul gioco "normale" (dove chi completa la sequenza vince). Questo lavoro fornisce strategie analitiche per la versione misère per valori di $b$ fino a 5, indipendentemente da quanto grande sia $a$ (purché $a \ge b$).

2. Metodologia

L'autore introduce un modello geometrico visivo per rappresentare lo stato del gioco, ispirandosi alla dimostrazione del Teorema di Erdős-Szekeres data da Seidenberg (1959) tramite il principio dei cassetti.

• La "Tavola da Gioco" (Board):
  • Il gioco è mappato su una griglia bidimensionale di dimensioni $(b-1) \times (a-1)$.
  • Ogni cella $(c, r)$ rappresenta una coppia ordinata: $c$ è la lunghezza della più lunga sottosequenza crescente che termina con l'ultimo elemento aggiunto, e $r$ è la lunghezza della più lunga sottosequenza decrescente che termina con lo stesso elemento.
  • Una cella viene "ombreggiata" (shaded) quando viene aggiunta un nuovo elemento alla permutazione che corrisponde a quella coppia $(c, r)$.
• Regioni Eliminate:
  • Se una cella $(c, r)$ è ombreggiata, tutte le celle $(c', r')$ con $c' \le c$ e $r' \le r$ sono considerate "eliminate" (non più giocabili).
  • Il gioco diventa quindi un processo di ombreggiatura di celle su una griglia, dove un giocatore può ombreggiare solo una cella "aperta" adiacente al bordo della regione eliminata.
• Equivalenza con il Gioco Chomp:
  • Il gioco è identificato come una variante del gioco combinatorio classico Chomp.
  • Regole del gioco sulla griglia:
    1. Il Giocatore 1 inizia ombreggiando l'angolo in alto a sinistra $(1,1)$.
    2. Ogni mossa successiva deve ombreggiare una cella adiacente (per lato) alla regione eliminata.
    3. Vince il giocatore che ombreggia l'angolo in basso a destra $(a-1, b-1)$, poiché ciò significa che la griglia è completamente eliminata e il prossimo giocatore è costretto a creare una sequenza proibita ($I_a$ o $J_b$).

3. Contributi Chiave e Risultati

L'articolo fornisce strategie vincenti per il Giocatore 1 (Player 1) nella versione misère per $b \in \{2, 3, 4, 5\}$ e $a \ge b$.

Caso $b=2$

• Analisi: La griglia è una singola riga di lunghezza $a-1$.
• Risultato: Il vincitore dipende dalla parità di $a$.
  • Se $a$ è dispari, il Giocatore 1 perde (il Giocatore 2 prende l'ultima cella).
  • Se $a$ è pari, il Giocatore 1 vince.
• Strategia: I giocatori sono costretti a prendere la cella più a sinistra disponibile.

Caso $b=3$

• Risultato: Il Giocatore 1 ha sempre una strategia vincente per $a \ge 3$.
• Strategia: Il Giocatore 1 mantiene uno stato in cui le celle ombreggiate formano una struttura specifica (riga 1 con $i$ celle, riga 2 con $i-1$ celle). Qualsiasi mossa del Giocatore 2 viene contrastata per mantenere questo equilibrio, costringendo il Giocatore 2 a completare la sequenza alla fine.

Caso $b=4$

• Risultato: Il Giocatore 1 ha sempre una strategia vincente per $a \ge 4$.
• Strategia: Il Giocatore 1 mantiene la griglia in uno di due stati specifici di "equilibrio" dopo ogni sua mossa:
  1. Righe 1 e 2 hanno $k$ celle eliminate, riga 3 ha $k-2$.
  2. Riga 1 ha $k$ celle eliminate, righe 2 e 3 hanno $k-1$.
  • Qualsiasi mossa del Giocatore 2 può essere controbattuta per tornare a uno di questi due stati, guidando il gioco verso una vittoria forzata nel finale.

Caso $b=5$ (Contributo Principale)

• Risultato: Il Giocatore 1 ha una strategia vincente per $a \ge 5$. Questo estende i risultati precedenti (che si fermavano a $b=4$ o erano limitati a casi specifici).
• Metodologia: La strategia è stata derivata tramite un'analisi assistita da computer per piccoli valori di $a$, identificando pattern ricorrenti.
• Strategia: Il gioco è diviso in tre fasi: apertura, medio gioco e finale.
  • Il Giocatore 1 mira a lasciare la griglia in uno di 7 stati specifici (insieme $\mathcal{S}$) dopo ogni sua mossa. Questi stati sono definiti dalla parità del numero di celle aperte e dal numero di celle eliminate in ciascuna riga.
  • È dimostrato che da qualsiasi stato in $\mathcal{S}$, qualsiasi mossa del Giocatore 2 può essere controbattuta per tornare a uno stato in $\mathcal{S}$.
  • Quando la griglia si riduce, il Giocatore 1 guida il gioco verso un insieme di stati finali ($\mathcal{E}$) che garantiscono la vittoria.
• Complessità: La strategia per $b=5$ è significativamente più complessa di quelle per $b < 5$, richiedendo una gestione della parità delle celle aperte nella prima riga.

4. Discussione e Implicazioni

• Gioco Normale vs Misère: L'articolo discute anche il gioco "normale" (chi completa la sequenza vince). Viene notato che il gioco normale su una griglia $(b-1) \times (a-1)$ è equivalente al gioco misère su una griglia $(b-2) \times (a-2)$. Questo conferma congetture precedenti su chi vince in base alla parità e ai valori di $b$.
• Efficienza delle mosse: Vengono analizzati il numero minimo e massimo di mosse necessarie per concludere il gioco. Le strategie presentate tendono a produrre permutazioni più corte rispetto al limite massimo teorico di Erdős-Szekeres, specialmente per $b=3$ e $b=4$.
• Limiti e Futuro: L'autore nota che la metodologia diventa sempre più onerosa al crescere di $b$ a causa dell'esplosione combinatoria degli stati. Tuttavia, i dati suggeriscono che il Giocatore 1 potrebbe avere sempre una strategia vincente per $a \ge b \ge 4$ nel gioco normale.
• Connessione con la Teoria dei Permutazioni: Il lavoro collega la teoria dei giochi combinatori alla teoria delle permutazioni, mostrando come la struttura geometrica delle "celle eliminate" codifichi esattamente le informazioni necessarie per determinare il vincitore, indipendentemente dalla permutazione specifica che ha generato quella configurazione (sebbene per $b \ge 4$ più permutazioni possano generare la stessa griglia).

Conclusione

Il paper di Pudwell risolve il problema del vincitore per il gioco di Erdős-Szekeres nella versione misère per $b \in \{2, 3, 4, 5\}$ e $a \ge b$. Il contributo principale risiede nella generalizzazione delle strategie per $b=5$ e nell'introduzione di un modello visivo basato sull'ombreggiatura di griglie che semplifica l'analisi di giochi altrimenti complessi, offrendo nuove intuizioni sulla struttura delle permutazioni che evitano pattern monotoni.