Indice del forum Olimpo Informatico
I Forum di Zeus News
Leggi la newsletter gratuita - Attiva il Menu compatto
 
 FAQFAQ   CercaCerca   Lista utentiLista utenti   GruppiGruppi   RegistratiRegistrati 
 ProfiloProfilo   Messaggi privatiMessaggi privati   Log inLog in 

    Newsletter RSS Facebook Twitter Contatti Ricerca
* QUIZ: Le TRE taniche (forse anche di più)
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici
Precedente :: Successivo  
Autore Messaggio
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 06 Gen 2007 21:09    Oggetto: * QUIZ: Le TRE taniche (forse anche di più) Rispondi citando

Il problema delle due taniche era stato proposto qui.

Ora passiamo a qualcosa di più complicato.

Ho trovato su Puzzles and paradoxes di T. H. O'Beirne (Oxford University Press - 1965) un intero capitolo dedicato a taniche, bottiglie e bidoni.

Ecco il primo quesito che ho scelto:

Usando tre taniche da 3, 5 e 8 galloni suddividere 8 galloni in due parti uguali.


L'ultima modifica di ulisse il 23 Feb 2007 16:15, modificato 1 volta
Top
Profilo Invia messaggio privato HomePage
MK66
Moderatore Sistemi Operativi
Moderatore Sistemi Operativi


Registrato: 17/10/06 22:24
Messaggi: 8448
Residenza: dentro una cassa sotto 3 metri di terra...

MessaggioInviato: 07 Gen 2007 12:13    Oggetto: Rispondi citando

Premetto che potranno esserci metodi migliori, ma questo è il primo che mi è venuto in mente, immedesimandomi mentalmente in una situazione del genere...Shocked Confuso
Citazione:

Indicando le 3 taniche come A (3 galloni), B (5 galloni) e C (8 galloni), un procedimento potrebbe essere questo:
- la situazione iniziale è: A=0 B=0 C=8
- si travasano 3 galloni da C in A (la situazione diventa A=3 B=0 C=5)
- si travasano i 3 galloni da A a B (A=0 B=3 C=5)
- si travasano altri 3 galloni da C in A (A=3 B=3 C=2)
- si riempie B con parte del contenuto di A (A=1 B=5 C=2)
- si svuota il contenuto di B in C (A=1 B=0 C=7)
- si travasa il contenuto da A in B (A=0 B=1 C=7)
- si riempie A con parte del contenuto di C (A=3 B=1 C=4)
- si travasa il contenuto di A in B (A=0 B=4 C=4) ed il gioco è fatto.

Top
Profilo Invia messaggio privato HomePage
Benny
Moderatore Hardware e Networking
Moderatore Hardware e Networking


Registrato: 28/01/06 14:35
Messaggi: 6382
Residenza: Non troppo vicino, mai troppo lontano

MessaggioInviato: 07 Gen 2007 13:44    Oggetto: Rispondi citando

Un casino... meglio segnare passaggio per passaggio:
Citazione:
Situazione iniziale:
Tanica da 8: 8 galloni
Tanica da 5: vuota
Tanica da 3: vuota

riempio la tanica da 3 galloni versando acqua da quella da 8 galloni
T8: 5 gall
T5: vuota
T3: 3 gall

verso il contenuto di T3 in T5
T8: 5 gall
T5: 3 gall
T3: vuota

verso altri 3 galloni da T8 in T3
T8: 2 gall
T5: 3 gall
T3: 3 gall

riempio T5 versando da T3
T8: 2 gall
T5: 5 gall
T3: 1 gall

vuoto T5 in T8
T8: 7 gall
T5: vuota
T3: 1 gall

vuoto T3 in T5
T8: 7 gall
T5: 1 gall
T3: vuota

riempio T3 attingendo da T8
T8: 4 gall
T5: 1 gall
T3: 3 gall

infine vuoto T3 in T5
T8: 4 gall
T5: 4 gall
T3: vuota

in tutto 2^3=8 passaggi
(che l'esponente sia casuale?)


Come dice MK66, magari c'è una soluzione più semplice, ma con meno passaggi non mi viene...
Top
Profilo Invia messaggio privato
_L_
Semidio
Semidio


Registrato: 27/12/06 23:47
Messaggi: 215
Residenza: Brugherio (MI)

MessaggioInviato: 07 Gen 2007 13:50    Oggetto: Rispondi citando

Citazione:
a=tanica da 3, b=tanica da 5, c=tanica da 8
a b c
0 0 8 stato iniziale
0 5 3 (c --> b)
3 2 3 (b --> a)
0 2 6 (a --> c)
2 0 6 (b --> a)
2 5 1 (c --> b)
3 4 1 (b --> a)
0 4 4 (a --> c)
in 7 passaggi
Top
Profilo Invia messaggio privato HomePage MSN
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 07 Gen 2007 17:45    Oggetto: W _L_! Rispondi citando

...pensavo anch'io che 8 fosse il minimo, ora credo che non si possa fare meglio di quanto ci ha "nascosto" _L_!

Ma, ora, nasce spontanea una domanda: posto che le configurazioni possibili sono

Citazione:
24 (credo e spero) e cioè, nell'ordine tanica da 3, tanica da 5, tanica da 8,

008 017 026 035 044 053
107 116 125 134 143 152
206 215 224 233 242 251
305 314 323 332 341 350


è possibile partendo da quella neutra (008) raggiungere una qualsiasi delle altre? E se non è possibile, perche?

Salmastro
Top
Profilo Invia messaggio privato AIM Yahoo MSN
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 09 Gen 2007 14:45    Oggetto: Rispondi citando

Bravo MK66 che ha trovato una soluzione in 8 mosse e bravo _L_ che ne ha trovata una in 7 !

Resta da capire se è l'unica soluzione in 7 mosse e se, soprattutto, è la migliore.

Mi piace la domanda di Salmastro che muove così il primo passo verso la modellizzazione del problema!
Avendo il libro sotto al naso non posso intervenire quindi resto in attesa di risposte e considerazioni.

Permettetemi un piccolo aiuto (la strada verso il modello è lunga, seppur non complicata).

A meno di non travasare a casaccio del liquido da una tanica all'altra (cosa totalmente inutile ai nostri scopi) avremo sempre a che fare con quantità intere di liquido.

Secondo questa premessa che per rigore esplicito, avete già scelto di rappresentare lo stato del sistema facendo uso di una terna di numeri interi.

Proviamo ad usare un po' di geometria analitica. Poiché abbiamo 3 taniche dovremo introdurre una terna XYZ di assi cartesiani ortogonali.
I possibili stati del nostro sistema saranno rappresentati da punti (a coordinate intere) nello spazio cartesiano.

Dove se ne sta questo insieme di punti? sono sparsi a casaccio o se ne stanno in un luogo geometrico ben preciso?
Per rispondere a questa domanda ricordate che la quantità di liquido presente complessivamente nelle tre taniche è costante...
Top
Profilo Invia messaggio privato HomePage
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 09 Gen 2007 16:25    Oggetto: Rispondi citando

Vi confermo che la soluzione in sette mosse e` unica ed e` anche la migliore.
Ciao.
Marco.
P.S. Ho usato la forza bruta e un programmino Python di una trentina di righe... Smile
Top
Profilo Invia messaggio privato
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 09 Gen 2007 16:56    Oggetto: Re: W _L_! Rispondi citando

Ecco la risposta per salmastro.
Anche se non so il perche`...
Di fianco a ogni posizione il numero minimo di mosse.

Citazione:
Posizione: 008 = 0
Posizione: 017 = 6
Posizione: 026 = 3
Posizione: 035 = 2
Posizione: 044 = 7
Posizione: 053 = 1
Posizione: 107 = 5
Posizione: 116 = irraggiungibile
Posizione: 125 = irraggiungibile
Posizione: 134 = irraggiungibile
Posizione: 143 = irraggiungibile
Posizione: 152 = 4
Posizione: 206 = 4
Posizione: 215 = irraggiungibile
Posizione: 224 = irraggiungibile
Posizione: 233 = irraggiungibile
Posizione: 242 = irraggiungibile
Posizione: 251 = 5
Posizione: 305 = 1
Posizione: 314 = 7
Posizione: 323 = 2
Posizione: 332 = 3
Posizione: 341 = 6
Posizione: 350 = 2


Ciao.
Marco.
Top
Profilo Invia messaggio privato
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 09 Gen 2007 17:15    Oggetto: il luogo dei punti Rispondi citando

dalle dritte di Ulisse e dal quel che mi ricordo di geometria analitica nello spazio (che odiavo: non riesco a pensare in tre dimensioni!), mi pare che
Citazione:
i punti appartengano al piano x+y+z=8, cioè quello perpendicolare al versore(?) (1; 1; 1)
poi posso fare un passetto avanti e cioè
Citazione:
per x fissato (per noi: 0,1,2 e 3) le possibili coppie (y;z), in numero di 6 per ogni x, appartengono ad una retta e, per essere più precisi ad un segmento
concludendo tutti i punti (ma sono veramente 24?) appartengono ad un
Citazione:
parallelogramma nello spazio con vertici in: (0;0;8 ), (0;5;3), (3;0;5) e (3;5;0), con gli altri simmetricamenti disposti, lungo il perimetro ed all'interno

se li collego, ho una specie di rete, ma allo stato attuale non so trovare una legge che mi possa far saltellare su TUTTI questi punti...

Salmastro

P.S.: leggendo Taifu mi accorgo che del "mio" parallelogramma possono essere raggiunti tutti e solo i 16 punti lungo il perimetro. Quelli all'interno NO! Quale oscura ragione spiega tutto ciò??
Top
Profilo Invia messaggio privato AIM Yahoo MSN
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 09 Gen 2007 23:32    Oggetto: Rispondi

Perfetto!
(solo una pignoleria che mi vergogno di puntualizzare: i versori sono i vettori di lunghezza unitaria uscenti dall'origine e diretti come gli assi coordinati; quindi (1;1;1) è giusto chiamarlo vettore)

Ecco i grafici di quanto hai scritto con qualche osservazione.

Innanzi tutto il piano passante per (8,0,0), per (0,8,0) e per (0,0,8 ).
Poiché le misure delle taniche sono positive ho limitato la figura al "quadrante" a coordinate positive. Il piano si riduce, dunque a un triangolo.



Al variare del liquido complessivamente contenuto nelle taniche, l'unica cosa che cambia è la distanza del piano dall'origine e, conseguentemente, la dimensione del triangolo.

Osservando il triangolo da un'altra angolazione ovvero da un punto sul prolungamento del vettore (1;1;1) possiamo notare che il triangolo è equilatero, che la trama del reticolo è costituita da tre fasci di rette ognuno parallelo a un lato del triangolo e che, assecondando l'orientamento degli assi, ogni tanica si riempie andando verso il corrispondente vertice del triangolo e si svuota andando verso il lato opposto.
I punti su una parallela corrispondono a tutte le configurazioni che possiamo ottenere mantenendo costante il contenuto di una tanica e distribuendo il liquido residuo in tutti i modi possibili tra le altre due taniche.



Poiché tutti i punti che rappresentano potenziali stati del sistema giacciono sul triangolo, possiamo dimenticarci dello spazio tridimensionale e considerare soltanto il triangolo equilatero col relativo reticolo ottenuto unendo tutti i punti prima trovati.

Ovviamente una tanica da 3 galloni non potrà contenerne 4 quindi dovremo escludere dal reticolo tutti i punti corrispondenti a configurazioni impossibili.
Il reticolo delle configurazioni possibili sarà costituito da un poligono incluso nel triangolo la cui forma dipenderà dalle condizioni iniziali (volume di ognuna delle tre taniche e liquido complessivamente disponibile).

Nel nostro caso il reticolo è esattamente quello descritto da Salmastro:


Ho evidenziato con un quadratino rosso la configurazione di partenza, con un quadratino blu quella di arrivo e con i pallini rossi le altre configurazioni possibili.

Un cambio di stato (una "mossa") può essere rappresentato con una freccia che unisce i due stati iniziale e finale.
Poiché l'unica cosa che possiamo fare è travasare liquido da una tanica ad un'altra, due punti potranno essere collegati da una freccia solo se essi coincidono per una coordinata ovvero se giacciono sulla medesima parallela.

Evidentemente tutti gli stati possono essere stati iniziali ma non tutti gli stati possono essere stati finali.

Ora dovrebbe essere facile rispondere alla domanda di Salmastro: "quali sono i punti che non possono mai essere raggiunti da una freccia e perché?"
Come ha notato Salmastro i punti raggiungibili sono solo quelli perimetrali.
Questo perché i punti perimetrali sono tutti quelli corrispondenti a taniche piene o taniche vuote (infatti quando iniziamo a travasare del liquido da una tanica ad un'altra siamo costretti a proseguire sino a che o la prima tanica si svuota o la seconda si riempie).

Quindi le uniche frecce che potremo disegnare sul reticolo saranno quelle che terminano sul perimetro.
Anzi, poiché dopo la prima mossa piombiamo inesorabilmente sul perimetro, possiamo tranquillamente affermare che le uniche frecce che è lecito disegnare sono quelle che collegano due punti perimetrali sulla stessa parallela.

Ecco un'esempio di mosse che soddisfano tale condizione.



E' tutto qui e le sequenze di mosse vanno costruite per tentativi o ci sono ulteriori regole che ci garantiscono di determinare con certezza se il problema ammette o no soluzione e, nel caso esista, di costruirla?
Top
Profilo Invia messaggio privato HomePage
Mostra prima i messaggi di:   
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici Tutti i fusi orari sono GMT + 1 ora
Vai a 1, 2, 3, 4, 5  Successivo
Pagina 1 di 5

 
Vai a:  
Non puoi inserire nuovi argomenti
Non puoi rispondere a nessun argomento
Non puoi modificare i tuoi messaggi
Non puoi cancellare i tuoi messaggi
Non puoi votare nei sondaggi