Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 02-02-2014 13:25:08

cogito
Expert de Prise2Tete
Enigmes résolues : 48
Messages : 593

traverdée + généralisation

Bonjour,

Cet énigme aura sans doute un air de déjà vu, c'est un grand classique qui a été proposé il n'y a pas longtemps, mais quand même, je prend le risque de me faire "asher" menu menu big_smile :

Quatre personnes veulent traverser un pont en pleine nuit.
Ils ne disposent que d'une seule torche, et le pont est fragile, il ne peut supporter que le poids de deux personnes. Le pont est troué par endroit, et il serait suicidaire d'essayer de le traverser sans rien voir.

Parmi les quatre personnes il y a :

-Une jeune elfe très agile qui peut traverser le pont en 2 minutes.
-Un mage endurant qui peut traverser le pont en 4 minutes.
-Un guerrier qui, encombré par son armure, met 12 minutes pour traverser le pont.
-Un nain bourru qui a le vertige, lui met 20 minutes à traverser.

Comment feront nos héros pour traverser ce pont en un minimum de temps ?

Certes c'est un classique, mais quelqu'un du forum (je n'ai pas retrouvé où hmm)
a dit que de temps en temps, ça ne fait pas de mal de réviser ses classiques.

Dans la discussion ici :

http://www.prise2tete.fr/forum/viewtopic.php?id=11710

Tous le monde à dit que c'était trop facile, tous le monde connais, mais tous ceux qui ont donnés une réponse, ont donnés une réponse fausse.

Donc révisons nos classiques, le temps minimum n'est pas 40 minutes.

Question bonus 1 : Et puisque c'est un classique, allons-y pour le cas général où le temps des personnages est a, b, c, et d (avec a < b < c < d) ?

Question bonus 2 : Et si au lieu d'avoir 4 personnages, il y a [latex]n[/latex] personnages dont les temps respectifs sont [latex]a_1,\ldots, a_n[/latex] avec [latex]a_1 <\ldots < a_n[/latex] ??



Annonces sponsorisées :

Il y a sûrement plus simple.
  • |
  • Répondre

#0 Pub

 #2 - 02-02-2014 13:42:48

JeanDaft
Amateur de Prise2Tete
Enigmes résolues : 41
Messages : 3

Traversée + généralistaion

2 et 4 font le trajet => 4 min
2 revient => 6min
12 et 20 font le trajet => 26 min
4 revient => 30 min
2 et 4 font le trajet => 34 min
TOTAL = 34 min (j'espère avoir été clair dans l'explication)

 #3 - 02-02-2014 14:02:51

SabanSuresh
Elite de Prise2Tete
Enigmes résolues : 45
Messages : 1945
Lieu: Paris

yraversée + généralisation

En effet, le minimum est de 34 minutes.

Aller Elfe et Mage → 4 minutes
Mage revient → 8 minutes
Aller Nain et Guerrier → 28 minutes
Elfe revient → 30 minutes
Aller Elfe et Mage → 34 minutes.

Voilà !

 #4 - 02-02-2014 15:06:08

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,466E+3

Traversée + géénralisation

Effectivement, il est rigolo de constater que bien que boudant l'énigme, personne ne l'ai résolue car c'est effectivement du déjà vu maintes fois...

2+4 =4

2=2
10+20=20
4=4
2+4=4

total : 34

 #5 - 02-02-2014 15:44:39

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 639

Traevrsée + généralisation

1) elfe et mage traverse => 4 min
l'elfe revient => 6 min
2) le nain et le guerrier traverse => 26 min
le mage revient => 30 min
3) les deux derniers traversent => 34 min

C'est un classique ...

 #6 - 02-02-2014 19:50:28

cogito
Expert de Prise2Tete
Enigmes résolues : 48
Messages : 593

Travesée + généralisation

Cette fois que de bonnes réponses smile


Il y a sûrement plus simple.

 #7 - 02-02-2014 20:15:26

cogito
Expert de Prise2Tete
Enigmes résolues : 48
Messages : 593

rTaversée + généralisation

Il y a deux questions bonus supplémentaires, pour la généralisation.


Il y a sûrement plus simple.

 #8 - 02-02-2014 20:17:28

ash00
Sage de Prise2Tete
Enigmes résolues : 49
Messages : 5,568E+3

Traversée + généralisaion

C'est du déjà vu !! Pfff... toujours la même chose...

lol


34 minutes au mieux. Mais maintenant, cela dépend du poids de chacun.
En effet, un de mes amis l'explique bien :

 #9 - 02-02-2014 23:01:57

Nombrilist
Expert de Prise2Tete
Enigmes résolues : 10
Messages : 562

traversée + génétalisation

1 - mage+elfe = 4
2 - elfe = 2
3 - guerrier+nain = 20
4 - mage = 4
5 - mage + elfe = 4

Soit 34 minutes. Ou encore a+3b+d. Le résultat est indépendant de c !

Et sinon, pour n pair:
[TeX]t = \sum\limits_{i=2}^\frac{n}{2}{(2a_2+a_1+a_{2i})}+a_2[/TeX]
Et pour n impair:
[TeX]t = \sum\limits_{i=2}^\frac{n-1}{2}{(2a_2+a_1+a_{2i+1})}+(a_1+a_2+a_3)[/TeX]
En espérant ne pas avoir fait d'erreur.

 #10 - 03-02-2014 00:30:45

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 639

Traversée + généarlisation

Question 1 :
C'est a et b qui traversent
L'un des deux revient
c et d traversent
l'autre revient
et a et b traversent

Question 2 :
Cas paire :
Les deux plus rapides traversent (a et b)
l'un ramène la torche (a ou b)
Les deux plus lents qui restent traversent
l'autre ramène la torche (a ou b)
et on recommence

Cas impair

Pareil que le cas pair jusqu’au moment où il reste 3 personnes
Le plus rapide traverse avec l'un puis revient chercher l'autre.

 #11 - 03-02-2014 08:17:55

cogito
Expert de Prise2Tete
Enigmes résolues : 48
Messages : 593

Traversée + généralisatioon

Pour la généralisation, malheureusement ce n'est pas aussi simple que cela.
Pour la question 1, si, le résultat dépend de c !!

Sinon, j'ai peut-être été un peu rapide pour poser la question 2 hmm.
On va dire que pour l'instant c'est une question ouverte.


Il y a sûrement plus simple.

 #12 - 03-02-2014 12:15:50

kossi_tg
Professionnel de Prise2Tete
Enigmes résolues : 18
Messages : 301
Lieu: Montargis

Traversée + généralsiation

La question 2 étant devenue ouverte, je vais y aller avec la 1 tout en continuant de réfléchir sur la 2:

1-) a et b vont l'allée et a ramène la torche: (b+a) min
2-) c et d font l'allée et b ramène la torche : (d+b) min
3-) a et b font l'allée pour finir: (b) min

Au total on aura mis: (d+3b+a) min soit 34min pour a=2,b=4,c=12etd=20

 #13 - 03-02-2014 15:09:02

kossi_tg
Professionnel de Prise2Tete
Enigmes résolues : 18
Messages : 301
Lieu: Montargis

Traversée + généraisation

Une proposition pour le cas général 2 valable pour les cas où [latex]2*a_2 \leq a_1+a_x[/latex] pour tout x:

*** Pour [latex]n \leq 2[/latex]: [latex]temps=a_n[/latex]

*** Pour [latex]n \geq 3[/latex]:
En appliquant le même principe que le cas particulier 1, [latex]a_1[/latex] et [latex]a_2[/latex] vont s'occuper des autres en faisant les aller/retour en constituant des pseudo-équipes de 4 personnes à chaque fois: [latex]a_1[/latex], [latex]a_2[/latex], [latex]a_x[/latex] et [latex]a_{x+1}[/latex], x>2 et x<n.

Après combinaison, on trouve les 2 formules suivantes; à confirmer ou à infirmer lol

1-) Si n est pair, on pose [latex]p=\frac{n}{2}[/latex]
[TeX]temps=\sum_{i=2}^{p}a_{2i}+(p-1)*a_1+(n-1)*a_2[/TeX]
2-) Si n est impair, on pose [latex]p=\frac{n-1}{2}[/latex]
[TeX]temps=\sum_{i=1}^{p}a_{2i+1}+p*a_1+(n-2)*a_2[/TeX]
Voilà

 #14 - 03-02-2014 18:57:06

cogito
Expert de Prise2Tete
Enigmes résolues : 48
Messages : 593

traversér + généralisation

Non kossi_tg, pour la question 1 le résultat dépend de c !!


Il y a sûrement plus simple.

 #15 - 03-02-2014 19:10:43

Nombrilist
Expert de Prise2Tete
Enigmes résolues : 10
Messages : 562

traversée + générzlisation

Ah oui, si a=2 ; b=4 ; c=5 ; d=20, alors

a-c = 5
a = 2
a-d = 20
a = 2
a-b = 4

fait 33 minutes et donc mieux que 34 minutes. Donc, dans cet exemple, le résultat serait indépendant de c si c est compris entre 6 et 20 ?

 #16 - 03-02-2014 19:17:23

kossi_tg
Professionnel de Prise2Tete
Enigmes résolues : 18
Messages : 301
Lieu: Montargis

tracersée + généralisation

Oui cogito, je trouve maintenant pour le cas général 1, [latex]temps=min(a+3b+d ; 2a+b+c+d)[/latex] selon que 2b<a+c ou pas.

 #17 - 03-02-2014 19:25:45

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,466E+3

Traversée + génralisation

Question 1 :

si c > 2b-a  (je parle de temps de parcours) , alors on emploie le trajet clasique de l'énigme. a et b passent, a revient, c et d passent b repart puis revient avec a.

si c< 2b-a , il est plus économique de faire faire les aller retour à a qui emméne chacun puis revient chercher le suivant.

Question 2 : Soient L le plus lent et L' le plus lent en second.

Tant que L' > 2b-a, on fait passer le couple L L' avec la première méthode.

Dès que L' < 2b-a , a fait passer tout le monde un par un.

 #18 - 03-02-2014 21:08:43

Moriss
Professionnel de Prise2Tete
Enigmes résolues : 37
Messages : 460

Traversée + généralisatio

cogito a écrit:

Tout le monde a dit que c'était trop facile, tout le monde connait, mais tous ceux qui ont donné une réponse, ont donné une réponse fausse.

C'est très vrai, ça m'avait d'ailleurs choqué mais la discussion était fermée...

Pour le problème à 4, l'idée est de faire traverser les plus lents ensembles. Pour cela, les plus rapides se répartissent de part et d'autre du pont, puis les 2 lents traversent, puis un des 2 rapides ramène la torche pour revenir avec son collègue de l'autre côté du pont. Concrètement :
a et b traversent.
a ramène la torche.
c et d traversent.
b ramène la torche.
a et b traversent.
Durée du parcours : a + 3b + d = 34 minutes.

Mieux que si a fait tous les voyages (il traverse avec chacun et ramène la torche à chaque fois) : 2a + b + c + d = 40 minutes.

Question bonus 1
Si a, b, c et d inconnus, les durées des stratégies se comparent ainsi :
a + 3b + d versus 2a + b + c + d
càd 2b versus a+c
Il suffit donc de comparer ces deux valeurs pour connaître la meilleure stratégie.

Question bonus 2
La première stratégie fait passer les 2 plus lents ensembles. La seconde stratégie fait passer les plus lents un par un. Dans les 2 cas, lorsqu'on a fait passer les 2 plus lents et ramené la torche au départ, les deux stratégies ont abouti au même résultat.
Il est donc possible de changer de stratégie à chacun de ces moments !!
Il est donc logique de comparer les 2 stratégies à chaque fois qu'elles sont intervertibles, afin de toujours utiliser la méthode la plus optimale.

La stratégie 1 fait traverser a et b, puis a (ou b) revient, puis les 2 plus lents traversent, puis b (ou a) revient. Durée : a + 2b + z (z = le temps du plus lent).

La stratégie 2 fait traverser a avec z, puis a revient, puis a traverse avec y, puis a revient. Durée : 2a + y + z.

Comparaison des 2 stratégies : a + 2b + z versus 2a + y + z
Càd 2b versus a + y.
Ce qui d'ailleurs s'applique parfaitement au cas à 4 voyageurs.

Donc, chaque fois que les 2 plus lents ont traversé, on refait la comparaison avec les 2 plus lents suivants pour choisir la nouvelle stratégie à adopter. On obtient donc la solution la plus optimale !

NB : s'il n'y a plus que 3 voyageurs, les 2 stratégies reviennent au même.
Stratégie 1 :
a et b traversent ;
a revient ;
a et c traversent.
Stratégie 2 :
a et c traversent ;
a revient ;
a et b traversent.

CQFD big_smile

 #19 - 03-02-2014 22:26:14

fix33
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1198
Lieu: Devant un clavier depuis 1748

Taversée + généralisation

On a le droit de lancer le nain ou pas ? lol


Je ne vien sur se site que pour faire croir que je suis treise intélligens.

 #20 - 03-02-2014 22:29:47

fix33
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1198
Lieu: Devant un clavier depuis 1748

Traversée + généraliisation

Après quelques tâtonnages (c'est vrai qu'on oublie vite) :
- 4 & 2 traversent (4).
- 2 revient (2).
- 12 & 20 traversent (20).
- 4 revient (4).
- 4 & 2 traversent (4).
=> 34 !


Je ne vien sur se site que pour faire croir que je suis treise intélligens.

 #21 - 03-02-2014 23:22:40

cogito
Expert de Prise2Tete
Enigmes résolues : 48
Messages : 593

Traversée + génééralisation

@Nombrilist: c'est cela, donc en comparant les deux expressions générales que tu obtiens tu peux conclure.

@fix33: Rien à redire.

@kossi_tg: Oui pour la question 1.

Et bravo à gwen27 et Moriss qui font un carton plein !  cool


Il y a sûrement plus simple.

 #22 - 04-02-2014 09:22:59

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

teaversée + généralisation

Pour l'énoncé original, le minimum est de 34 minutes
- aller de 2 et 4 => 4
- retour de 2 => 6
- aller de 12 et 20 => 26
- retour de 4 => 30
- aller de 2 et 4 => 34

On remarque qu'il faut 2 trajets pour faire passer une personne, et un seul pour faire passer les deux dernières personnes. Pour N personnes il faut donc au minimum2(N-2)+1 trajets

Pour la "petite" généralisation à 4 personnes, a<b<c<d, il faut donc 5 trajets.
2 options se posent:
- le plus rapide fait l'aller retour avec chacun. Total b+a+c+a+d = 2a + b + c +d
- les deux plus rapides ramènent la torche à tour de rôle et les plus lents partent ensembles : b+a+d+b+b = a+3b+d
En comparant les deux on trouve qu'il est plus rapide d'utiliser l'option 1 si a et c ont une meilleure moyenne que b (a+c < 2b), et l'autre option sinon.

Exemple:
* 2-8-9-12 nous donne 8+9+12+2+2 = 33 avec l'option 1, 8+2+12+8+8 = 38 avec l'option 2
* 2-5-9-12 nous donne 5+9+12+2+2 = 30 avec l'option 1, 5+2+12+5+5 = 29 avec l'option 2.

Pour la "grande" généralisation  j'y pense.

 #23 - 04-02-2014 09:54:49

fmifmi
Passionné de Prise2Tete
Enigmes résolues : 18
Messages : 87

Traversée + généralistion

Corrigé erreur étourderie.

"mais bon sang,mais c'est bien sûr .C'est clair comme de l'eau de roche". Comment n'y ai je pas pensé avant.

4 et 2 traversent                                                            (4 mn)
2 reste en face tout seul comme un grand et 4 revient       (4 mn)
12 et 20 traversent ensemble                                         (20 mn)
2 qui etait resté en face revient avec la torche                  (2mn)
2 retraverse avec 4                                                         (4mn)

total                                                                               34 mn


On peut faire mieux :(28 mn)  en respectant strictement l'énoncé.
En effet rien n’oblige 2 a revenir chercher 4 qui a déjà traversé le pont une fois.
on dit bien "traverser le pont" mais pas rester de l'autre coté.   lol

 #24 - 04-02-2014 10:25:33

cogito
Expert de Prise2Tete
Enigmes résolues : 48
Messages : 593

Traversée + généralistaion

@scarta : C'est un parfait début.

@fmifmi: Bravo, commissaire Bourrel ! wink  (à part une toute petite erreur d'étourderie, quand le mage traverse le pont, il met 4 minutes et pas 2)


Il y a sûrement plus simple.

 #25 - 04-02-2014 12:38:35

Fito11235
Professionnel de Prise2Tete
Enigmes résolues : 48
Messages : 148
Lieu: Bourgogne

Traverse + généralisation

Coucou

Je noterai E2 pour l'elfe qui met 2 min, M4 pour le mage qui met 4 min,...

Départ --> Arrivée

E2 M4       -->   4min      (b)
E2           <--    2min      (a)
N20 G12   -->   20 min    (d)
M4           <--   4min       (b)
E2 M4       -->   4min       (b)

ET voilà, tout le monde est passé en 34 min smile.

Pour la première généralisation : Par analogie on devrait avoir a + 3b + d min.

Pour la deuxième ... à suivre.


Choose a job you like and you'll never have to work a day in your life.    Confucius

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Si il y a 63 pommes et que vous en prenez 23, combien en avez-vous ?

Sujets similaires

Sujet Date Forum
P2T
12-10-2007 Enigmes Mathématiques
02-10-2011 Enigmes Mathématiques
20-07-2009 Enigmes Mathématiques
P2T
08-03-2008 Enigmes Mathématiques
P2T
16-10-2015 Enigmes Mathématiques
P2T
La baignoire par shadock
20-11-2009 Enigmes Mathématiques
P2T
Gâteau 104 par Vasimolo
12-09-2015 Enigmes Mathématiques
P2T
Le Polynôme par Promath-
06-09-2014 Enigmes Mathématiques
P2T
Flew Marties par Vasimolo
29-03-2014 Enigmes Mathématiques

Mots clés des moteurs de recherche

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete