Traversée de la rivière

[Kekia]

Bonjour à tous, encore un problème que j'avais posé ailleurs mais dont personne n'avait donné la réponse pour le 2nd cas. Il s'agit d'un vieux problème de Claude-Gaspard Bachet de Méziriac (1581-1638) revisité dans "Amusements in mathematics"

Il y a n>1 couples qui doivent traverser une rivière avec une barque. A cette époque, aucune femme ne peut rester en compagnie d'un homme si son mari n'est pas présent, que ce soit sur terre ou dans une barque. Tout de même, les femmes comme les hommes peuvent ramer.

1er cas : Ils disposent d'une barque de 4 places
2nd cas : Ils disposent d'une barque de 2 places et d'une ile entre les 2 rives.

Quel est le nombre de traversée minimum pour faire passer tout ce beau monde d'une rive à l'autre ? Une traversée correspond à un unique trajet entre les deux rives ou entre une rive et l'ile.

N'hésitez pas à proposer votre solution même si vous n'avez pas le minimum et le 1er cas est plus facile à trouver que le second !

[catamat]

Bonjour

Pour le premier cas je dirai 2n -3
Pour n=2, 1 traversée suffit
puis tout couple supplémentaire oblige à effectuer deux traversées de plus, une d'un couple qui revient chercher le dernier couple et bien sûr le retour.
Donc suite arithmétique de raison 2 avec d'où

[TOUFAU]

Bonjour,

Le 1er cas est résolu par Catamat
Pour le second cas, quelques réflexions…
On constate immédiatement qu’une femme est soit seule, soit avec uniquement d’autres femmes, soit avec qui on veut ET son mari, que ce soit lors des traversées ou sur une rive/ile. Ce qui crée une contrainte forte dans une barque biplace.

En appliquant la ‘méthode bourrin’, on trouve une solution avec 6n-5 traversées :
- Une femme, que nous appellerons Josette, emmène chacune des autres sur l’ile
- Josette revient chercher son mari et l’emmène sur l’autre rive
- Le mari retourne chercher un des hommes, Alfred, et revient
- Alfred va chercher tous les hommes restants
- Josette ramène toutes les femmes de l’ile et c’est réglé.

J’optimise un peu l’algo en reprenant le constat initial (une femme peut rester seule sur une rive, en particulier au point de départ) pour obtenir 6n-7 traversées :
- Josette emmène toutes les femmes sauf 1 (Ursuline) sur l’ile, puis emmène son mari sur l’autre rive
- Le mari de Josette repart chercher Alfred, qui ensuite ramène tous les hommes sur l’autre rive sauf le mari d’Ursuline
- Josette ramène de l’ile toutes les femmes sauf une, Brigitte
- Le mari de Brigitte retourne chercher le mari d’Ursuline
- Josette ramène finalement Brigitte et Ursuline et c’est réglé.

Donc 6n-7 mais sans démo que c’est un minimum. A optimiser ou démontrer, donc…

[Kekia]

Bravo à vous 2, vous êtes très efficaces.
C'est effectivement le minimum TOUFAU et c'est assez bluffant que tu le sortes directement !
Il ne reste plus éventuellement qu'à trouver une démonstration.