Scimmie e banane

[SkZ]

Le scale sono in fila (non mi sembra che poi importi veramente).

le scale sono collegate solo alle scale affianco? Se fossero in tondo una scala potrebbe essere tranquillamente collegata a qualunque altra, perche' la corda non "intersecherebbe" altre scale.

[SkZ]

Per semplicita' di trattazione si potrebbe eliminare tutti i pioli non collegati da/a una corda. In tal modo una scimmia ha due soli movimenti:
a) passare al piolo successivo della scala
b) percorrere una corda
e i due movimenti devono alternarsi
Chiamo step la parte di scala tra due pioli.

Per dimostare che le scimmie arrivano sempre ad una banana, basta dimostrare che uno step e' percorso da una e una sola scimmia.
Se uno step e' percorso da due o piu' scimmie diverse, esse avranno la stessa banana.

Se per uno step passa una una sola scimmia, allora una corda e' percorsa da due sole scimmie. Eliminando quella corda quelle due scimmie si "scambiano" le banane.

[SkZ]

proposizione:"Un percorso puo' essere percorso in modo inverso e riconduce alla base della scala da cui la scimmia era partita."
Se cio' e' vero allora:
1) Ad una banana arriva una sola scimmia
2) Non sono possibili cicli perpetui
3) ad ogni banana arriva una sola scimmia

[il percorso e' una funzione bigettiva tra le basi delle scale e le banane] se e solo se [ogni step e' percorso da una sola scimmia]

[SkZ]

Riassumo (piu' per me, che per gli altri ). Le regole sono che:
a) ho delle scale collegate tra loro da corde con in cima una banana
b) ad ogni piolo e' collegata una e una sola corda
c) una scimmia sale la scala
d) una scimmia appena trova una corda la percorre

Se ho $ ~n $ scale e $ ~m $ corde, allora avro' $ ~2m $ pioli e $ ~2m+n $ step

L'aggiunta di una corda (e quindi di due pioli) comporta che due step vengono sdoppiati.
Con l'aggiunta di una corda lo step $ ~s_{ik} $ (i-esima scala, k-esimo step della scala) diventa $ ~s_{ik}^u $ e $ ~s_{ik}^b $.
Dati due step $ ~s_{ik} $ e $ ~s_{jl} $, li colleghiamo con una corda. Avremo quindi ora $ ~s_{ik}^u $, $ ~s_{ik}^b $, $ ~s_{jl}^u $ e $ ~s_{jl}^b $. Se originariamente la scimmia $ ~\sigma $ percorreva lo step $ ~s_{ik} $, ora percorerra' prima $ ~s_{ik}^b $ e poi $ ~s_{jl}^u $, mentre la scimmia $ ~\tau $ che percorreva lo step $ ~s_{jl} $, ora percorrera' gli step $ ~s_{jl}^b $ e poi $ ~s_{ik}^u $. Quindi aggiungendo una corda creo uno scambio di percorso tra le due scimmie che percorrevano in origine i due step collegati.
Quindi l'aggiunta di una corda non permette che due scimmie possano percorrere uno stesso step.
La presenza di step percorsi da piu' di una scimmia e' invariante per l'aggiunta di corde.
Il numero di step percorsi da piu' di una scimmia aumenta parimenti al numero di step coinvolti che erano gia' percorsi da piu' di una scimmia.

Senza corde ogni scimmia percorre una scala:
a) ogni banana e' raggiunta da una sola scimmia
b) ogni step e' percorso da una sola scimmia.
quindi aggiungendo corde il numero di step percorsi da piu' di una scimmia non puo' aumentare, dato che originariamente il numero iniziale e' 0 e quindi aggiungendo corde il loro numero puo' aumentare solo di 0.

[MindFlyer]

la matematizzazione sono i 3 puntini. Volendo, lo si può scrivere esplicitamente.

Ecco, l'ho aggiunto.

[SkZ]

va bene quello che ho scritto?

[Nonno Bassotto]

Il messaggio lungo non l'ho capito molto, ma questa

proposizione:"Un percorso puo' essere percorso in modo inverso e riconduce alla base della scala da cui la scimmia era partita."
Se cio' e' vero allora:
1) Ad una banana arriva una sola scimmia
2) Non sono possibili cicli perpetui
3) ad ogni banana arriva una sola scimmia

[il percorso e' una funzione bigettiva tra le basi delle scale e le banane] se e solo se [ogni step e' percorso da una sola scimmia]

si può considerare una soluzione (molto sintetica). Cerco di scriverla più per esteso.

L'osservazione fondamentale è che i percorsi sono reversibili. Questo significa che se in un qualsiasi punto di una scala una scimmia decide di fermarsi e seguire le regole inverse (cioè ogni volta che incontra una corda la segue, ma scende le scale anziché salirle) allora torna indietro sui propri passi. Questo può essere verificato osservando che è vero ad ogni bivio.

Inoltre così come le regole iniziali determinano univocamente il moto in avanti delle scimmie, anche le regole simmetriche determinano univocamente il moto.

Da questo segue che i percorsi di due scimmie non si possono congiungere: se così fosse, invertendo il moto si troverebbe un bivio (dove i percorsi delle due scimmie si sono incontrati), contro il fatto che il moto all'indietro è unicamente determinato.

Perciò se tutte le scimmie arrivano in cima, arrivano tutte a banane diverse. Rimane da vedere che ogni scimmia arriva in cima: poiché lo spazio totale da percorrere è finito, basta vedere che non ci sono scimmie che vanno in loop.

Per questo l'argomento è del tutto analogo. Se una scimmia va in loop, vuol dire che ad un certo punto incontra un pezzo di percorso che ha già seguito. Tornando indietro si ottiene un bivio, assurdo.

Piccola osservazione: i loop esistono, basta considerare due scale adiacenti collegate da due corde che si incrociano. Una scimmia che parta a metà tra le due corde andrà in loop. Il fatto è che le scimmie non ci possono entrare, se partono dal basso.

Appena ho tempo posto anche l'altra soluzione (se intanto volete pensarci...)

[SkZ]

Il messaggio lungo non l'ho capito molto

Chissa' perche' non mi meraviglio.

Dopo alcune delucubrazioni su cosa succede se aggiungo una corda al numero di step in generale, a quello dei step percorsi da piu' di una scimmia e ai percorsi, ho notato che all'aggiunta di una corda il numero di step percorsi da piu' di 1 scimmia aumenta di un numero pari al numero di questi coinvolti nell'aggiunta:
se collego uno step "normale" ad uno "multi-percorso", i "multi-percorsi" aumentano di 1;
se collego 2 "multi-percorsi", aumentano di 2;
se collego due step "normali", i "multi-perorsi" non aumentano di numero.
Quindi aggiungendo una corda non posso crearli, solo aumentare il loro numero se gia' ci sono (la presenza di step "multi-percorsi" e' un invariante rispetto all'aggiunta di corde).
Dopo noto che nella configurazione iniziale (nessuna corda) non ci sono "multi-percorsi", quindi non potro' mai avere step percorsi da piu' di 1 scimmia.

Sono riuscito a spiegarmi, o il discorso e' ancora confuso?

[teppic]

Forse non tutti sanno che...

In Giappone (soprattutto tra i bambini) è molto diffuso un metodo per tirare a sorte n premi (o incarichi, o qualunque altra cosa) tra n persone. Su un foglio si disegnano n linee verticali equispaziate. In basso sotto ogni riga si scrive il nome di una delle persone. In alto sopra ogni riga si scrive un premio (associandoli in un modo qualunque). Poi rapidamente e senza pensare si disegnano a caso un po' di linee orizzontali tra le coppie di segmenti adiacenti (è bene che tra ogni coppia di segmenti ce ne siano da 2 a 5 ad altezze diverse). Infine si fanno "partire le scimmie", ovvero si parte da ogni nome andando verso l'alto fino a che non si incontra una linea orizzontale; arrivati a questa la si segue fino alla prossima linea verticale, e si ricomincia a salire; si procede in questo modo fino ad arrivare al premio, che viene assegnato alla persona da cui si era partiti.

(Visto in numerosi cartoni giapponesi... e poi dicono che sono diseducativi! )

[MindFlyer]

Dimenticate che, mettendo infinite corde, è possibile far salire le scimmie all'infinito senza che raggiungano mai la cima. (hmm, forse nel testo andava detto che le corde sono finite?)

[peppux]

a me sembra che possano verificarsi tutte la opzioni possibili, overro:

-le scimmie continuino a girare all'infinito
-ogni scimmia arriva a una banana
-e poi che alcune arrivino a prendere un banana e altre no

[MindFlyer]

Benvenuto, peppux!
Secondo me hai capito male il testo, perché se le corde sono finite, la dimostrazione di Nonno Bassotto funziona (è scritta in bianco, per leggerla devi evidenziare il testo col mouse).

[Nonno Bassotto]

Dimenticate che, mettendo infinite corde, è possibile far salire le scimmie all'infinito senza che raggiungano mai la cima. (hmm, forse nel testo andava detto che le corde sono finite?)

Ok, mi sono dimenticato. Le corde sono finite.

[Nonno Bassotto]

Sono riuscito a spiegarmi, o il discorso e' ancora confuso?

Mi sembra che funzioni, ma questo dice solo che non ci sono due scimmie i cui percorsi si congiungono; bisognerebbe vedere anche che non ci sono scimmi che vanno in loop. Comunque, come ti ho detto lo sketch funzionava.
Ciao

[SkZ]

Dato che per creare un loop (all'inizio non ve ne sono, quindi vanno creati) devo collegare due step percorsi dalla stessa scimmia, chiamo $ ~s^1_{ij} $ e $ ~s^2_{kl} $ i due step ove i numeri indicano l'ordine di persorrenza (1 e' percorso prima di 2). Congiungendo questi due step ottengo solo che il percorso della scimmia viene accorciato, ovvero la scimmia si scambia la banana con il suo futuro, ma allora arriva alla stessa banana. Avendo cambiato percorso il futuro cessa di esistere e mi si crea quindi un loop fantasma, fantasma perche' non e' raggiungibile.
Quindi i loop si possono formare ma esistono solo come percorsi preclusi alle scimmie.
collegando uno step permesso ad uno appartenente ad un loop, si ottiene solo di spezzare il loop nel punto di collegamento e aggiungerlo al percorso della scimmia.