Inscription / Connexion Nouveau Sujet
La rivière
Salut!
voila une petite énigme qui tourne au cauchemar! XD
Pour franchir une rivière,3 missionnaires et 3 cannibales doivent utiliser une passerelle qui ne peut supporter plus de 2 personnes. Si à tout moment les cannibales sont plus nombreux que les missionnaires sur l'une des deux rives, les missionnaires seront tués et mangés. Les six protagonistes peuvent-ils traverser la rivière sains et saufs ? S'ils le peuvent, comment y arrivent-ils avec un minimum de traversées et quel est le nombre de façons de parvenir à ce minimum? Que se passe-t-il avec 4 missionnaires et 4 cannibales ?
Généraliser le problème avec a missionnaires et a cannibales, a=4,5 et 6 et une passerelle supportant p personnes (p=2,3,4,5). Sur la passerelle comme sur chacune des deux rives, les cannibales ne peuvent pas être plus nombreux que les missionnaires.
pour cette énigme aucun problème j'arrive a la faire, mais la personne qui me la poser a rajouter en plus "il faut qu'il y est autant de missionnaires que de cannibales a chaque traverser de chaque coter !
je doute que ce soit possible pourtant il ma certifié le contraire ! en ajoutant que celui qui me la poser est prof de maths ! donc la je bloque bien !
a vous de jouer !
Bonjour !
S'ils partent par 2 il n'y a pas de problème non ?
MMMCCC-> -
MMCC-> MC
MC -> MMCC
- -> MMMCCC
j'ai oublier de préciser que sur la barque ou ils sont deux il y a obligatoirement 1 qui doit revenir sur l'autre rive car la barque ne se conduit pas toute seul
tout d'abord, il est impossible d'avoir autant de missionaire que de canibale de chaque coté à tout moment, vu qu'a la première traversée, tu prends soit 2 C, et donc ce n'est pas équilibré, soit 1 C (quel intérêt ?), soit 1 M et 1 C, mais comme l'un des 2 doit revenir, il n'y aura pas l'équilibre des 2 cotés...
Ensuite, non seulement il y a une personne qui doit revenir sur la barque, mais il faut préciser qu'il y a toujours une personne sur la barque, c'est à dire qu'une personne ne débarque pas. Sinon on se retrouvera forcément avec plus de C que de M (avec M>0) d'un coté ou de l'autre. Si on note "~" la rivière, on a la berge gauche ~ la barque ~ la berge droite. Alors, un exemple minimum est:
3M3C ~ 0M0C ~ 0M0C
<->
3M1C ~ 0M2C ~ 0M0C
<->
3M1C ~ 0M1C ~ 0M1C
<->
2M1C ~ 1M1C ~ 0M1C
<->
2M1C ~ 0M1C ~ 1M1C
<->
1M1C ~ 1M1C ~ 1M1C
<->
1M1C ~ 0M1C ~ 2M1C
<->
1M0C ~ 0M2C ~ 2M1C
<->
1M0C ~ 0M1C ~ 2M2C
<->
0M0C ~ 1M1C ~ 2M2C
<->
0M0C ~ 0M0C ~ 3M3C
Pourquoi est-ce minimum ? A chaque débarquement sur la berge droite, si il reste du monde sur la berge gauche, une seule personne peut débarquer. Comme il y a 6 personnes, il n'y aura plus personne sur la berge gauche quand il y en aura 2 sur la barque et 4 sur la berge droite. Pour déposer ces 4 personnes, il faut donc 4 débarquements, et 1 dernier pour les 2 dernières personnes sur la barque. Cela fait donc 5 débarquements sur la berge droite nécessaire, cqfd...
On en déduit simplement que pour n C et n M, il faut donc 2n-1 débarquements sur la berge droite pour les mêmes raisons...
Maintenant, quand au nombre de possibilités de séquences de passages minimum, je n'y ai pas encore réfléchi, mais j'y penserai ^^ ca ressemble a du dénombrement a mon avis ^^
edit:
il y a un décalage sur les <-> : ceux les plus a droite correspondent a l'échange barque <-> berge droite, ceux les plusa gauche, barque <-> berge gauche
edit: décidément, je n'ai pas bien lu ton problème...
donc pour élargir à n C et n M, ainsi qu'une barque supportant p voyageurs, avec p < 2n (sinon 1 voyage suffit), le principe est le même. [] (partie entière inférieure) débarquements sur la berge droite sont nécessaires pour débarquer tout les premiers voyageurs, et 1 voyage supplémentaire pour les voyageurs restants, donc un total de [
] +1.
Bonjour,
Reprenons l'énoncé :
Pour franchir une rivière,3 missionnaires et 3 cannibales doivent utiliser une passerelle qui ne peut supporter plus de 2 personnes. Si à tout moment les cannibales sont plus nombreux que les missionnaires sur l'une des deux rives, les missionnaires seront tués et mangés. Les six protagonistes peuvent-ils traverser la rivière sains et saufs ? S'ils le peuvent, comment y arrivent-ils avec un minimum de traversées et quel est le nombre de façons de parvenir à ce minimum? Que se passe-t-il avec 4 missionnaires et 4 cannibales ?
Et là, il faut commencer par se mettre d'accord sur la signification du mot "passerelle". D'après le dictionnaire en ligne www.mediadico.com :
Passerelle : (nom féminin) Pont étroit pour les piétons.
Il ne s'agit donc pas d'une barque qu'il faut ramener de l'autre côté , et il suffit que nos voyageurs traversent deux par deux (un missionnaire et un cannibale) pour que personne ne se fasse boulotter... à moins bien sûr que les cannibales, pour avoir leur casse-croute quand-même, n'aient démonté la fameuse passerelle pour en faire un radeau, puis du bois pour le feu
Haha, oui en effet ><', je pense que j'aurais mieux fait de dormir. Et s'il faut la même quantité de Cannibale et de Missionaire de chaque coté à chaque fois, il suffit d'en envoyer le même nombre quelque soit la capacité de la passerelle.
Après, ramoutcho a bien parlé de barque dans sa réponse, alors quel est l'énoncé exact ?
Annuler
connectez vous