Bonjour,
je suppose que vous connaissez tous le très célèbre problème des sept ponts de Königsberg, plus ou moins à l'origine de la théorie des graphes par Euler :
Jamo a décidé de dépoussiérer ce problème en provoquant une grande tempête sur la ville. (et c'est une des rares fois où l'énigme vient presque entièrement de moi).
Rappelons vite fait la situation de la ville : elle est traversée par une rivière qui délimite ainsi plusieurs zones qui sont accessibles entre elles par 7 ponts.
Sur le schéma de droite ci-dessous, on y voit la rivière en bleu, la ville en vert, et les ponts en jaune.
Voilà qu'une terrible tempête est annoncée et va s'abattre sur la ville !!
Un spécialiste en génie civil estime que chaque pont a une chance sur deux de s'effondrer.
Question : dans ces conditions, quelle est la probabilité de pouvoir encore aller du sud au nord de la ville après la tempête ? (c'est-à-dire de la zone A à la zone B, ou de B à A)
Je veux la valeur exacte, sous forme de fraction (ou décimale si ça tombe "juste"). Une probabilité est un nombre entre 0 et 1, je ne veux pas de pourcentages.
Le trajet de A à B ne peut se faire qu'en empruntant les ponts, donc je ne veux pas qu'on me dise qu'il suffit de nager ou d'aller chercher un pont plus loin.
Je mets 3 étoiles parce que je demande la valeur exacte, afin d'éviter des solutions approximatives obtenues de manière hasardeuse (ce serait un comble pour un problème de probabilité ). Mais je ne sais pas si l'énigme mérite autant d'étoiles, j'ai toujours du mal à estimer la difficulté des problèmes que je propose.
Bonne recherche !
P.S. : j'en profite pour faire une petite "pub" sur un problème ouvert que j'ai soumis ici : Problème ouvert : probabilités avec un dé pyramidal , si les grands esprits qui se rencontrent sur le forum des énigmes veulent bien s'y pencher ...
Bonjour Jamo,
ma réponse:
il y a 7 ponts et 2 possibilités par pont soit 27 = 128 cas possibles
il y a 9 passages différents possibles pour aller de A en B
sur les 128 cas j'ai compté (sauf erreur) 92 cas favorables
Bonjour,
il y a 5 trajets qui passent par 2 ponts. On a une chance sur 4 de passer
il y a 4 trajets possibles qui passent par 3 ponts. On a une chance sur 8 de passer
En tout on a 5 chances sur 20 de passer par un trajet de 2 ponts et 4 chances sur 32 de passer par un trajet de 3 ponts.
5/20+4/32 = 1/4+1/8 = 3/8 de chances de passer par n'importe quel trajet.
La probabilité de rejoindre la rive A à partir de B ou l'inverse est de 0,375
Bonjour,
très joli problème !
Ici le cas d'équiprobabilité (p=1/2) nous simplifie grandement la tâche (enfin je crois) et permet de se limiter à du dénombrement.
Un pont étant soit détruit soit conservé, il y a 2^7=128 possibilités (configurations totales de ponts possible).
Reste à dénombrer le nombre de configurations laissant un passage sud-nord ou plus simplement, via le complémentaire, celles n'en laissant aucun.
En numérotant les ponts de A à G (en partant du bas à gauche et dans le sens direct), seules les configurations contenant AG, AF, ADE, BG, BF, BDE, CE, CDF, CDG sont valables.
En passant par le complémentaire, je dénombre (sauf erreur) 36 configurations coupant tous les passages possibles.
La probabilité est donc de .
Merci pour l'Enigmo.
Les modélisations sont multiples, mais en cas d'équiprobablité celle-ci me parait la plus simple...(mais plus valable dans le cas général)
Bonjour.
La probabilité est 99/128 = 0,7734375.
Probabilité que le pont reliant les deux îles soit intact et que le passage reste possible : 1/2 * 7/8 * 7/8 = 49/128.
Probabilité que ce pont soit détruit et que le passage soit possible par l'île ouest : 1/2 * 3/4 * 3/4 = 9/32.
Probabilité que ce pont soit détruit, que le passage soit impossible par l'ouest, mais possible par l'est : 1/2 * 7/16 * 1/4 = 7/64.
Probabilité totale : 49/128 + 9/32 + 7/64 = 99/128.
bonjour,
On a 9 chances sur 29 (d'ou la probabilité est de ) pour qu'on puisse passer de A vers B (ou de B vers A).
merci.
La probabilité de pouvoir traverser après la tempête est de : 23/32.
On note : O=Ouvert, F=Fermé
Considérant les 2 ponts de droite, ils peuvent être : OO, OF, FO, FF, avec chaque fois 1 chance sur 4.
Si OO : alors on passe dans 1/1 cas
Si FF : alors on passe dans 3/4 * 3/4 cas
Si 0F : alors on passe 3/4*(3/4+1/2-1/2*3/4)
Si FO : alors idem que OF
Donc au total :
P = 1/4*[1+9/16+2*3/4*(3/4+1/2-1/2*3/4)]
P = [16+9+3*(6+4-3)]/64
P = [46]/64
P = 23/32
Merci pour l'énigme.
Bonjour
Grâce à un arbre, je dirais que la probabilité de pouvoir encore joindre A et B vaut 23/32
MM
Salut Jamo
Je trouve une probabilité de 23/32 , en espérant ne pas m'être trompé !
Merci pour l'énigme !
Bonjour
-------Réponse proposée--------
p = 23/32
-------Methode employée-------
Par dénombrement, en examinant les 2^7 = 128 possibilités, des cas où la traversée est possible
Je note les sept ponts par A, B, ..., F et G (fig.1) et leur valeur = 0 pour pont-coupé et = 1 pour pont-non-coupé
La traversée T est donnée par la formule excel T = OU(A*E;A*F;A*D*G;B*E;B*F;B*D*G;C*D*E;C*D*F;C*G)
La fonction NB.SI( ) fournit 92 cellules où T = 1 (fig.2)
Comme les probabilités de présence des ponts sont égales et valent 1/2, chacune des 128 lignes est équiprobable
La probabilité cherchée vaut donc 92/128 = 23/32
Je pense cependant m'être trompé dans le raisonnement car ce résultat semble bien simple au vu des 3 étoiles...
---------Enigme associée---------
Pour rendre cette énigme encore plus difficile, il est possible de donner une probabilité différente sur la robustesse de chacun des ponts
Par exemple (fig.3) ,
- une probabilité de 1/1 pour que le pont n°1 soit détruit,
- une probabilité de 1/2 pour que le pont n°2 soit détruit,
- une probabilité de 1/3 pour que le pont n°3 soit détruit,
- une probabilité de 1/4 pour que le pont n°4 soit détruit,
- une probabilité de 1/5 pour que le pont n°5 soit détruit,
- une probabilité de 1/6 pour que le pont n°6 soit détruit,
- une probabilité de 1/7 pour que le pont n°7 soit détruit.
Il est alors demandé de chercher la probabilité de pouvoir traverser du Nord au Sud
Rudy
bonjour jamo,
je note les ponts situés au nord,les ponts situés au sud et M le septième pont
il y a 9 trajets possibles pour aller du sud au nord en empruntant les ponts
si E est l'évènement "on peut passer du sud au nord après la tempête" je cherche la probabilité dec'est à dire qu'aucun des chemins ne soit utilisable
je trouve
( soit environ 0,769 ce qui me semble être beaucoup )
merci pour cet énigmo
Bonjour jamo,
La probabilité de pouvoir aller du sud au nord de Königsberg après la tempète
est 0.71875.
Bonjour,
Ma réponse est 23/32, soit 0,71875.
J'ai trouvé 27=128 combinaisons possibles de ponts soit intacts, soit écroulés.
Il y a 9 chemins minimaux possibles permettant de passer du sud au nord.
Le nombre de cas où au moins un de ces chemins ne comporte aucun pont écroulé est égal à 92, d'où le résultat.
notons:
a,b et c les ponts partant de la berge A
d,e et f les ponts partant de la berge B
g le pont reliant les deux iles
la probabilité d'avoir k ponts "KC" est P(k)=C7k * (1/2)k * (1/2)7-k = C(k,7) * (1/2)7
puisqu'il y a indépendance et 1/2 de casse
avec 0,1 ou 2 ponts KC on traverse toujours
avec 3 ponts KC on ne traverse pas si c'est abc ou def donc 33 cas où on peut traverser
avec 4 ponts KC on ne traverse pas si c'est abcx ou defx ou abgf ou degc où le x représente un pont qq soit 10 cas qui ne marche pas et 25 cas où on peut traverser
avec 5 ponts KC les seuls chemins permettant de traverser sont ad,ae,bd,be et cf (les 5 autres ponts étant KC) dont 5 cas
avec 6 ou 7 ponts KC on ne traverse pas
soit un total de (1+7+21+33+5)/128=67/128
Tout d'abord, essayez de ne pas vous moquer da ma proposition, je suis en 3ème et les probabilités sont du programme de cette année, alors j'ai peut-être une proposition ridicule. De toute façon je crois que j'ai faux, le résultat ne me revient pas...
J'ai en fait réalisé toutes les combinaisons possibles pour aller du Sud au Nord et j'ne ai trouvé 9, soit 5 en empruntant deux ponts et 4 en empruntant trois ponts.
Probabilité qu'une combinaison de deux ponts tienne : 0,25
Probabilité qu'une combinaison de trois ponts tienne : 0,125
J'ai donc fait la moyenne de toutes les probabilités...
Moyenne : (5*0,25 + 4*0.125) / 9 = 1,75 / 9 = 7 / 36
Réponse : 7 / 36 (ça doit vraiment pas être ça...)
Bonjour l'équipe,
voila je propose cette réponse : La probabilité d'aller du sud au nord après cette terrible tempête est de 1\2
Je reste quand même perplexe.....
Merci ,
Pour étudier le pb j'ai pris 1/2/3 pour les ponts de A 4 le pont de l'île et 5/6/7 les ponts de B ;en système heptal il y a 128 nombres entiers possibles de 1 à 1234567; seuls les chemins 15 16 25 26 37 147 247 345 et 346 sont possibles .
on trouve ;
NB PONTS DETRUITS 0 1 2 3 4 5 6 7
NB DE POSSIBILITES 1 7 21 35 35 21 7 1
PASSAGES POSSIBLES 1 7 21 33 25 5 0 0
En pondérant,je trouve 0.71875probabilités de traverser de A vers B ou B vers A
sur 128 possibiltés , il y a 36 qui ne collent pas,
ca fait une probabilité de 1 - 36/128
soit 0. 71875
position des ponts:
[zone B]
(7) (8) (5)
=============(4)====
(1) (2) (3)
[zone A]
de A à B:
(1)->(7) P1= 0.5 *0.5= 0.25
(1) -> (8) P2= 0.5 *0.5= 0.25
(1) -> (4) -> (5) P3= 0.125
(2)->(7) P4= 0.5 *0.5= 0.25
(2) -> (8) P5= 0.5 *0.5= 0.25
(2) -> (4) -> (5) P6= 0.125
(3) -> (5) P7=.5
(3) -> (4) -> (7) P8=.125
(3) -> (4) -> (8) P9=.125
Ptot = sommes des P/(n possibilités) = 2.25/9 =0.25
P=.25 => une chance sur 4
Tout d'abord, merci! C'est le meilleur site d'énigmes que j'ai visité, et j'en ai visité... (faut bien s'occuper en stage :p)
Maintenant concernant l'énigme:
p = la proba de pouvoir passer de A à B
q = la proba de ne pas pouvoir passer de A à B = 1 - p
j'ai numéroté les pont:
1 2 3
7
4 5 6
on ne peut pas passer si:
"1 est cassé" ET "2 est cassé" ET "3 est cassé"
OU
"4 est cassé" ET "5 est cassé" ET "6 est cassé"
OU
"1 est cassé" ET "2 est cassé" ET "6 est cassé" ET "7 est cassé"
OU
"3 est cassé" ET "4 est cassé" ET "5 est cassé" ET "7 est cassé"
donc q = (1/2)3 + (1/2)3 + (1/2)4 + (1/2)4
= 3/23
p = 1 - q
= (23 - 3)/23 = 0.625
la probabilité de pouvoir passer après la tempête de A à B est selon moi de 0.625
Merci, et bonne continuation
Clôture de l'énigme
Il y avait en tout 128 configurations possibles.
Su ces 128, 92 permettent d'aller de A et B, d'où une probabilité de 92/128=23/32=0,71875
Bravo à tous ceux qui ont trouvé !
Bonsoir,
comme beaucoup l'ont montré, il y a en effet 128 solutions à considérer suivant que chaque pont est détruit ou non.
Mais je pense que concernant les passages possibles, il y a une erreur de raisonnement. En effet, quand on veut par exemple passer de A à G,(voir figure de Manpower) peut importe que B,C,D,E ou F soient détruits ou non.Un certain nombre de possibilités disparaissent donc de la statistique.
En réalité voici les passages possibles pratiquement:
AG, AF ADE ABCE (qui n'a pas de sens si on longe la rive de A à C)
BG BF BDE BACE (qui n'a pas de sens si on longe la rive de B à C)
CDG, CDF et CE
Pour le raisonnement, je maintiens ma réponse précédente.
Bien à vous
J'ai oublié de préciser que les 128 solutions correspondent à un passage successif par chacun des 7 ponts: ce qui n'est pas le cas !
Bien à vous
Bonjour castoriginal
Si je te comprends bien, en prenant tes identifications de ponts, lorsque tu cites ABCE, tu proposes de considérer ce trajet là :
mais alors pourquoi ne pas avoir cité, dans ce cas, toujours en commençant par A : ABCDG et ABCDF
idem en commençant par B où tu ne cites que BACE : il reste aussi BACDG et BACDF
même remarque en commençant par C où tu ne cites pas les passages par A ou B : CDABG, CDABF, CDBAG, CDBAF voire même reprendre le pont D...
Quand tu insistes sur le mot "pratiquement", je ne vois pas l'intérêt pratique de ABCE, par exemple :
pourquoi quitter la rive sud par le pont A, aller sur la première isle aux cinq ponts, pour ensuite revenir par le pont B sur la rive sud et enfin prendre le pont C ?
Là où je suis d'accord avec toi, c'est l'opportunité des trajets possibles
Pour l'illustrer, j'ai considéré les 3 ponts G, F et D coupés : la seule possibilité est alors de passer par C et E,
En faisant les filtres idoines dans le tableau excel, on dénombre bien 4 trajets (qui participent aux 92) C-E indépendants de l'état des ponts A et B :
Et, où tu as raison, certaines configurations ne correspondent à aucune réalité de trajet possibles,
Ici les cas où (E-C et A) et (E-C et B) ne reflètent pas des trajets réalisables contrairement à E-C-A-B que tu avais identifié et qui offre peu d'intérêt comme je l'ai souligné plus haut
Je me demande alors si tu ne désires pas retirer, des 128 cas recensés, les cas d'aller-retour à une rive (tels les A-B de la figure 1 ci-dessus) ?
En tout cas, ta remarque mérite réflexion et doit changer la probabilité recherchée, qui avait été jugée correcte avec 23/32
Je ne sais pas, néanmoins, si on répond au même énoncé...
Qu'en pense la communauté ?
Rudy
Ce que j'en pense est très simple.
Nous sommes tous d'accord qu'il existe 128 configurations de ponts possibles.
Pour chacune de ces configurations, il faut se poser la question : un chemin existe-t-il, oui ou non ?
Et il se trouve que sur les 128 cas possibles, il existe un chemin 92 fois (peu importe que le chemin soit de longueur 2, 3 ou 4, et fasses des aller-retours ou non).
bonjour jamo
tu indiques qu' "il existe un chemin 92 fois"
Le souci est, illustré sur mon exemple ci-dessus, que les deux configurations A-C-E ou B-C-E qui participent bien aux 92 recensées ne sont pas des chemins !
Je me demande si ce n'est pas la réflexion de castoriginal ...
Rudy
bonjour,
>>rudy il me semble que l'on ne doive considérer que les chemins passant par 2ponts ou bien 3 ponts dont Dle texte ne le précise pas mais c'est ce que je comprends
ABCE est à exclure ( je pense que castoriginal veut le rejeter) ,GFEC aussi
ACE et BCE ne sont pas à prendre en compte ni ADC , BDC ... ce ne sont pas des chemins qui permettent le passage N<->S
il fait bien chaud pour y réfléchir un peu plus,bon courage
bonjour veleda
d'accord avec toi pour ne considérer que des chemns à deux ou trois ponts dont D, principe sur lequel le décompte des 92 cas favorables s'appuie
Néanmoins, dans ces 92 cas se trouvent justement les cas où ACE et BCE (qui permettent assurément le passage Sud-Nord) ne sont pas détruits...
Nota : Je ne suis pas sûr que tu utilises la dénomination des ponts de manpower, castoriginal où la mienne rappelée dans mon message de ce matin 10h38
Ce qui me fait abonder dans le sens de castoriginal c'est que, justement, ACE et BCE ne sont pas des chemins, au sens Eulériens du terme
Rudy
Je vais prendre un exemple plus simple, pour expliquer comment je vois les choses.
Prenons 3 pièces de monnaies, qu'on nomme A, B et C (on peut donc les distinguer).
On les jette en l'air, et chaque pièce peut donc présenter 2 valeurs : pile ou face.
Imaginons un jeu dans lequel, pour gagner, il faut que les pièces A et B présentent toutes les deux le côté face. Peu importe la pièce C.
En tout, nous sommes bien d'accord qu'il y a 23=8 possibilités.
Prenons p pour pile et f pour face.
A B C
p p p
p p f
p f p
p f f
f p p
f p f
f f p
f f f
Sur les 8 possibilités, on en trouve 2 de favorables (les 2 derniers), d'où une probabilité de : 2/8=1/4=0,25.
D'ailleurs, on retrouve bien la même chose en ne jouant qu'avec les 2 pièces A et B : 4 possibilités, une seule gagnante, d'où une probabilité de 1/4.
Pour l'histoire des ponts, c'est la même chose pour moi. Considérons les ponts A, C et E. Le pont A ne sert à rien, étant donné que seuls les ponts C et E suffisent à établir le chemin. Mais dans l'énumération des cas favorables, on est bien obligé de considérer les deux possibilités pour le pont A, qu'il soit ouvert ou non, ce qui apporte donc à la fois 2 issues dans le "nombre de cas favorables" et dans le "nombre de cas total".
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :