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 - 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 ...

  • |
  • Répondre

#0 Pub

 #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 ! big_smile

 #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 lol


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 sad

Vasimolo

 

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
25-08-2012 Enigmes Logiques
P2T
13-10-2008 Enigmes Logiques
P2T
Suite 3-7-12 ... par Sophus
24-08-2007 Enigmes Logiques
P2T
100=11+12??? par stella-gemella
09-04-2011 Enigmes Logiques
P2T
Logigramme des Sages par fvallee27
22-06-2015 Enigmes Logiques
P2T
Tristan et Iseut par gaara2a
29-05-2009 Enigmes Logiques
17-02-2016 Enigmes Logiques
03-11-2011 Enigmes Logiques
P2T
10-11-2024 Enigmes Logiques

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