Problemi di attraversamento

Giochini matematici elementari ma non olimpici.
Rispondi
Theaetetus
Messaggi: 10
Iscritto il: 24 dic 2008, 12:43
Località: Roma

Problemi di attraversamento

Messaggio da Theaetetus » 02 gen 2009, 13:03

Questo è un indovinello molto antico (risale almeno all'VIII secolo!), quindi non lo snobbate solo perchè sembra uscito dalla settimana enigmistica... :D :D

Un uomo doveva trasportare al di là di un fiume un lupo, una capra ed un cavolo senza che alcuno di questi ne subisse danno. La corrente era troppo rapida ed impetuosa perchè fosse possibile guadarlo a nuoto, e l'unica imbarcazione disponibile permetteva all'uomo di tenere con sè, durante la navigazione, al più uno fra i tre organismi sotto la sua tutela. Poichè solo la presenza dell'uomo sulla medesima riva poteva impedire alla capra di mangiarsi il cavolo (nonostante l'enorme mole di questo) ed al lupo di divorare la capra (ma non criminalizziamolo!), come fece l'uomo a traghettare in salvo tutti e tre?
Se questa frase è vera, allora Babbo Natale esiste.

Pauca sed matura (C.F.Gauss)

Agostino
Messaggi: 211
Iscritto il: 11 dic 2007, 17:43

Messaggio da Agostino » 02 gen 2009, 16:09

andata 1 uomo pecora
ritorno 1 uomo
andata 2 uomo lupo
ritorno 2 uomo pecora
andata 3 uomo cavolo
riotorno 3 uomo
andata 4 uomo pecora
همؤهثمخ سفثممشفخ سخحقش يه ةثز

Theaetetus
Messaggi: 10
Iscritto il: 24 dic 2008, 12:43
Località: Roma

Messaggio da Theaetetus » 02 gen 2009, 18:36

Agostino ha scritto:andata 2 uomo lupo ... andata 3 uomo cavolo
Giustissimo! Questa è una delle due soluzioni che consentono il minor numero di attraversamenti. Altrimenti è possibile invertire l'andata 2 con l'andata 3, impiegando allo stesso modo 7 viaggi.
Eccovi, direttamente dalla corte di Carlo Magno, un altro indovinello medioevale che godette di molta fortuna durante il Rinascimento:

Tre mariti molto gelosi si trovano con le rispettive consorti sulla sponda di un ampio fiume. Vorrebbero attraversarlo, ma vi è una sola imbarcazione che può contenere al massimo due persone. Ciascuno di loro sa remare, ma nessun marito, per motivi di onore, permetterebbe mai alla propria moglie di trovarsi in compagnia di un altro uomo senza che lui stesso sia presente. Come fanno a compiere tutti la traversata evitando che il loro onore ne sia macchiato?
Se questa frase è vera, allora Babbo Natale esiste.

Pauca sed matura (C.F.Gauss)

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 02 gen 2009, 20:16

Vanno 2 mogli sull'altra sponda, ne torna una, vanno le ultime 2, ne torna una.
A sinistra c'è una coppia, quindi rimangono liberi 2 uomini che vanno a destra dalle rispettive mogli. Anche a destra ci sono 2 coppie. (Da qui si può rifare tutto al contrario) Ne torna una. Vanno 2 uomini a destra (tanto la donna a destra è protetta dal suo maritino), torna questa. A sinistra ci sono 3 donne, a destra 3 uomini. Vanno a destra due donne, ne torna una e vanno a destra le ultime 2. Fine
Così i mariti possono stare tranquilli che non avvengano tradimenti :wink:
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

Theaetetus
Messaggi: 10
Iscritto il: 24 dic 2008, 12:43
Località: Roma

Messaggio da Theaetetus » 03 gen 2009, 12:42

Esatto! :) In soli 11 viaggi i sei vengono fuori da una situazione che rischiava di rivelarsi pericolosamente indecorosa… :shock:
Come per salvare capra e cavoli, anche qui esiste più di una strategia vincente: al primo viaggio poteva passare una coppia marito-moglie, al penultimo poteva tornare il legittimo marito della donna sulla prima sponda, oppure si potevano compiere entrambe le scelte. Ora cerchiamo di generalizzare un po':

Mantenendo le regole fissate in precedenza e chiamando n il numero delle coppie marito-moglie, p il numero minimo di posti sull’imbarcazione necessari per portare a termine la traversata e v il numero di viaggi, descrivere i valori di p e v al variare di n.
Se questa frase è vera, allora Babbo Natale esiste.

Pauca sed matura (C.F.Gauss)

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 03 gen 2009, 21:21

Provo al variare di p.
Per p = 2:
  • se n = 1, v = 1
    se n = 2, v = 7
    se n = 3, v = 11
    se n > 3, non ci sono soluzioni
per p = 3:
  • se n = 1,2, v = 1
    se n = 3, v = 7
    se n = 4, v = 9
    se n = 5, v = 11
    se n > 5, non ci sono soluzioni
per p > 3 la faccenda è più complicata...
pongo $ \displaystyle c=\left\lfloor \frac{p}{2}-1\right\rfloor $;
il numero (forse) minimo di viaggi è il minimo fra i risultati di queste espressioni:

$ \displaystyle~\begin{cases} \frac{2n}{c}-1 & \text{se } c|n \lor (p \equiv 1 \pmod{2} \land n \equiv 1 \pmod{c}) \\ 2\left\lfloor\frac{n}{c}\right\rfloor+1 & \text{altrimenti} \end{cases} $
$ \displaystyle~11+2\left\lceil\frac{n-2p+1}{c}\right\rceil $
$ \displaystyle~7+2\left\lceil\frac{n-2p+3}{c}\right\rceil $

(Don't try this at home)

Scriverò la spiegazione quando avrò tempo.
Se non capite cosa vogliono dire cose del tipo $ \lfloor x\rfloor $ o $ \lceil x\rceil $ cliccate qui e qui.
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

Avatar utente
exodd
Messaggi: 728
Iscritto il: 09 mar 2007, 19:46
Località: sulle pendici della provincia più alta d'europa

Messaggio da exodd » 08 gen 2009, 20:23

in altri casi.. si imbavagliano mariti, mogli, pecore e lupi... e se non bastassere anche i cavoli!!!! :D
Tutto è possibile: L'impossibile richiede solo più tempo
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
EvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
ispiratore del BTA

in geometry, angles are angels

"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"

Theaetetus
Messaggi: 10
Iscritto il: 24 dic 2008, 12:43
Località: Roma

Messaggio da Theaetetus » 31 gen 2009, 20:49

kn ha scritto:pongo $ \displaystyle c=\left\lfloor \frac{p}{2}-1\right\rfloor $;
il numero (forse) minimo di viaggi è il minimo fra i risultati di queste espressioni:

$ \displaystyle~\begin{cases} \frac{2n}{c}-1 & \text{se } c|n \lor (p \equiv 1 \pmod{2} \land n \equiv 1 \pmod{c}) \\ 2\left\lfloor\frac{n}{c}\right\rfloor+1 & \text{altrimenti} \end{cases} $
$ \displaystyle~11+2\left\lceil\frac{n-2p+1}{c}\right\rceil $
$ \displaystyle~7+2\left\lceil\frac{n-2p+3}{c}\right\rceil $
Bè... ma anche no! Il resto è decisamente corretto (a parte n=2, p=2), ma la soluzione per n>5 è molto diversa (e molto più semplice). Colgo in effetti solo oggi :idea: un possibile fraintendimento del testo: la richiesta è di trovare, date le n coppie, il minimo numero di posti p affinchè possano tutte attraversare il fiume; e di determinare poi, in tale situazione, quale sia il minor numero di viaggi v che si riesce a impiegare. Era questo il problema?
Se questa frase è vera, allora Babbo Natale esiste.

Pauca sed matura (C.F.Gauss)

Rispondi