Gioco con carta e penna
Vi descrivo un bel giochino che si fa con carta e penna:
Si gioca in due, a turno.
Si inizia col disegnare un po' di croci (X) su un foglio pulito.
Diciamo che ogni croce ha 4 linguette, che sarebbero i quattro piccoli trattini che partono dal centro della croce.
Una mossa consiste nell'unire due linguette (anche della stessa croce) tramite una linea (non necessariamente retta). L'unica condizione è che nel tracciare questa linea non si intersechi niente altro di già disegnato.
Ovviamente le due linguette che costituiscono gli estremi della linea non sono più, di fatto, delle linguette, quindi non potranno essere più usate in nessun modo.
Inoltre ogni volta che si traccia una linea, in un punto di essa (magari approssimativamente al centro) si disegna un trattino che la taglia in due. Si può dire che il trattino è in questo modo a sua volta tagliato in due dalla linea: le due parti in cui viene diviso costituiscono due nuove linguette, che potranno essere usate in altre mosse successivamente.
In ogni turno, un giocatore compie una mossa e poi passa il gioco all'avversario.
Perde chi non può più muovere.
A patto che sia tutto chiaro, le domande sono:
Il gioco finisce sempre?
Determinare chi vince (o se il gioco non termina) in funzione del numero di croci iniziali (ovviamente assumendo che ognuno dei due giocatori giochi al meglio delle sue possibilità...)
Sperando di aver scritto tutto in modo comprensibile, vi auguro buon divertimento
PS: anche se non risolvete completamente il problema, magari anche proporre delle idee o dare degli spunti è ben accetto.
Si gioca in due, a turno.
Si inizia col disegnare un po' di croci (X) su un foglio pulito.
Diciamo che ogni croce ha 4 linguette, che sarebbero i quattro piccoli trattini che partono dal centro della croce.
Una mossa consiste nell'unire due linguette (anche della stessa croce) tramite una linea (non necessariamente retta). L'unica condizione è che nel tracciare questa linea non si intersechi niente altro di già disegnato.
Ovviamente le due linguette che costituiscono gli estremi della linea non sono più, di fatto, delle linguette, quindi non potranno essere più usate in nessun modo.
Inoltre ogni volta che si traccia una linea, in un punto di essa (magari approssimativamente al centro) si disegna un trattino che la taglia in due. Si può dire che il trattino è in questo modo a sua volta tagliato in due dalla linea: le due parti in cui viene diviso costituiscono due nuove linguette, che potranno essere usate in altre mosse successivamente.
In ogni turno, un giocatore compie una mossa e poi passa il gioco all'avversario.
Perde chi non può più muovere.
A patto che sia tutto chiaro, le domande sono:
Il gioco finisce sempre?
Determinare chi vince (o se il gioco non termina) in funzione del numero di croci iniziali (ovviamente assumendo che ognuno dei due giocatori giochi al meglio delle sue possibilità...)
Sperando di aver scritto tutto in modo comprensibile, vi auguro buon divertimento
PS: anche se non risolvete completamente il problema, magari anche proporre delle idee o dare degli spunti è ben accetto.
Risposte
[xdom="giammaria"]Il problema è carino e fa scervellare, ma è un gioco: ritengo opportuno spostarlo in quella sezione. Che poi spesso dietro ai giochi matematici si nascondano problemi anche astrusi è vero, ma cambia poco le cose.[/xdom]
"milizia96":
A patto che sia tutto chiaro, le domande sono:
Il gioco finisce sempre?
Determinare chi vince (o se il gioco non termina) in funzione del numero di croci iniziali (ovviamente assumendo che ognuno dei due giocatori giochi al meglio delle sue possibilità...)
Sperando di aver scritto tutto in modo comprensibile, vi auguro buon divertimento
PS: anche se non risolvete completamente il problema, magari anche proporre delle idee o dare degli spunti è ben accetto.
Ti dico da subito, che vince sempre chi inizia per primo
mi ha incuriosito il problema, cosi ho fatto delle prove:in funzione del numero di croci disegnate, e "assumendo che ognuno dei due giocatori giochi al meglio delle sue possibilità", il numero di mosse per terminare il gioco è di $4k-1$, dove $k$ è il numero di croci disegnate in partenza...si, il gioco finisce sempre! (come puoi ben notare, la formula da come risultato sempre un valore dispari (se giocate con una croce, finirete in $3$ mosse, con 2 croci in $7$ mosse etcetera) di conseguenza, a vincere sarà sempre il primo a iniziare ("assumendo che ognuno dei due giocatori giochi al meglio delle sue possibilità")
Mi dispiace ma... risposta errata! 
Non so se questo dipenda dal fatto che ho spiegato male qualche cosa.
Con una croce sono d'accordo con te: si finisce in 3 mosse.
Ma con 2 croci si finisce in 8...
Non so se questo dipenda dal fatto che ho spiegato male qualche cosa.
Con una croce sono d'accordo con te: si finisce in 3 mosse.
Ma con 2 croci si finisce in 8...
"milizia96":
Mi dispiace ma... risposta errata!
Non so se questo dipenda dal fatto che ho spiegato male qualche cosa.
Con una croce sono d'accordo con te: si finisce in 3 mosse.
Ma con 2 croci si finisce in 8...
Prendo le due croci singolarmente: ognuna si risolve in $3$ mosse: siamo quindi a $6$ in tutto. Da ognuna di queste "pseudo-croci" escono ora un solo rametto a testa: è possibile unirli una volta sola, e siamo a $7$: essendo rimasta una sola linguetta, la partita dovrebbe essere finita
Forse sto scordando qualcosa
Il fatto è che facendo l'ultima unione crei 2 linguette
"milizia96":
Il fatto è che facendo l'ultima unione crei 2 linguette
Diavolaccio, hai ragione
devo rifare i conti allora
P.S.
$5k-2$ ora dovrebbe essere esatto
in questo caso, il vincitore dipende dal numero di croci:
se le croci sono in numero dispari, vince il 1° giocatore, se le croci sono pari, vince il 2° giocatore.
Bene, la risposta è quella
Ma se hai voglia sarebbe bello dare qualche spiegazione, non necessariamente formale ma almeno convincente.
Ah, fatto importante: a questo punto ti si potrebbe domandare: qual è la strategia che permette di vincere? (cioè, com'è che si gioca "al meglio delle proprie possibilità"?)
Ma se hai voglia sarebbe bello dare qualche spiegazione, non necessariamente formale ma almeno convincente.
Ah, fatto importante: a questo punto ti si potrebbe domandare: qual è la strategia che permette di vincere? (cioè, com'è che si gioca "al meglio delle proprie possibilità"?)
Nessuno si fa avanti per spiegare il perché di quella risposta?
Allora ecco un mega-suggerimento (leggetelo solo se non sapete che pesci pigliare):
Allora ecco un mega-suggerimento (leggetelo solo se non sapete che pesci pigliare):
dimostriamo la formula \(\displaystyle 5n-2 \) per induzione
passo base: gia fatto
passo induttivo: che se vale per n ,vale anche per n+1
con n mosse il gioco è terminato ,cioè ogni estremo di trattino non puo raggiungerne un altro perche il percorso è bloccato da altri collegamenti, quest'ultimi delimitano il piano in tanti piccoli spazi chiusi
immaginiamo ora di disegnare l' n+1-esima croce in uno di questi spazi
abbiamo che per chiudere il gioco saranno necessarie \(\displaystyle 5n-2+5=5(n+1)-2 \)
se dimostrassimo quella formula,avremmo finito,cerchiamo dunque di capire perche quel \(\displaystyle +5 \)
intanto \(\displaystyle +3 \) c'è dato dalla risoluzione singola di una croce
\(\displaystyle +1 \) per il collegamento tra il trattino utilizzabile e quello del trattino padrone del sottospazio scelto
\(\displaystyle +1 \) perche l'ultimo collegamento effettuato,crea un altro trattino collegabile facendo passare il collegamento intorno alla croce,inoltre il numero di mosse per risolvere una croce è costante,come facilmente si nota facendo tentativi su una sola,da cui la tesi.
Poi per il fatto di chi vince,semplicemente perche la parita di n si alterna, e si ricavano banali considerazioni mod 2.
Infine per la dimostrare la strategia vincente si potrebbe prendere come invariante (e dimostrarlo) che prendeno una croce, la risoluzione è univoca,qualsiasi siano le mosse e poi provare a generalizzare per insiemi di croci,ma mi pare un po contoso.
Oppure dato che abbiamo stabilito che il numero di mosse è fisso a prescindere su \(\displaystyle 5n-2 \), possiamo anche dire che dato che ogni giocatore fa una mossa a turno,una strategia nn serve visto che il gioco termina nell'istante in cui si arriva alla formula, e la vittoria dipende solo dalla parita dell'espressione. (quest'ultima considerazione potrebbe altamente essere sballata, se è cosi è colpa dell'ora in cui scrivo)
passo base: gia fatto
passo induttivo: che se vale per n ,vale anche per n+1
con n mosse il gioco è terminato ,cioè ogni estremo di trattino non puo raggiungerne un altro perche il percorso è bloccato da altri collegamenti, quest'ultimi delimitano il piano in tanti piccoli spazi chiusi
immaginiamo ora di disegnare l' n+1-esima croce in uno di questi spazi
abbiamo che per chiudere il gioco saranno necessarie \(\displaystyle 5n-2+5=5(n+1)-2 \)
se dimostrassimo quella formula,avremmo finito,cerchiamo dunque di capire perche quel \(\displaystyle +5 \)
intanto \(\displaystyle +3 \) c'è dato dalla risoluzione singola di una croce
\(\displaystyle +1 \) per il collegamento tra il trattino utilizzabile e quello del trattino padrone del sottospazio scelto
\(\displaystyle +1 \) perche l'ultimo collegamento effettuato,crea un altro trattino collegabile facendo passare il collegamento intorno alla croce,inoltre il numero di mosse per risolvere una croce è costante,come facilmente si nota facendo tentativi su una sola,da cui la tesi.
Poi per il fatto di chi vince,semplicemente perche la parita di n si alterna, e si ricavano banali considerazioni mod 2.
Infine per la dimostrare la strategia vincente si potrebbe prendere come invariante (e dimostrarlo) che prendeno una croce, la risoluzione è univoca,qualsiasi siano le mosse e poi provare a generalizzare per insiemi di croci,ma mi pare un po contoso.
Oppure dato che abbiamo stabilito che il numero di mosse è fisso a prescindere su \(\displaystyle 5n-2 \), possiamo anche dire che dato che ogni giocatore fa una mossa a turno,una strategia nn serve visto che il gioco termina nell'istante in cui si arriva alla formula, e la vittoria dipende solo dalla parita dell'espressione. (quest'ultima considerazione potrebbe altamente essere sballata, se è cosi è colpa dell'ora in cui scrivo)
Uh bello questo! Peccato che sia finito in giochi matematici Per curiosità: dove l'hai trovato?
Sto sveglio a quest'ora giusto perchè dovrei studiare molta filosofia
Comunque @wall98 sei sicuro che quell'induzione ha validità generale? Cioè non ho ben ragionato su tutti i passaggi però a prima vista il fatto di prendere una croce nuova in uno spazio già delimitato senza ulteriori spiegazioni non mi è ben chiaro se si possa fare
In teoria una volta dimostrato che il gioco finisce, si potrebbe trasformare il grafo in un grafo planare considerando i punti di intersezione tra i segmenti tracciati come se fossero dei vertici. E' inoltre possibile determinare univocamente anche il numero di facce che avrà questo grafo mentre il numero di vertici e di spigoli può essere calcolato in funzione del numero di mosse effettuate. Dopodichè impostando l'equazione $S=F+V-2$ si ricava il numero di mosse effettuate. Una via un po' brutale forse ma potrebbe funzionare.
Per curiosità: dove l'hai trovato?Sto sveglio a quest'ora giusto perchè dovrei studiare molta filosofia
Comunque @wall98 sei sicuro che quell'induzione ha validità generale? Cioè non ho ben ragionato su tutti i passaggi però a prima vista il fatto di prendere una croce nuova in uno spazio già delimitato senza ulteriori spiegazioni non mi è ben chiaro se si possa fare
In teoria una volta dimostrato che il gioco finisce, si potrebbe trasformare il grafo in un grafo planare considerando i punti di intersezione tra i segmenti tracciati come se fossero dei vertici. E' inoltre possibile determinare univocamente anche il numero di facce che avrà questo grafo mentre il numero di vertici e di spigoli può essere calcolato in funzione del numero di mosse effettuate. Dopodichè impostando l'equazione $S=F+V-2$ si ricava il numero di mosse effettuate. Una via un po' brutale forse ma potrebbe funzionare.
"xXStephXx":
Sto sveglio a quest'ora giusto perchè dovrei studiare molta filosofia
Almeno tu fai qualcosa di serio,io sono rimasto incastrato con degli amici su chi spegne il computer piu tardi scrivendo cose su ask,quanto vorrei studiare filosofia
tornando al problema,ho supposto che la formula vale per n, poi sono passato ad n+1, aggiungendo una croce in piu alle n, ora la croce la posso mettere dove voglio senza perdita di generalita poiche come ho detto gli spazi sono tutti delimitati da collegamenti gia fatti,e tutti i collegamenti collegabili sono gia stati collegati,quindi gli spazi dovrebbero avere le stesse proprieta topologiche (forse si dice cosi), infatti non mi interessa quando sia grande una partizione di piano,bensi se questa partizione è effettivamente isolata,e lo è perche tutto è gia stato collegato.
Magari pero mi sbaglio eh
L'unica pecca del tuo ragionamento è che non puoi supporre di aver collegato tutto il collegabile di $n$ croci, e poi solo alla fine incominciare a trattare l'ultima croce. Non potresti, diciamo, trattare le croci "uniformemente" cioè le usi un po' tutte senza lasciarne una "esclusa" fino alla fine?
[ot]Dove l'ho trovato? Scritto da nessuna parte, è semplicemente un gioco raccontato a caso in pizzeria l'ultima volta a Pisa[/ot]
[ot]Dove l'ho trovato? Scritto da nessuna parte, è semplicemente un gioco raccontato a caso in pizzeria l'ultima volta a Pisa
[/ot]
"milizia96":
oppure... basta fare mosse a caso tanto non cambia nulla?
Comunque devo ancora rivedere bene (anche se stò avendo problemi nell'analizzare $3$ o più croci, di sicuro con $1$ o $2$ croci il vincitore è rispettivamente e sicuramente il giocatore $1$ e il giocatore $2$)
Comunque, quello che volevo dire ieri/qualche ora fa, è che si può considerare il "disegno" del gioco come un grafo planare dove i vertici sono gli estremi delle croci più i punti di intersezione che si vengono a creare tracciando la nuova linea al centro di un collegamento. Ora ho che all'inizio della partita i vertici di primo grado sono $4n$ (gli estremi delle croci). Ad ogni mossa ci sono due vertici di primo grado che diventano di secondo grado, ma si vengono a creare due vertici nuovi di primo grado. Quindi il numero di vertici di primo grado rimane costante a $4n$. Il gioco, supponendo che finisce (ehm... xD), finirà quando tutti questi vertici di primo grado si troveranno in "facce" del grafo isolate tra loro. Quindi servono almeno $4n$ facce diverse a gioco terminato. Non è possibile ottenerne di più perchè per "chiudere" una nuova faccia si viene sempre a creare un vertice di primo grado che resta intrappolato al suo interno. Quindi le facce saranno $4n$ a gioco terminato.
Ora supponendo che faccio $x$ mosse.. il numero di vertici è dato dal numero di vertici iniziali $5n$ (5 per croce: estremi + il centro) più il numero di vertici che si aggiungono con ogni mossa (che sono 3: il centro della nuova linguetta e i suoi estremi). Quindi avrò $V=5n+3x$. Gli spigoli invece sono dati dal numero di spigoli iniziali (4 per croce) più queli che si aggiungono ad ogni mossa (che sono 4, in pratica i 4 bracci della nuova croce che si forma). In totale $S=4n+4x$.
Ora ho che con $S=V+F-2$ ottengo $4n+4x=5n+3x+4n-2$ Da cui $x=5n-2$.
Ora supponendo che faccio $x$ mosse.. il numero di vertici è dato dal numero di vertici iniziali $5n$ (5 per croce: estremi + il centro) più il numero di vertici che si aggiungono con ogni mossa (che sono 3: il centro della nuova linguetta e i suoi estremi). Quindi avrò $V=5n+3x$. Gli spigoli invece sono dati dal numero di spigoli iniziali (4 per croce) più queli che si aggiungono ad ogni mossa (che sono 4, in pratica i 4 bracci della nuova croce che si forma). In totale $S=4n+4x$.
Ora ho che con $S=V+F-2$ ottengo $4n+4x=5n+3x+4n-2$ Da cui $x=5n-2$.
Benissimo Steph! (anche se completamente diverso da come lo stavo pensando io...)
Resterebbe solo da determinare se effettivamente il gioco finisce prima o poi...
Resterebbe solo da determinare se effettivamente il gioco finisce prima o poi...
In teoria una volta saputo che se finisce, termina dopo $5n-2$ mosse si può barare un po' euristicamente... basta infatti dimostrare che si viene a creare un grafo planare.
Allora dimostro per induzione che il gioco finisce dopo $5n-2$ mosse.
Passo base: si nota che con una croce finisce dopo $3$ mosse.
Passo induttivo: Se con $n-1$ croci finisce, allora con $n$ croci finisce in $5n-2$ mosse.
Dimostrazione:
Suppongo che una croce rimanga sempre scollegata dalle altre. Ma allora mi trovo a operare separatamente con $n-1$ croci e con la croce scollegata e prima o poi non ho più mosse per ipotesi induttiva. Così prima o poi collego anche la croce scollegata. Fatto ciò ho un bel grafo planare come prima e senza ripetere tutti i ragionamenti con Eulero posso calcolarmi anche le facce in funzione delle mosse fatte. Infatti se fin'ora ho fatto $x$ mosse, allora dalla relazione precedente ho che $4n+4x=5n+3x+F-2$ da cui $F=x-n+2$ (quantità sempre positiva visto che per collegare tutte le croci servono almeno n-1 mosse). Ora sempre per il fatto che il numero di facce non può superare $4n$ (infatti per ogni nuova faccia si viene a creare un vertice di primo grado bloccato al suo interno, ma il numero di vertici di primo grado è invariante a $4n$), ho che $x$ non può crescere oltre $5n-2$. Quindi il gioco finisce entro $5n-2$ mosse. Inoltre affinchè finisca servono almeno $4n$ facce, altrimenti non riesco ad isolare tutti i vertici. Unendo le due cose ottengo che finisce dopo $5n-2$ mosse.
A questo punto si poteva ragionare anche in un altro modo abbastanza parallelo notando che una volta che tutte le croci sono collegate tra loro, ogni mossa implica la creazione di una nuova regione di spazio. Quindi sempre usando l'induzione, posso collocarmi nell'istante immediatamente precedente a quello in cui tutte le croci sono collegate e ho che ci sono n-1 croci collegate tra loro e una scollegata. Supponendo anche che ci siano $k$ regioni di spazio ho che per arrivare fino a lì ho usato $n-2$ mosse per collegare le $n-1$ croci e $k-1$ mosse per formare $k$ regioni di spazio (perchè una regione c'è già dall'inizio) e quindi $n+k-3$. Poi per collegare l'ultima croce spreco una mossa e le regioni non aumentano facendo quindi $n+k-2$ mosse. E per finire siccome d'ora in avanti ad ogni mossa ne segue una nuova regione posso fare ancora altre $4n-k$ mosse per un totale di $5n-2$. Forse se formalizzata un po' meglio potrebbe funzionare anche questa strada Ma ormai praticamente era spoileratissima dopo aver usato eulero
Allora dimostro per induzione che il gioco finisce dopo $5n-2$ mosse.
Passo base: si nota che con una croce finisce dopo $3$ mosse.
Passo induttivo: Se con $n-1$ croci finisce, allora con $n$ croci finisce in $5n-2$ mosse.
Dimostrazione:
Suppongo che una croce rimanga sempre scollegata dalle altre. Ma allora mi trovo a operare separatamente con $n-1$ croci e con la croce scollegata e prima o poi non ho più mosse per ipotesi induttiva. Così prima o poi collego anche la croce scollegata. Fatto ciò ho un bel grafo planare come prima
e senza ripetere tutti i ragionamenti con Eulero posso calcolarmi anche le facce in funzione delle mosse fatte. Infatti se fin'ora ho fatto $x$ mosse, allora dalla relazione precedente ho che $4n+4x=5n+3x+F-2$ da cui $F=x-n+2$ (quantità sempre positiva visto che per collegare tutte le croci servono almeno n-1 mosse). Ora sempre per il fatto che il numero di facce non può superare $4n$ (infatti per ogni nuova faccia si viene a creare un vertice di primo grado bloccato al suo interno, ma il numero di vertici di primo grado è invariante a $4n$), ho che $x$ non può crescere oltre $5n-2$. Quindi il gioco finisce entro $5n-2$ mosse. Inoltre affinchè finisca servono almeno $4n$ facce, altrimenti non riesco ad isolare tutti i vertici. Unendo le due cose ottengo che finisce dopo $5n-2$ mosse.A questo punto si poteva ragionare anche in un altro modo abbastanza parallelo notando che una volta che tutte le croci sono collegate tra loro, ogni mossa implica la creazione di una nuova regione di spazio. Quindi sempre usando l'induzione, posso collocarmi nell'istante immediatamente precedente a quello in cui tutte le croci sono collegate e ho che ci sono n-1 croci collegate tra loro e una scollegata. Supponendo anche che ci siano $k$ regioni di spazio ho che per arrivare fino a lì ho usato $n-2$ mosse per collegare le $n-1$ croci e $k-1$ mosse per formare $k$ regioni di spazio (perchè una regione c'è già dall'inizio) e quindi $n+k-3$. Poi per collegare l'ultima croce spreco una mossa e le regioni non aumentano facendo quindi $n+k-2$ mosse. E per finire siccome d'ora in avanti ad ogni mossa ne segue una nuova regione posso fare ancora altre $4n-k$ mosse per un totale di $5n-2$. Forse se formalizzata un po' meglio potrebbe funzionare anche questa strada
Ma ormai praticamente era spoileratissima dopo aver usato eulero
A questo punto metto anche i punti chiave della mia dimostrazione (senza spiegare tutto in dettaglio)
Immaginate che ciò che avete disegnato sul foglio sia una sorta di labirinto, cioè ogni linea che avete disegnato è un muro.
Voi vi trovate appunto vicino a uno di questi muri e, tenendo la mano destra "incollata" su di esso, cominciate a camminare, contando nel vostro tragitto quante "linguette" sfiorate con la mano.
A un certo punto vi ritroverete al punto di partenza: supponete di aver contato $k$ linguette.
Giusto per fare un esempio: se visitate il labirinto all'inizio del gioco conterete $4$ linguette, cioè quelle della croce a cui avete "girato intorno".
Ora incominciano i punti salienti del discorso:
per ora supponiamo che le linguette che abbiamo sfiorato si possano unire soltanto tra di loro e con le loro "discendenti" (cioè linguette frutto dell'unione di due di loro). E' facile dimostrare per induzione su $k$ che per "finire di giocare" con queste linguette serviranno esattamente $k-1$ mosse.
Cosa succede invece quando connettiamo due porzioni del labirinto non collegate tra loro?
E' facile dimostrare che, ogni volta che connettiamo due regioni sconnesse, il numero di mosse per finire il gioco aumenta di $2$ (rispetto a come sarebbe stato se avessimo "esaurito" le due porzioni indipendentemente, senza mai collegarle tra loro).
A questo punto è fatta: all'inizio abbiamo $n$ croci, cioè $n$ regioni sconnesse ognuna delle quali impiegherebbe $4-1=3$ mosse per esaurirsi. Il tutto si esaurirebbe in $3n$ mosse.
Ma dobbiamo per forza connettere tutto, e per connettere tra loro $n$ regioni sconnesse servono esattamente $n-1$ connessioni. Ad ogni connessione il numero di mosse totali aumenta di $2$.
Quindi numero di mosse totali = $3n+2(n-1)=5n-2$
Spero che dopo tutta la fatica fatta per scrivere questa roba almeno abbiate capito le linee generali del mio discorso...
Immaginate che ciò che avete disegnato sul foglio sia una sorta di labirinto, cioè ogni linea che avete disegnato è un muro.
Voi vi trovate appunto vicino a uno di questi muri e, tenendo la mano destra "incollata" su di esso, cominciate a camminare, contando nel vostro tragitto quante "linguette" sfiorate con la mano.
A un certo punto vi ritroverete al punto di partenza: supponete di aver contato $k$ linguette.
Giusto per fare un esempio: se visitate il labirinto all'inizio del gioco conterete $4$ linguette, cioè quelle della croce a cui avete "girato intorno".
Ora incominciano i punti salienti del discorso:
per ora supponiamo che le linguette che abbiamo sfiorato si possano unire soltanto tra di loro e con le loro "discendenti" (cioè linguette frutto dell'unione di due di loro). E' facile dimostrare per induzione su $k$ che per "finire di giocare" con queste linguette serviranno esattamente $k-1$ mosse.
Cosa succede invece quando connettiamo due porzioni del labirinto non collegate tra loro?
E' facile dimostrare che, ogni volta che connettiamo due regioni sconnesse, il numero di mosse per finire il gioco aumenta di $2$ (rispetto a come sarebbe stato se avessimo "esaurito" le due porzioni indipendentemente, senza mai collegarle tra loro).
A questo punto è fatta: all'inizio abbiamo $n$ croci, cioè $n$ regioni sconnesse ognuna delle quali impiegherebbe $4-1=3$ mosse per esaurirsi. Il tutto si esaurirebbe in $3n$ mosse.
Ma dobbiamo per forza connettere tutto, e per connettere tra loro $n$ regioni sconnesse servono esattamente $n-1$ connessioni. Ad ogni connessione il numero di mosse totali aumenta di $2$.
Quindi numero di mosse totali = $3n+2(n-1)=5n-2$
Spero che dopo tutta la fatica fatta per scrivere questa roba almeno abbiate capito le linee generali del mio discorso...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo