La somma fa 15?

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Due giocatori , \(A\) e \(B\), a turno (cominciando da \(A\)) dicono un numero compreso tra uno e nove senza ripetizione. Il gioco è vinto dal giocatore che ha detto tre numeri la cui somma è 15. Se \(A\) e \(B\) giocano in modo perfetto come termina il gioco? Vince \(A\), \(B\) o finisce in parità?

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

"3m0o":[quote="Martino"]

E la versione $n xx n$ del tic tac toe è una patta per ogni $n ge 3$?

La versione aritmetica sarebbe: A e B scelgono i numeri da $1$ a $n^2$ senza ripetizione e vince chi riesce per primo ad avere $n$ numeri la cui somma è $1/2 n (n^2+1)$.

Se \( n \geq 8 \) la partita finisce in parità. Se \( 3 < n < 8 \) devo pensarci, ma probabilmente finisce in parità.

[/quote]

Ecco, penso che questo dovrebbe dimostrare la mia affermazione precedente.

E' chiaro che il secondo giocatore, \(B\), non ha una strategia vincente, altrimenti il primo giocatore, \(A\) può rubarli la strategia vincente semplicemente sprecando la prima mossa e poi pretendendo di essere il secondo giocatore. Resta da dimostrare che neanche il primo giocatore ha una strategia vincente. Dimostriamo dunque che il secondo giocatore ha una strategia che porta al pareggio.
Chiamiamo la scacchiera del tris \(n\times n \) con \(X\). Ora ciascun elemento \(x \in X \) è selezionabile da un giocatore e ci può mettere una sua pedina (tipicamente una X oppure una O). Denotiamo con \( \mathcal{V} \) la famiglia di insiemi vincenti. Abbiamo chiaramente che \[ X = \bigcup_{ Y \in \mathcal{V} } Y.\]
Il primo giocatore vince il gioco se riesce a coprire con sue pedine tutte le caselle di un certo insieme \(Y \in \mathcal{V} \).
Se per ogni insieme vincente \(Y\) riusciamo a trovare un insieme di rappresentanti \(R_Y \subseteq Y \) tale che \( \left| R_Y \right| =2 \) e tale che dati \( Y_1 , Y_2 \in \mathcal{V} \) abbiamo che \(R_{Y_1} \cap R_{Y_2} = \emptyset \) allora \(B\) riesce a pareggiare la partita. Assumiamo infatti che \(A\) vuole vincere coprendo \( Y \in \mathcal{V} \), ad un certo punto deve coprire \( r \in R_Y \). La strategia di \(B\) è rispondere subito dopo coprendo il punto in \( R_Y \setminus \{ r \} \). Se \(A \) ad una certa mossa non copre nessun punto dei rappresentanti per ogni \( Y \in \mathcal{V} \) allora \(B\) fa quello che vuole.
Questo è praticamente il teorema del matrimonio di Hall applicato a \( \mathcal{W} \), dove \( \mathcal{W} \) contiente due coppie di \(Y \) per ogni \(Y \in \mathcal{V} \). Assumendo quindi che per ogni sottofamiglia \( \mathcal{F} \subseteq \mathcal{V} \) risulta che
\[ \left| \bigcup_{Y \in \mathcal{F} } Y \right| \geq 2 \left| \mathcal{F} \right| \]
otteniamo l'esiste di questi \(R_Y \) per ogni \(Y \in \mathcal{V} \).
Infatti il teorema del matrimonio di Hall afferma che una famiglia \( \mathcal{W} \) di insiemi finiti possiede un sistema di rappresentanti distinti se e solo se \( \mathcal{W} \) soddisfa la condizione che per ogni sottofamiglia \( \mathcal{G} \subseteq \mathcal{W} \) abbiamo che
\[ \left| \mathcal{G} \right| \leq \left| \bigcup_{ Y \in \mathcal{W} } Y \right|. \]

Assumiamo ora \(n \geq 8 \), abbiamo che \( \left| Y \right|= n \) per ogni \( Y \in \mathcal{V} \). Allora per ogni \( \mathcal{F} \subseteq \mathcal{V} \) risulta che
\[ n \left| \mathcal{F} \right| = \sum_{ Y \in \mathcal{F} } \left| Y \right| = \sum_{ x \in \bigcup_{Y \in \mathcal{F}} Y} \sum_{Y \in \mathcal{F} : x \in Y } 1 \]
inoltre ciascun \(x \in X \) appartiene ad al più \(n/2\) insiemi di \( \mathcal{V} \) (poiché abbiamo assunto \( 8 \geq n \)), dunque risulta che
\[ n \left| \mathcal{F} \right| \leq \frac{n}{2} \left| \bigcup_{ Y \in \mathcal{F} } Y \right| \]
pertanto abbiamo che
\[ 2 \left| \mathcal{F} \right| \leq \left| \bigcup_{ Y \in \mathcal{F} } Y \right| \]
e con \(n \geq 8 \) tris finisce in parità.

Ad esempio
\[ \begin{bmatrix}
\beta & 1 &1 & \circ & \circ & \circ& g & \alpha\\
a & \beta & 2 &2 & \circ & \circ & \alpha &h \\
a & b & \circ& 3&3 & \circ &\circ & h \\
\circ & b & c & \circ & 4&4 & \circ & \circ \\
\circ & \circ & c & d & \circ & 5& 5 & \circ \\
\circ & \circ & \circ & d & e & \circ & 6& 6 \\
7 & \circ &\circ & \circ & e & f &\circ & 7\\
8 & 8 & \circ & \circ & \circ & f &g & \circ \\
\end{bmatrix} \]

I numeri sono i rappresentanti delle righe, le lettere delle colonne mentre le lettere greche delle due diagonali che sono gli unici insiemi vincenti, i.e. gli insiemi in \( \mathcal{V} \). Se \( A\) copre un certo rappresentante, diciamo un \(3\), allora \(B\) copre l'altro \(3\) ed \(A\) non può vincere sulla riga \(3\).

Probabilmente con \( 3 \leq n \leq 8 \) riesci a fare una cosa simile ma che dipende dalla prima mossa di \(A\).