Il gioco di Van der Waerden

Maker e Breaker decidono di giocare al gioco di Van der Waerden. Ecco il funzionamento del gioco: la scacchiera è composta da \(n \) numeri, l'insieme \( \{1,2,3,4,\ldots, n \} \). Maker (pedine blu) è il primo giocatore mentre Breaker (pedine rosse) è il secondo. Inizia Maker e poi si prosegue alternandosi ad ogni turno successivo. Nel proprio turno un giocatore posiziona una ed una sola pedina del proprio colore su un numero della scacchiera che non è ancora stato occupato da altre pedine, dopodiché il turno termina ed è il turno dell'altro giocatore. Maker vince se riesce a creare una progressione aritmetica di lunghezza \(k\) con pedine blu, altrimenti se non ci riesce vince Breaker.

Se \(n=9\) e \(k=3\) è facile vedere che vince sempre Maker. Se \(n=8\) e \(k=3\) esiste una strategia vincente per Maker? Qual è il più piccolo \(n\) per cui Maker ha una strategia vincente per \(k=3\) ?

Si con $n=8$ e $k=3$ esiste una strategia vincente per Maker:

Se parto da $4$ ho 6 possibili combinazioni, che sono:

$(1,4,7)$, $(2,3,4)$, $(2,4,6)$, $(3,4,5)$, $(4,5,6)$, $(4,6,8)$

L'avversario dovrà con la sua mossa eliminare quante più terne possibili, il numero più diffuso in queste terne è il $6$, a Maker rimangono: $(1,4,7)$, $(2,3,4)$, $(3,4,5)$. Scegliendo il numero $3$ Maker vince.

Con un ragionamento analogo si vede che maker vince anche con $n=7$ e con $n=6$. Con $n=5$ Maker non ha abbastanza scelte per avere una strategia vincente. Dunque $n = 6$ è il valore più piccolo per cui Maker ha una strategia vincente.

Sei sicuro su \(n=5\)?

Sei sicuro su \(n=5\)?

Già, con $n=5$ si ha:

$(1,2,3)$, $(1,3,5)$, $(2,3,4)$, $(3,4,5)$

Vince anche con $n=5$. Basta scegliere $3$ alla prima mossa e il numero più frequente rimasto come seconda mossa dello stesso giocatore.

Con $n=4$ si ha solo:

$(1,2,3)$, $(2,3,4)$ e non ci sono possibilità