Un 'classico' col malocchio

[orsoulx]

Un problema di attraversamento, la cui origine si perde nella notte dei tempi, l'ho incontrato quando frequentavo le scuole superiori e credo di conoscerne la soluzione ottimale. Molti divulgatori di giochi logico-matematici hanno trattato il problema correggendo gli errori di altri proponenti.
Alla fine dello scorso anno l'ha riproposto "Diophante.fr", un sito francese di quesiti matematici, e, con sorpresa, fra le soluzioni, solitamente curate e spesso oltre alla mia portata, non ho trovato quella corretta della seconda parte.
http://www.diophante.fr/problemes-par-t ... electables

Un sunto in italiano:
Alcune coppie, con mogli belle e mariti gelosissimi, devono attraversare un fiume usando una barca che può portare solo una o due persone per volta. Nessuna moglie può stare in compagnia di un uomo se non è presente anche il marito. In mezzo al fiume si trova un'isola dove è possibile isolare una o più persone. Con un massimo di $ 32 $ traversate (per traversata si intende un qualsiasi percorso sponda-sponda, sponda-isola o isola-sponda) quante coppie potranno attraversare il fiume?
NB Tutti sanno utilizzare la barca, anche se in realtà ne basterebbero meno.

Ciao

[axpgn]

Sono arrivato a sette coppie

Dalla riva sx all'isola:
$d_1+d_2 >$
$< d_1$
$d_1+d_3 >$
$< d_3$

Dalla riva sx alla riva dx:
$u_1+u_2 >$
$< u_1$
$u_3+d_3 >$
$< u_2$

Questi quattro passaggi vengono ripetuti per portare sull'altra sponda le coppie $4, 5, 6, 7$

Poi, dalla riva sx alla dx $u_1+u_2 >$

Ed infine, dall'isola alla riva dx:
$< d_3$
$d_1+d_3 >$
$< d_1$
$d_1+d_2 >$

Per un totale di $29$ passaggi

Un'altra coppia porterebbe a $33$ passaggi …

Questo è il mio meglio

Cordialmente, Alex

[orsoulx]

@Alex

Perfetto! In generale se le coppie sono $ n $ bastano $ 4n+1 $ traversate e si può dimostrare che, per $ n>3 $, non si può far di meglio. In assenza di vincoli maschilisti occorrono comunque $ 4n-3 $ traversate e, a causa del vincolo, bisogna isolare (con $ n>3 $) almeno due signore, come hai farro..
Resta da spiegare, perché i divulgatori si fossilizzino, a parte il caso di una sola coppia, su $ 6n-7 $, che fornisce l'ottimo solo per $ n=2,3,4 $. Penso derivi da un mix fra una certa difficoltà insita nei casi iniziali (con $ n=3 $ il miglior attraversamento è più complicato di quello che proponi), e una buona dose di ipse dixit.
Non sono bravo come Riccardo, ma cercando in rete ho trovato un solo autore che dichiara di aver trovato, con l'aiuto del computer, la dipendenza da $ 4n $.

Ciao

[axpgn]

@orsoulx

"orsoulx":Resta da spiegare, perché i divulgatori si fossilizzino, a parte il caso di una sola coppia, su $ 6n-7 $, che fornisce l'ottimo solo per $ n=2,3,4 $. Penso derivi da un mix fra una certa difficoltà insita nei casi iniziali (con $ n=3 $ il miglior attraversamento è più complicato di quello che proponi), e una buona dose di ipse dixit.

Boh … ne ho lette talmente tante, negli anni, di versioni, da ricordarmi solo quella della capra, del cavolo e del lupo[nota]A proposito, l'avevo già postata la soluzione che fa uso dei cammini su un cubo?[/nota] , le altre devo "rifarle" ogni volta.
E questo sicuramente rende difficile o meglio, pesante e lungo, render conto di tutto (o di tanto).
Inoltre penso che molto dipenda anche dal "livello" della divulgazione cioè anche dal pubblico a cui ci si rivolge.

Con "dipendenza da $4n$" si intende meno di $4n+1$?

Cordialmente, Alex

P.S.: Who is Riccardo?

[orsoulx]

@Alex

con dipendenza da $ 4n $ intendevo quella che hai trovato ( dimostrata non migliorabile per $ n>3 $), contrapposta alla dipendenza da $ 6n $ (ottima per $n=2,3$).
Riccardo era per me "Veciorik", ma forse non si chiama così.

Non ricordo soluzioni che utilizzano i cammini su un cubo.
Ciao

[axpgn]

Grazie

Cordialmente, Alex

P.S.: per quanto riguarda il cubo …

È una soluzione del professor Ian Stewart, che riporto in originale

I like to solve this geometrically, using a picture in wolf–goat–cabbage space.
This consists of triples (w, g, c) where each symbol is either 0 (on this side of the river) or 1 (on the far side).
So, for instance, (1, 0, 1) means that the wolf and cabbage are on the far side but the goat is on this side.
The problem is to get from (0, 0, 0) to (1, 1, 1) without anything being eaten.
We don’t need to say where the farmer is, since he always travels in the boat during river crossings.
There are eight possible triples, and they can be thought of as the vertices of a cube.
Because only one item can accompany the farmer on each trip, the permissible moves are the edges of the cube.
However, four edges (shown in grey) are not permitted, because things get eaten.
The remaining edges (black) do not cause mayhem.
So the puzzle reduces to a geometric one: find a route along the black edges, from (0, 0, 0) to (1, 1, 1). The two solutions are immediately evident.

[orsoulx]

@Alex
Molto carino il cubo. Grazie.
Ciao

[Mary Anne]

io questo indovinello lo sapevo avendo come soggetti pecole, broccoli e lupi! ma la soluzione è sempre la stessa. non tramonterà mai