CONSIDERAZIONI E RIFLESSIONI

Il problema dei tre mariti gelosi

Vi sono tre coppie (marito e moglie) che arrivano sulla riva di un fiume e debbono attraversarlo, ma hanno a disposizione una barca che può trasportare al massimo due persone. Il problema sorge per il fatto che i mariti sono tutti estremamente gelosi e nessuno di essi permette alla propria moglie di restare in una compagnia nella quale siano presenti altri uomini e sia assente il marito.

Come anticipato, la strategia è la stessa della capra dei cavoli.

E’ necessario:

• fare un elenco delle configurazioni possibili ed eliminare quelle non permesse;
• congiungere tra loro le configurazioni per le quali è possibile il passaggio dall’una all’altra;
• vedere infine se esiste un cammino che congiunga la configurazione di partenza con quella desiderata di arrivo.

Intanto si può osservare che il problema si presta ad una immediata generalizzazione: invece di considerare tre coppie, si possono considerare n coppie (con n intero positivo) sempre legate dal vincolo della gelosia.

Qualche abbreviazione

Indichiamo rispettivamente con:

il componente di sesso maschile della n-esima coppia

il componente di sesso femminile della n-esima coppia

ed incominciamo ad affrontare nell’ordine i casi fino a tre coppie.

Osserviamo ancora che, usando la stessa procedura del problema della capra e dei cavoli, gli elementi dell’insieme di partenza sono e quindi il numero di stati possibili (non necessariamente tutti accettabili) è e cresce piuttosto rapidamente con n (già per si hanno 256 combinazioni).

Nota. Vi è, in questo problema dei mariti gelosi, una differenza rispetto a quello della capra e dei cavoli, nel senso che, in quel caso non ci si doveva preoccupare della barca, in quanto vi era solo il pastore in grado di governarla e quindi la barca era sulla riva dove si trovava il pastore; in questo caso sarà invece necessario tenere in qualche maniera conto della riva su cui si trova la barca.

Una coppia

Sponda di partenza: Sponda di arrivo:

Tutte le configurazioni sono accettabili (con una coppia il problema della gelosia non si dovrebbe porre).

Congiungiamo tra loro gli stati per i quali è possibile un passaggio:

Il grafo corrispondente è:

Nei vertici del grafo è stato aggiunto il simbolo B che indica la presenza della barca. Se la B è all’inizio ciò significa che la barca si trova sulla sponda di partenza mentre se è alla fine si trova sulla sponda di arrivo.

Come si vede il problema si risolve in una mossa, a meno che la coppia non decida di fare dei viaggi a vuoto, trasportando una sola persona (sono i casi che corrispondono alle due biforcazioni laterali)

Due coppie

In questo caso si hanno combinazioni

Sponda di partenza: Sponda di arrivo:

Le combinazioni indicate con * sono quelle vietate.

Lo schema presenta una certa similitudine con quello della capra e dei cavoli, nel senso che anche in quel caso erano rimaste 10 situazioni possibili. Qui però, grazie alla maggiore operatività dei soggetti (tutti possono traghettare), le connessioni tra i vari stati sono un po’ più confuse.

Infatti risulta:

Sponda di partenza: Sponda di arrivo:

Vorrei invitare il lettore a soffermarsi, al di là dell’intreccio delle linee, sull’alto grado di simmetria del grafico, simmetria che deriva da almeno due considerazioni:

• in questo caso, come in altri simili, il problema è reversibile, nel senso che, una volta individuata la soluzione e raggiunta la riva opposta, il ritorno alle condizioni di partenza è un problema identico a quello iniziale, semplicemente i ruoli delle rive di partenza e di arrivo si sono scambiati.
• Il problema rimane identico per una qualsiasi permutazione degli indici delle coppie nel senso che tutte le coppie marito-moglie sono equivalenti e non ha importanza da quale si parte per risolvere il problema.

Come nel caso del numero scorso, lo schema può essere messo sotto forma di un grafo meno confuso di quanto appare nello schema testé elaborato, grafo che mette anche maggiormente in risalto la simmetria del problema.

Tre coppie / Quattro coppie

Quando ho iniziato a scrivere questo articolo era mia intenzione trattare nel dettaglio il caso di tre coppie e quattro coppie.

Mi sono però reso conto che la trattazione sarebbe stata piuttosto onerosa in termini di spazio e di leggibilità, e, quel che è peggio, anche estremamente noiosa.

Mi limiterò quindi a descrivere le conclusioni.

Se ci fossero, comunque, dei lettori interessati, posso fornire loro le fotocopie dei miei appunti.

Nel caso di tre coppie si hanno combinazioni, che, dopo l’esclusione delle situazioni non permesse, si riducono a 22. Una volta tracciata la tabella con i collegamenti tra i vari stati, si vede che il problema è risolubile, ma è abbastanza difficile tracciare un grafo decente dal punto di vista della leggibilità.

Penso che una soluzione, per chi è dotato di un minimo di manualità, potrebbe essere una realizzazione tridimensionale del grafo dal quale si evidenzierebbe la simmetria del medesimo in quanto, grazie all’equivalenza delle tre coppie, è presente una simmetria di rotazione tipo quella di un triangolo equilatero attorno ad un asse perpendicolare al piano del triangolo e passante per il suo baricentro.

Nella trattazione di questo caso si presenta però, per la prima volta, una situazione abbastanza singolare: vi sono delle situazioni che, pur essendo compatibili con i vincoli del problema, sono “isolate” nel senso che non vi è nessuna serie si passaggi che, partendo dalla configurazione iniziale, possa portare ad esse.

Nel caso di quattro coppie si hanno casi che si riducono, dopo l’eliminazione di quelli inaccettabili a 46.

Una volta tracciato il grafo dei passaggi si vede che quest’ultimo è non connesso, cioè è costituito di due parti che non sono tra loro collegate da alcun ramo. Poiché lo stato iniziale è in un blocco e quello finale nell’altro, il problema risulta non risolubile.

Spunti e commenti

Una prima osservazione è che, contrariamente ad altri problemi, questo non mi pare un problema ricorsivo, nel senso che anche se si sa risolvere il problema per n coppie, questo non aiuta a risolverlo per .

Dopo aver visto che il problema non è risolubile per 4 coppie ero stato tentato di rispondere che non lo era neppure per un numero maggiore di 4, ma direi che a causa della mancanza di ricorsività, non è detto che ciò sia vero. C’è qualche lettore che se la sente di analizzare i casi di 5 coppie?

C’è qualcuno che se la sente di impostare un programma parametrico per n coppie che enumeri tutti casi, elimini quelli inaccettabili e quindi tracci il grafo? Credo che, anche se non si riesce a risolvere il problema, sia comunque un’esperienza matematicamente interessante. G.B.