Giochiamo a Nash?

[enomis_costa88]

Sia considerato un quadrato $ 13*13 $ .
Sia diviso in $ 13^2 $ quadratini unitari.

Considero il grafo G così definito:
Ciascuno dei $ 14^2 $vertici dei quadratini unitari è connesso ai 4 (o meno se è sul bordo) vertici che stanno alla sua destra, sinistra, in alto e in basso.
Inoltre in ciascun quadratino unitario il vertice in alto a destra è connesso con il vertice in basso a sinistra.

2 giocatori a turno fanno la seguente mossa:
A colora di blu un vertice a scelta di G, e se questo vertice è connesso ad altri colorati di blu colora anche le connessioni con questi vertici di blu.
Stessa mossa per B solo che colora vertici e connessioni di rosso.

Inizia il giocatore A.

Il giocatore A vince se riesce a colorare di blu un cammino che parta dal lato sinistro del quadrato e che arrivi al lato destro.
Il giocatore B vince se riesce a colorare di rosso un cammino che parta dall'alto del quadrato al basso.

Dimostrare che:
1) Necessariamente uno e solo uno dei due giocatori deve vincere.
2) A possiede una strategia vincente.

Può essere utile al fine del punto 1 trovare un'interpretazione geometrica del problema (Hint: pensate a come si possono disporre gli esagoni sul piano).

[MindFlyer]

Bisogna aggiungere la regola che non si può colorare un vertice già colorato, altrimenti i claim saltano.
Con questa modifica, il gioco si chiama Hex, ed è un esempio classico di gioco in cui esiste una strategia vincente per chi comincia, ma nessuno è in grado di applicarla a livello pratico.

[enomis_costa88]

Questo gioco era chiamato a Princeton come Nash in onore del suo inventore.
In raltà era stato creato alcuni anni prima da un danese, un certo Piet Hein (non nella forma da me descritta ma in una equivalente e molto più piacevole dal punto di vista estetico).
Hein chiamò "incantesimo" (Hex) questo gioco.
La prima versione data da Nash di questo gioco era sotto forma di grafo e esteticamente più "goffa" di quella di Hein, per cui tutti ritengono che abbia scoperto questo splendido gioco del tutto indipendentemente.

PS: Si ovviamente Mind hai ragione (avevo dato per scontato non si potesse ricolorare i vertici e le connessioni sorry).

[piever]

1)
-è impossibile che vincano entrambi i giocatori perché i due cammini si incrocerebbero in un punto che dovrebbe essere sia rosso sia blu, cosa ovviamente impossibile.
-è impossibile che non vinca nessuno dei due giocatori: per impedire a un giocatore la vittoria, l'altro dovrebbe creare un cammino che tagli la scacchiera (o come si chiama) trasversalmente rispetto all'altro giocatore, ma così facendo avrebbe vinto (o ho capito male il funzionamento del gioco, o non riesco proprio a capire il suggerimento sugli esagoni)

2)
Definiamo che una posizione è vinta se chi è di turno può forzare la vittoria, mentre è persa se l'altro giocatore può forzare la vittoria.
Una posizione o è vinta o è persa. Ovviamente da una posizione persa, qualsiasi mossa si giochi, si arriva a una posizione vinta per l'avversario.
Supponiamo per assurdo che la posizione inziale sia persa: il giocatore A colora un punto qualunque. A questo punto il giocatore B dovrebbe avere una posizione vinta, ma se la scacchiera vuota è una posizione persa, evidentemente è una posizione persa anche la scacchiera con un punto colorato dall'avversario.
Quindi la posizione iniziale non è persa, quindi è vinta.

Ci si vede a Pisa.

[Catraga]

E' interessante anche sapere che prima di venire formalizzato il gioco si svolgeva sulle piastrelle dei bagni di Princeton, che sono di forma esagonale...

[enomis_costa88]

o ho capito male il funzionamento del gioco, o non riesco proprio a capire il suggerimento sugli esagoni

No non hai capito male il gioco.

Solo che, come dice Catraga questo gioco ha anche un'interpretazione geometrica che sfrutta la disposizione degli esagoni nello spazio.

Mi pareva che con questa interpretazione fosse più facile concludere il primo punto (che sono prevalentemente considerazioni "topologiche").

Non ho controllato minuziosamente la tua soluzione ma mi pare torni! Bellissima l'idea del secondo punto!

PS ci si vede a Pisa..

[enomis_costa88]

l'altro dovrebbe creare un cammino che tagli la scacchiera (o come si chiama) trasversalmente rispetto all'altro giocatore

Giusto per fare il rompipalle (sorry ) questo pezzo potresti formalizzarlo un po',non mi pare spiegato benissimo.

[piever]

ahem, in effetti se fosse stato durante una gara non avrei scritto esattamente così...

Proviamo a creare una situazione finale in cui nessun giocatore ha vinto.
Coloriamo di Rosso tutti gli archi e tutti i vertici. Ora il Blu deve, colorando di Blu 98 vertici rossi Rossi, interrompere tutti i percorsi vincenti del Rosso. Per farlo deve creare almeno una barriera che vada dall'alto al basso che il Rosso non può oltrepassare. Se i punti di questa barriera non fossero tutti collegati tra loro, al Rosso rimarrebbe almeno un percorso valido, in quanto dati due punti non collegati comunque presi, esiste un percorso avversario che passa tra loro. Quindi i punti della barriera Blu sono collegati fra loro quindi sono un percorso vincente per il Blu.
Quindi se il Rosso vince un giocatore ha vinto e se il rosso non vince allora il blu vince e un giocatore ha vinto.

Dimostrazione non brillantissima ma spero chiara

P.S. Tu come avevi dimostrato il secondo punto?

ciao!