Enigmo 116 : Tempête sur les sept ponts de Königsberg

Posté par jamo jamo

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 : , si les grands esprits qui se rencontrent sur le forum des énigmes veulent bien s'y pencher ...

Posté par 13or 13or

Salut jamo,
Réponse : 23/32

Merci pour l'énigmo

Posté par Daniel62 Daniel62

Bonjour Jamo,

ma réponse:

    


il y a 7 ponts et 2 possibilités par pont soit 2⁷ = 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

Posté par lolo248 lolo248

la probabilité de pouvoir encore aller du sud au nord de la ville après la tempête est

Posté par Nofutur2 Nofutur2

Je trouve une probabilité de 92/128 soit 23/32 que le passage entre A et B soit possible.

Posté par castoriginal castoriginal

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

Posté par manpower manpower

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)}

Posté par torio torio

Prob = 92/128 = 23/32

A+
Torio

Posté par plumemeteore plumemeteore

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.

Posté par maher_91 maher_91

bonjour,
On a 9 chances sur 2⁹ (d'ou la probabilité est de ) pour qu'on puisse passer de A vers B (ou de B vers A).
merci.

Posté par nate_92 nate_92

bonjour je suis nouveau,j'espere que j'ai fait mouche:1/4*5/9+1/8*4/9=7/36

Posté par evariste evariste

23/32

Posté par Nyavlys Nyavlys

je trouve 92/128 ou encore 23/32
merci pour l'énigme

Posté par LeDino LeDino

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.

Posté par MatheuxMatou MatheuxMatou

Bonjour

Grâce à un arbre, je dirais que la probabilité de pouvoir encore joindre A et B vaut 23/32

MM

Posté par rezoons rezoons

Bonjour ,
je trouve de deux manières differentes 23/32.

Posté par yoyodada yoyodada

Salut Jamo

Je trouve une probabilité de 23/32 , en espérant ne pas m'être trompé !
Merci pour l'énigme !

Posté par Rudi Rudi

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

Posté par daxtero daxtero

92/128

Posté par veleda veleda

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

Posté par maher_91 maher_91


... on a plutôt 160 chances sur 512 ... bonjour le

Posté par gloubi gloubi

Bonjour jamo,

La probabilité de pouvoir aller du sud au nord de Königsberg après la tempète
est 0.71875.  

Posté par thiblepri thiblepri

Bonjour,
La valeur de cette probabilité est 23/32 soit 0,71875 .

Posté par pythamede pythamede

89/128 soit 0,6953125

Posté par hypatie hypatie

Bonjour,

Ma réponse est 23/32, soit 0,71875.

J'ai trouvé 2⁷=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.

Posté par matovitch matovitch

Bonjour !

Je trouve (vite fait donc sans doute un poisson).

Posté par dhalte dhalte

Bonjour

23/32

Posté par carpediem carpediem

salut

la probabilité est 67/128 = 67/2⁷

Posté par carpediem carpediem

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)=C₇^k * (1/2)^k * (1/2)^7-k = C(k,7) * (1/2)⁷
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

Posté par carpediem carpediem

REM: un résultat proche de 1/2 parait raisonnable....

Posté par Eric1 Eric1

A l'aide d'un tableau et des "et" et des "ou", je trouve:
23/32

Posté par engine engine

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

Posté par tudul tudul

128 possibilités, 92 ou on peut aller de A vers B ( dénombrées via excell )

Donc P= 92/128

Posté par jolabeille jolabeille

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 ,

Posté par dpi dpi

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

Posté par juggernauth juggernauth

sur 128 possibiltés , il y a 36 qui ne collent pas,
ca fait une probabilité de 1 - 36/128
soit 0. 71875

Posté par tsoubi tsoubi

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

Posté par tonton tonton

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)³ + (1/2)³ + (1/2)⁴ + (1/2)⁴
          = 3/2³

       p = 1 - q
          = (2³ - 3)/2³ = 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

Posté par 1emeu 1emeu

Bonjour,

voici ma proposition :
23/32=0.71875

Merci pour l'énigme

1emeu

Posté par gagou2713 gagou2713

La probabilité d'aller du nord au sud après la tempête est : P=7/36

Posté par jamo jamo

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é !

Posté par castoriginal castoriginal

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

Posté par castoriginal castoriginal

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

Posté par Rudi Rudi

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

Posté par jamo jamo

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

Posté par Rudi Rudi

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

Posté par veleda veleda

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

Posté par Rudi Rudi

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

Posté par jamo jamo

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 2³=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".

Posté par jamo jamo



Pour moi, le "chemin" ACE, c'est-à-dire quand les ponts A, C et E sont encore opérationnels, est à considérer dans les cas favorables, car dans ce cas, on peut joindre les 2 rives, même si le pont A ne sert à rien.