|
#1 - 25-08-2012 12:47:06
- gilles355
- Professionnel de Prise2Tete
- Enigmes résolues : 49
- Messages : 421
nEigme du pont généralisée
Mon post précédent concernait un grand classique étant la traversée du pont en 17 minutes avec quatre personnes.
Voici l'énoncé http://www.prise2tete.fr/forum/viewtopic.php?id=10611
Dans un premier temps je vous demanderai de généraliser c'est à dire :
A met "a" minutes, B met "b" minutes, C met "c" minutes et D "d" minutes. avec a plus petit que b plus petit que c plus petit que d ...
Et la question ouverte que je me pose est : Y a t-il une formule pour généraliser pour x personnes ?
Exemple pour 7 personnes il y aurait : A met "a" minutes, B met "b" minutes, C met "c" minutes, D "d" minutes E met "e" minutes, F met "f" minutes et G met "g" minutes. avec a plus petit que b plus petit que c plus petit que d ...
#2 - 27-08-2012 00:12:52
- gilles355
- Professionnel de Prise2Tete
- Enigmes résolues : 49
- Messages : 421
Enigme ddu pont généralisée
Je pense avoir trouvé une formule en utilisant les termes d'une suite. La première personne mettant U0 minutes, la seconde U1 minutes etc.
#3 - 28-08-2012 11:57:46
- dhrm77
- L'exilé
- Enigmes résolues : 49
- Messages : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
enigmr du pont généralisée
Ca depend si le nombre de personnes est pair ou impair. 1: a 2: b 3: a+b+c 4: a+3b+d 5: 2a + 3b + c + e 6: 2a + 5b + d +f
pour la suite: pour le nombre impair suivant (7), on prend le temps mis par le nombre impair precedent (total pour 5) rajoute le temps de la nouvelle personne (G), plus le temps de A et 2 fois le temps de B.
pour le nombre pair suivant (8), on prend le temps mis par le nombre pair precedent (total pour 6) rajoute le temps de la nouvelle personne (H), plus le temps de A et 2 fois le temps de B.
en fait on peut generaliser a partir de 4 personnes.
Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt
#4 - 28-08-2012 13:54:58
- Klimrod
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 4050
- Lieu: hébesphénorotonde triangulaire
Enigme du pont égnéralisée
Bonjour,
Je pense que si la formule généralisée existe, alors elle doit être assez complexe.
Rien que le cas avec 4 personnes n'est déjà pas si facile que ça, car il y a a priori deux stratégies possibles.
Supposons a ≤ b ≤ c ≤ d.
1ère stratégie (cas 1-2-5-10) : a et b passent, a revient, c et d passent, b revient, a et b passent. Formule = d+3b+a
2ème stratégie (cas 1-4-5-10) : a et b passent, a revient, a et c passent, a revient, a et d passent. Formule = d+c+b+2a
Si je ne me suis pas trompé, pour 4 personnes, la formule générale est donc d+b+a+min(2b,a+c)
Je laisse le soin aux mordus de continuer pour 5 personnes et plus... Klim.
J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.
#5 - 28-08-2012 15:07:27
- gilles355
- Professionnel de Prise2Tete
- Enigmes résolues : 49
- Messages : 421
Enigm edu pont généralisée
dhrm77 a écrit:pour le nombre impair suivant (7), on prend le temps mis par le nombre impair precedent (total pour 5) rajoute le temps de la nouvelle personne (G), plus le temps de A et 2 fois le temps de B.
pour le nombre pair suivant (8), on prend le temps mis par le nombre pair precedent (total pour 6) rajoute le temps de la nouvelle personne (H), plus le temps de A et 2 fois le temps de B.
en fait on peut generaliser a partir de 4 personnes.
J'étais parti sur cette même idée mais à la lumière de Klimrod Klimrod a écrit:(cas 1-4-5-10) : a et b passent, a revient, a et c passent, a revient, a et d passent. Formule = d+c+b+2a
Je réalise que le problème devient trop complexe.
#6 - 28-08-2012 16:13:08
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 6,004E+3
enigme di pont généralisée
Si on appelle les candidats a,b, c d .... n du plus rapide au moins rapide
Le premier trajet compte 2 personnes dont a .
Si deux autres partent et une revient, on se retrouve de toute façon avec a au départ, donc autant le faire participer, on gagne du temps.
La seconde est b.
Vu qu'on a toujours a au départ, le seul cas ou il faut quelqu'un de l'autre côté c'est s'il doit faire un retour, donc autant qu'il soit le second plus rapide et dans ce cas, peu importe qui revient des 2 la première fois vu qu'ils feront tous 2 un aller retour. Mais bon , a revient en premier, c'est plus simple...
Si c et d repartent, le temps de trajet sera a+c+d si a et c repartent, le temps sera d+b+b
Donc c et d font le second trajet si a+c < 2b Sinon dès que le temps du suivant est c > 2b-a , a fait des aller retours.
#7 - 29-08-2012 13:56:52
- Klimrod
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 4050
- Lieu: hébesphénorotonde triangulaire
enigme du pont gébéralisée
@Gwen : Je pense que le bon raisonnement consiste à partir non pas des plus rapides, mais des plus lents.
Appelons a,b, c d .... n les candidats du plus rapide au plus lent. Donc a ≤ b ≤ c ... ≤ m ≤ n
Il faut d'abord s'intéresser au couple des deux plus lents m et n et leur appliquer l'une des deux stratégies.
1ère stratégie (si m ≥ 2b-a) : a et b passent, a revient, m et n passent, b revient. Formule = n+2b+a
2ème stratégie (si m ≤ 2b-a) : a et n passent, a revient, a et m passent, a revient. Formule = n+m+2a On remarque que si cette stratégie est préférable pour le couple (m,n), alors elle est également préférable pour tous les couples plus rapides (k,l), (i,j), etc, puisque que k est aussi ≤ 2b-a, ainsi que i, etc...
On voit donc se dessiner la stratégie globale :
Il faut grouper les plus lents par paires (m,n), puis les deux plus lents précédents (k,l), etc... jusqu'au couple (i,j) tant que que i > 2b-a (i strictement supérieur à 2b-a), et leur appliquer la 1ère stratégie. Leur trajet total durera (n+2b+a)+(l+2b+a)+...+(j+2b+a).
Pour les couples plus rapides suivants (g,h), (e,f), etc... il faut leur appliquer la 2ème stratégie. Leur trajet total durera (h+a+g+a)+(f+a+e+a)+...
Et le processus se termine avec les plus rapides. S'il en reste trois (a,b,c), alors (a,c) traversent, a revient et (a,b) traversent, pour un trajet d'une durée a+b+c. S'il en reste deux (a,b), alors (a,b) traversent, pour une durée de b.
Voilà. Il n'y a plus qu'à additionner tout ça, et on obtient deux formules, selon que le nombre total de passagers est pair ou impair. Les deux formules ne sont pas si compliquées que ça pour des spécialistes en LaTex. Klim.
J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.
#8 - 30-08-2012 09:28:49
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Eniigme du pont généralisée
Bien vu, ça me semble juste. Bien que je n'arrive pas avoir d'argument béton clair pour démontrer qu'il n'y a aucun intérêt à faire autrement. Assez étonnant qu'il faille procéder par paire et non individuellement ni non plus par triplet ou plus.
#9 - 30-08-2012 09:55:17
- Klimrod
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 4050
- Lieu: hébesphénorotonde triangulaire
Eniggme du pont généralisée
Il faut procéder par paires parce que dans l'énoncé ce sont des couples qui traversent le pont.
Si tu poses la même question avec des triplets qui traversent, eh bien le problème se résoudra par triplets et la récurrence se fera sur trois termes.
Voilà un truc amusant à programmer.... X personnes au départ et N personnes peuvent traverser simultanément.
J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.
#10 - 30-08-2012 12:18:00
- Christian91
- Passionné de Prise2Tete
- Enigmes résolues : 0
- Messages : 89
- Lieu: 91
Enigme du pont génééralisée
Klimrod a écrit:... on voit donc se dessiner la stratégie globale ...
C'est une image car on ne voit pas vraiment le dessin !
#11 - 30-08-2012 12:21:16
- Klimrod
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 4050
- Lieu: hébesphénorotonde triangulaire
enigme du ponr généralisée
Il n'y a ni dessin, ni image
J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.
#12 - 31-08-2012 11:32:46
- dhrm77
- L'exilé
- Enigmes résolues : 49
- Messages : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
Enigme du pont gnééralisée
C'est a dessin qu'il n'y ait pas d'image?
Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt
#13 - 31-08-2012 12:36:44
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,426E+3
Enigme du pon tgénéralisée
D'un autre côté si on commence à montrer des seins l'image du site
Vasimolo
Mots clés des moteurs de recherche
|
|