Problemi di attraversamento

[Theaetetus]

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

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?

[Agostino]

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]

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?

[kn]

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

[Theaetetus]

Esatto! In soli 11 viaggi i sei vengono fuori da una situazione che rischiava di rivelarsi pericolosamente indecorosa…
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.

[kn]

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.

[exodd]

in altri casi.. si imbavagliano mariti, mogli, pecore e lupi... e se non bastassere anche i cavoli!!!!

[Theaetetus]

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 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?