martedì, luglio 27, 2010

Fiammiferi

Due uomini siedono ad un tavolo rotondo e hanno a disposizione un numero praticamente illimitato di fiammiferi. Decidono di giocare ad un gioco: a ciascun turno uno di loro poggerà un fiammifero sul tavolo, in maniera tale che non tocchi alcun fiammifero già presente, e il gioco avrà fine quando non sarà più possibile poggiare ulteriori fiammiferi. Supponendo che entrambi i giocatori sono infinitamente abili e intelligenti (sicuramente sceglieranno la strategia migliore e hanno l'abilità manuale necessaria per disporre i fiammiferi esattamente come prevede la strategia che hanno in mente) chi dei due vincerà la partita, il primo che poggia un fiammifero sul tavolo oppure il suo avversario? (Chiaramente la condizione per vincere è essere stato l'ultimo a disporre con successo un fiammifero).

21 commenti:

Sixam ha detto...

Chiarimento 1: un fiammifero puo' sporgere dal tavolo (ovviamente senza cadere...)?
Chiarimento 2: i fiammiferi devono essere lasciati integri (cioe' non posso accenderne uno se e' rimasto spazio x meta' fiabbifero)?

Grazie
Bye by SixaM 8-]

Sixam ha detto...

Chiarimento 3 (a scoppio ritardato): c'e' una distanza minima tra due fiammiferi al di sotto della quale 'si toccano'? O devono 'fisicamente' non toccarsi (quindi anche un picometro conta)?

Bye by SixaM 8-]

Walter ha detto...

Purché queste regole valgano allo stesso modo per entrambi i giocatori le si può fissare a piacimento. Io sarei dell'idea che i fiammiferi non possono sporgere, che devono restare integri e che possono essere vicini quanto si vuole purché non si tocchino. Ma in realtà tutto ciò non modifica la soluzione del problema: chi vince con queste regole vincerebbe anche con qualunque permutazione delle stesse (purché, lo ripeto, le regole valgano per entrambi).

cip999 ha detto...
Questo commento è stato eliminato dall'autore.
cip999 ha detto...

per me la strategia migliore sarebbe quella di cominciare dal centro cercando di formare un triangolo equilatero, ma ci sono infinite combinazioni, a seconda della mossa che sceglie l'avversario.
in ogni caso, il primo a cominciare ha una mossa di vantaggio sull'avversario, un po' come nel gioco degli scacchi, quindi secondo me è sempre il primo a vincere(naturalmente scegliendo la giusta strategia).

Walter ha detto...

Ovviamente c'è da dire una cosa: anche se i due giocatori dovessero concordare che i fiammiferi si possono accendere, ad ogni turno comunque qualcuno DEVE mettere un fiammifero (spento) sul tavolo, non può certo bruciarlo tutto e dire "è finito" :D
Ciò perché, come faceva notare cip999, il gioco non può certo durare all'infinito e poi altrimenti ciascuno potrebbe, al suo turno, bruciare un intero fiammifero e passare il turno, così che non si arriverebbe mai ad un vincitore.

Ad ogni modo vi sconsiglio di riflettere troppo su fiammiferi parzialmente bruciati o in bilico: la soluzione è indipendente da questo. Senz'altro è più semplice pensare ai fiammiferi come integri e integralmente sul tavolo ;)

cip999 ha detto...

allora, la strategia migliore sarebbe quella di lasciare sempre sul tevolo uno spazio più grande di quello che può occupare un intero fiammifero(quindi anche bruciandolo parzialmente o mettendolo in bilico se necessario), facendo sì che l'avversario non riesca a occupare tutto il restante spazio. a tale scopo potrei bruciare un fiammifero anche al punto di far rimanere solamente un millesimo di millimetro(abbiamo detto che i due giocatori sono abilissimi).
comunque, anche lasciando sul tavolo uno spazio uguale o minore dell'area di un fiammifero(e quindi facendo in modo che l'avversario possa inserire un intero fiammifero o parte di esso senza lasciare spazi), non essendo fissata una distanza minima tra un fiammifero e l'altro, potrei comunque inserire una particina di fiammifero tra altri due.
quindi penso che ci siano troppe poche informazioni per determinare una soluzione logica.

cip999 ha detto...

in pratica, per essere più conciso, quello che voglio dire è che se è vero che esistono infiniti punti, questo enigma non ha soluzioni.

Walter ha detto...

Ho capito ciò che intendi, ma non sono d'accordo: il tavolo ha una superficie finita, e anche i fiammiferi (o frammenti di tali) devono occupare una superficie finita, per quanto piccola.
Di conseguenza poiché ad ogni turno ciascuno DEVE occupare una superficie finita di un tavolo di dimensioni finite, dopo un numero finito di turni non ci sarà più spazio sufficiente ad aggiungere un ulteriore fiammifero (o frammento di tale).

Riassumendo i due giocatori possono concordare una qualunque dimensione minima di fiammifero, ma poiché qualunque dimensione, per quanto piccola, è comunque finita, il gioco non può che avere un numero finito di turni.

cip999 ha detto...

sono ancora più confuso di prima =D

Walter ha detto...

Mi spiego meglio: hai detto, giustamente, che un tavolo, anche se non è infinitamente grande, ha infiniti punti. È vero, ma ogni fiammifero (anche parte di esso) non può occupare un punto, dato che il punto non ha dimensione. Deve infatti occupare una certa area, per quanto piccola. Volendo fare un esempio, se il tavolo è grande 1 m^2 e supponiamo che la minima dimensione concordata per un fiammifero sia 1 mm^2, allora sul tavolo entreranno 1 milione di fiammiferi (a patto che siano disposti nella maniera ottimale), non uno di più. Cambiando le dimensioni del tavolo o dei fiammiferi cambia il numero massimo di fiammiferi, ma non cambia il fatto che è comunque un numero finito.

Ad ogni modo, lo ripeto: questa è un'inutile complicazione: supponete per semplicità i fiammiferi debbano restare interi e debbano stare per intero sul tavolo, vi assicuro che la soluzione trovata in questo modo è uguale a quella che si troverebbe se si desse la possibilità di bruciare (per metà, per tre quarti o comunque per una frazione finita e minore di 1) i fiammiferi prima di disporli sul tavolo.

cip999 ha detto...

supponiamo, per semplicità, che l tavolo sia quadrato e non rotondo e abbia un'area totale di 1 m^2, che ciascun fammifero occupi uno spazio di 1 mm^2 e che non sia possibile bruciare fiammiferi. come ha già detto walter, disposti nella maniera più ottimle nel tavolo entrano 1000000 di fiammiferi. qindi, essendo un numero pari, vincerà sicuramente il secondo giocatore che ha cominciato.
ora proviamo ad "allungare" due lati del tavolo di mezzo millimetro ciascuno, ottenendo così un'area del tavolo pari a 1001000,25 mm^2(in cui entrano quindi 1001000,25 fiammmiferi). ora, 1001000 è un numero pari, quindi il 1001000° fiammifero sarà posizionato dal secondo giocatore. il primo giocatore, non potendo bruciare fiammiferi, non riuscirà mai a posizionare 1/4 di fiammifero sul tavolo, neance facendolo sporgere dal tavolo(perchè il baricentro si troverebbe al di là del bordo), e quindi la vittoria sarebbe di nuovo del secondo giocatore.
ora incrementiamo la lunghezza dei lati di 1 mm, avndo così un'area totale di 1002001 mm^2. essendo 1002001 un numero dispari, l'ultimo fiammifero sarà posizionato dal primo giocatore, che quindi vincerà la partita.
se non ho fatto erori(ma sono sicuro che li ho fatti =D) è impossibile determinare il vincitore senza conoscere l'area occupata dal tavolo e dai fiammiferi.

stewaolone ha detto...

mah secondo me vince sempre il secondo, se mette ogni fiammifero esattamente in maniera simmetrica rispetto a ogni fiammifero che mette il primo.. perché alla fine esauriranno tutti i posti disponibili e il primo non saprà più dove metterlo..

stewaolone ha detto...

però se il primo mette il primo fiammifero in modo che il centro esatto del fiammifero si trovi al centro del tavolo, seguendo sempre il meccanismo della simmetria (questa volta lui mette i fiammiferi seguenti in modo simmetrico rispetto al secondo), vince lui (il primo)per lo stesso motivo che ho cercato di spiegare nel commento precedente...

Walter ha detto...

complimenti stewaolone, 2 punti :)

Sixam ha detto...

Ci sono pero' almeno due casi in cui la strategia della simmetria non funziona...
- un tavolo la cui superficie e' esattamente grande quanto un fiammifero (soluzione degenere, ma accettabile);
- un tavolo la cui superficie e' di 3 fiammiferi messi in fila(il primo mette il suo fiammifero in un angolo, il secondo lo mette simmetrico, ed il primo risponde mettendo il suo in mezzo e vincendo).

Bye by SixaM 8-]

Walter ha detto...

Ma la soluzione di stewalone che ho premiato è la seconda che ha proposto, ovvero quella secondo la quale il primo vince sempre, a patto di adottare la strategia ideale. Questa cosa è vera anche nella soluzione degenere (lui mette l'unico fiammifero posizionabile, quindi il secondo perde) che dei tre fiammiferi (lui mette il primo, il secondo giocatore posiziona il secondo fiammifero, lui mette l'ultimo e vince).

Marco ha detto...

Secondo me la soluzione non è del tutto vera.
Se infatti il secondo giocatore fa in modo da rimanere con un piccolo spazio, eventualmente utilizzabile per più fiammiferi affiancati, ma poi mettesse il suo in obliquo, in modo da occupare lo spazio rimasto, il primo perderebbe.
In pratica una cosa del genere:
||||||||||||
||||||||||||
||||| \ ||||
||||||||||||
||||||||||||

Unknown ha detto...

Secondo me vince il primo: accende il fiammifero e lo appoggia sul tavolo facendo in modo che il tavolo bruci completamente.
Il peggior rompicapo del mondo è il seguente: c'è un tubo di materiale perfettamente indeformabile e assolutamente senza buchi e fessure ad eccezione delle due estremità. Da una estremità viene versato un liquido con la pressione di un atmosfera, all'uscita del tubo esce però a 2 atmosfere. Tenere presente che il tubo è perfettamente parallelo al terreno, che non risente di particolari campi magnetici cosa più importante il liquido da quando viene versato a quando esce dal tubo mantiene sempre la stessa temperatura, idem il tubo... La soluzione c'è!

jubiaba ha detto...
Questo commento è stato eliminato dall'autore.
Matteo ha detto...

Il tavolo è tondo quindi la soluzione degenere è solo quella con tavolo di diametro pari ad 1 fiammifero. Impossibile che un cerchio abbia superficie pari a 1 o 3 fiammiferi la cui superficie è invece un rettangolo