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 - 27-06-2015 22:12:26

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

gâtezu 100

Bonjour à tous smile

Sur P2T la coutume est de fêter les centaines , les milliers …

Personnellement j’ai du mal à conserver un problème du millénaire pour le sortir à la grande occasion , quant à prévoir ce qui peut intéresser ou ennuyer les amateurs de gâteaux ...

Pour ce 100ème j’ai fait confiance à mon pâtissier smile

Il a placé au hasard 50 points sur chaque bord d’une bande de pâte ( on peut supposer que deux points ne sont jamais pas pile poil en face ) . Il a ensuite relié de façon biunivoque ( et toujours au hasard ) tout point de chaque bord à l’un de ses vis à vis par une ligne de crème Chantilly .

Une illustration avec 10 points au lieu de 100 :

http://www.prise2tete.fr/upload/Vasimolo-gateau100.png

Il y a ( en rouge ) une ligne de centaine ( de dizaine pour le dessin ) , c’est-à-dire une ligne Chantilly reliant les cents points du gâteau .

Quelle est la probabilité qu’une telle ligne existe ?

Amusez-vous bien smile

Vasimolo



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 28-06-2015 02:28:16

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3319

Gâteau 1100

J'espère que tu ne fais pas parti des correcteurs des oraux de mes concours lol

Juste pour voir si j'ai bien tout compris pour trois points de chaque côté je dirai 4/9.


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #3 - 28-06-2015 12:33:41

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

gâteay 100

Je n'ai pas le même résultat que toi , mais comme tu ne donnes pas ta stratégie je ne peux pas te dire s'il y a une erreur de méthode ou si le problème est mal compris .

Vasimolo

PS : Si tu ne passes pas le brevet des collèges tu n'a pas d’inquiétude à avoir lollollol

 #4 - 28-06-2015 12:40:05

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

Gâtteau 100

Une petite question : celui du haut est invalide, mais celui du bas ?
http://www.prise2tete.fr/upload/gwen27-g100question1.JPG

 #5 - 28-06-2015 13:03:12

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

Gâteauu 100

Excellente question Gwen smile

L'idée initiale était de passer d'un bord à l'autre en passant par la ligne rouge mais pourquoi ne pas accepter le chemin que tu proposes ?

http://www.prise2tete.fr/upload/Vasimolo-valide.png

Vasimolo

PS : Je n'ai pas de solution au problème initial et à fortiori à cette variante , si je suis débordé je lève le masque smile

 #6 - 28-06-2015 16:13:54

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

gâteai 100

Si c'est le problème avec un trait qui coupe tous les autres, c'est assez simple.
Si c'est "pas de réseaux indépendants" c'est bien plus difficile.

 #7 - 29-06-2015 09:02:29

halloduda
Professionnel de Prise2Tete
Enigmes résolues : 24
Messages : 479
Lieu: Ardèche

Gâteaau 100

@Vasimolo :
Veux-tu dire la probabilité d'existence d'un parcours sans lever la seringue ni ligne en double épaisseur, tel que celui-ci ?
http://www.prise2tete.fr/upload/halloduda-Sans-titre.jpg

 #8 - 29-06-2015 17:44:20

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

Gâteau 1000

@Halloduda : la chantilly doit relier en ligne droite deux points sur deux bords opposés ( pas de crème entre deux points d'un même bord ) .

Vasimolo

 #9 - 30-06-2015 09:29:56

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 401

gâreau 100

Bonjour,
D'après ce que j'ai compris, il faut trouver la probabilité que, pour chaque couple de points (situés sur un même côté ou non), il existe un chemin en chantilly qui les relie (cas n°2, défini en #16).

Pour 50 points de chaque côté, j'obtiens une probabilité de 95.955 %.
Voici un script en python3 qui calcule les valeurs de 1 à N (N est donné en paramètre). Le résultat est quasi instantané pour N=50, et il y a environ 6s de calcul pour N=1000.

Code:

import sys

N=int(sys.argv[1])

ok={}; facto={}; tot=1
# ok[k] : 
#    Nb de cas où l'ensemble des lignes est connexe
#    pour k couples de points.
# facto :
#    Dictionnaire de factorielles, pour ne pas les
#    recalculer.
# ko :
#    Variable intermédiaire comptabilisant les cas
#    à éliminer.
#    Pour k couples de points, on élimine les 
#    permutations constituées d'un bloc
#    connexe de moins de k lignes, suivi d'une
#    permutation quelconque des autres points.
for k in range(1,N+1):
   ko=0
   tot*=k; facto[k]=tot  
   for k1 in range(1, k): ko+=ok[k1]*facto[k-k1]
   ok[k]=tot-ko
   print("N= %3d ok= %7d ko= %7d tot= %7d %7.3f %%"%(k,ok[k],ko,tot,(ok[k]/tot)*100))

J'ai vérifié jusqu'à N=12 en simulant tous les cas possibles, mais le temps de calcul augmente très vite avec N (voir ci-dessous).

Édité : Ajout du script qui passe en revue toutes les positions possibles pour N donné
~3mn40s pour N=11
~49mn pour N=12

Code:

import sys
from itertools import permutations

N=int(sys.argv[1])

ko=tot=0
# permu :
#    permu va parcourir toutes les permutations des
#    nombres 0 à N-1.
#    permu[i] est le n° du point de la ligne du bas
#    relié au point n° i de la ligne du haut.
for permu in permutations(range(N),N):
 tot+=1
 jmax=-1
 for i in range(N-1):
  jmax=max(jmax,permu[i])
# jmax : n° du point le plus à droite de la ligne du bas
#        parmi tous les points reliés aux points 0 à i
#        de la ligne du haut (les numéros démarrent à 0).
#        Si jmax=i, on a un bloc isolé de i+1 lignes.
  if jmax==i: ko+=1; break
ok=tot-ko
print("N= %3d ok= %7d ko= %7d tot= %7d %7.3f %%"%(N,ok,ko,tot,(ok/tot*100)))

Édité : Ajout de commentaires dans les scripts

 #10 - 30-06-2015 09:55:34

halloduda
Professionnel de Prise2Tete
Enigmes résolues : 24
Messages : 479
Lieu: Ardèche

Gtâeau 100

rien compris à l'énoncé

 #11 - 30-06-2015 18:04:22

dbab3000
Professionnel de Prise2Tete
Enigmes résolues : 48
Messages : 110

Gâeau 100

Si j'ai bien compris le problème la ligne rouge est la ligne qui se croise avec tous les autres lignes.
On considère une ligne AB qui lie un point A de la partie supérieure avec un point B de la partie inférieure. La condition pour qu'une ligne AB soit une ligne rouge est que le nombre de points à droite de A soit égale au nombre points à gauche de B
et on doit lier ces points et vice versa.
Le placement des points n'est pas important, c'est les liaisons entre les points qui sont importantes.
Le nombre total de répartitions qu'on peut faire avec des liaisons est 50!=3,04140932×10⁶⁴
1)On commence en liant A le premier point à gauche dans la partie supérieure et B le premier point à droite dans la partie inférieure, il n'y a pas de points à gauche de A et à droite de B tous les autres points sont dans les autres côtés le nombre de répartitions qu'on peut avoir avec les liaisons des 98 points restants est 49!
2)On lie 2ème point A avec 2ème point B, le problème dans ce cas est qu'on va lier le premier point à gauche dans la partie supérieure et le premier point à droite dans la partie inférieure le deuxième cas est déjà considéré dans le premier cas.
3)On lie 3ème point A avec 3ème point B il y a 47 points à droite de A le nombre de répartitions pour ces points est 47! et il y a 2 points à gauche de A le nombre de répartition est 1 (on peut pas les lier les premiers entre eux donc on lie le premier avec le deuxième et le deuxième avec le premier). Le nombre de répartitions est 47!×1
On continue jusqu'à atteindre le 50ème point A.
On pose
Un le nombre de répartitions pour un point A d'ordre  n
Vn le nombre de répartitions qu'on peut avoir avec les liaisons des points qui se trouvent à droite de A
Wn le nombre de répartitions qu'on peut avoir avec les liaisons des points qui se trouvent à gauche de A
On a:
U₂=0
Un=Vn×Wn pour ∀n⋲N* tel que n≠2 et n≤50
Vn=(50−n)! ∀n⋲N* tel que n≤50
W₁=1
W₂=1
W₃=1
W(n+2)=nW(n+1)+(n−1)Wn ∀n⋲N* tel que n≠1 et n≠2 et n≤50
La probabilité P d'avoir une ligne rouge
[TeX]P=\sum_1^{50} Un \div50![/TeX]
PS:Pour les explications des relations je ne voulais pas l'écrire car ça va être trop long mais si tu veux je peux l'écrire dans mon prochain message.
Bonne soirée.

 #12 - 01-07-2015 20:23:55

louvyy
Amateur de Prise2Tete
Enigmes résolues : 13
Messages : 1

Gâteau 1000

1 chance sur 2500 :
on a que 4 façons de relier tous les points:
- "haut gauche" ---> "bas droit"
- "bas droit" ---> "haut gauche"
- "haut droit" ---> "bas gauche"
- "bas gauche" ---> "haut droit"
sur 10000 (100 points*100 points)
ce qui fait 4 chances sur 10000 donc 1 chance sur 2500

 #13 - 01-07-2015 22:07:55

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

hâteau 100

@Dbab :ton approche est la bonne mais tu peux faire bien plus simple .
@Louvyy : non smile

Vasimolo

 #14 - 02-07-2015 00:30:29

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

Gâteau 1000

Je tombe sur 1 chance sur  50

 #15 - 02-07-2015 07:27:54

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 401

Gteau 100

Dans mon message #9, j'ai supposé que l'on cherchait la probabilité que l'ensemble des lignes soit connexe.

Si le problème est d'obtenir au moins une grande diagonale (cas n°1, défini en #16), la probabilité est (pour N>1) :
( 2*(N-1)! - (N-2)! ) / N! = (2*N-3) / (N*(N-1))
et 100 % pour N=1.

La probabilité est de 3.959 % pour N=50

Édité : Orthographe

 #16 - 03-07-2015 01:24:02

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

Gâteau 1100

Bonsoir à tous , j'ai été un peu en dessous de tout pour ce gâteau ( disons que j'ai eu des activités annexes smile )

Je précise le(s) problème(s)  . On a 50 points sur chaque côté d'une bande et on relie chacun d'entre eux aléatoirement à l'un de ses vis-à-vis ( chaque point d'un bord étant relié à un unique point de l'autre bord ) .

Après il y a deux variantes smile

1°) Celle de mon pâtissier :

Pour un tracé donné , quelle est la probabilité de pouvoir relier chaque point par une ligne de Chantilly passant par la même ligne (rouge ) ?

http://www.prise2tete.fr/upload/Vasimolo-gateau100bis.png

2°) Celle de Gwen ( bien plus intéressante )

Pour le même tracé , quelle est la probabilité d'avoir un lien chantilly entre chacun des points donnés .

http://www.prise2tete.fr/upload/Vasimolo-gateau100ter.png

J'espère que tout est plus clair smile

J'aurai plus de temps pour répondre la semaine prochaine smile

Vasimolo

 #17 - 03-07-2015 06:46:14

scrablor
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 933

fâteau 100

Pour la 1, c'est p(A)+p(B)-p(A inter B) donc 1/50+1/50-1/(50*49).
Pour la 2, c'est une horreur... Pas de récurrence possible !


Celui qui fuit les casse-tête ne vaut pas un clou.

 #18 - 03-07-2015 08:26:01

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 401

Gâteau 1100

Voici un récapitulatif de ce que j'obtiens, pour N variant de 1 à 50 (voir mes messages #9 et #15) :

Code:

N=   1 proba_cas_1= 100.000 % proba_cas_2= 100.000 %
N=   2 proba_cas_1=  50.000 % proba_cas_2=  50.000 %
N=   3 proba_cas_1=  50.000 % proba_cas_2=  50.000 %
N=   4 proba_cas_1=  41.667 % proba_cas_2=  54.167 %
N=   5 proba_cas_1=  35.000 % proba_cas_2=  59.167 %
N=   6 proba_cas_1=  30.000 % proba_cas_2=  64.028 %
N=   7 proba_cas_1=  26.190 % proba_cas_2=  68.393 %
N=   8 proba_cas_1=  23.214 % proba_cas_2=  72.155 %
N=   9 proba_cas_1=  20.833 % proba_cas_2=  75.326 %
N=  10 proba_cas_1=  18.889 % proba_cas_2=  77.969 %
N=  11 proba_cas_1=  17.273 % proba_cas_2=  80.164 %
N=  12 proba_cas_1=  15.909 % proba_cas_2=  81.992 %
N=  13 proba_cas_1=  14.744 % proba_cas_2=  83.524 %
N=  14 proba_cas_1=  13.736 % proba_cas_2=  84.819 %
N=  15 proba_cas_1=  12.857 % proba_cas_2=  85.923 %
N=  16 proba_cas_1=  12.083 % proba_cas_2=  86.875 %
N=  17 proba_cas_1=  11.397 % proba_cas_2=  87.704 %
N=  18 proba_cas_1=  10.784 % proba_cas_2=  88.431 %
N=  19 proba_cas_1=  10.234 % proba_cas_2=  89.075 %
N=  20 proba_cas_1=   9.737 % proba_cas_2=  89.650 %
N=  21 proba_cas_1=   9.286 % proba_cas_2=  90.166 %
N=  22 proba_cas_1=   8.874 % proba_cas_2=  90.632 %
N=  23 proba_cas_1=   8.498 % proba_cas_2=  91.055 %
N=  24 proba_cas_1=   8.152 % proba_cas_2=  91.441 %
N=  25 proba_cas_1=   7.833 % proba_cas_2=  91.795 %
N=  26 proba_cas_1=   7.538 % proba_cas_2=  92.121 %
N=  27 proba_cas_1=   7.265 % proba_cas_2=  92.421 %
N=  28 proba_cas_1=   7.011 % proba_cas_2=  92.699 %
N=  29 proba_cas_1=   6.773 % proba_cas_2=  92.958 %
N=  30 proba_cas_1=   6.552 % proba_cas_2=  93.198 %
N=  31 proba_cas_1=   6.344 % proba_cas_2=  93.423 %
N=  32 proba_cas_1=   6.149 % proba_cas_2=  93.633 %
N=  33 proba_cas_1=   5.966 % proba_cas_2=  93.830 %
N=  34 proba_cas_1=   5.793 % proba_cas_2=  94.015 %
N=  35 proba_cas_1=   5.630 % proba_cas_2=  94.190 %
N=  36 proba_cas_1=   5.476 % proba_cas_2=  94.354 %
N=  37 proba_cas_1=   5.330 % proba_cas_2=  94.509 %
N=  38 proba_cas_1=   5.192 % proba_cas_2=  94.657 %
N=  39 proba_cas_1=   5.061 % proba_cas_2=  94.796 %
N=  40 proba_cas_1=   4.936 % proba_cas_2=  94.928 %
N=  41 proba_cas_1=   4.817 % proba_cas_2=  95.054 %
N=  42 proba_cas_1=   4.704 % proba_cas_2=  95.173 %
N=  43 proba_cas_1=   4.596 % proba_cas_2=  95.287 %
N=  44 proba_cas_1=   4.493 % proba_cas_2=  95.396 %
N=  45 proba_cas_1=   4.394 % proba_cas_2=  95.500 %
N=  46 proba_cas_1=   4.300 % proba_cas_2=  95.599 %
N=  47 proba_cas_1=   4.209 % proba_cas_2=  95.694 %
N=  48 proba_cas_1=   4.122 % proba_cas_2=  95.785 %
N=  49 proba_cas_1=   4.039 % proba_cas_2=  95.872 %
N=  50 proba_cas_1=   3.959 % proba_cas_2=  95.955 %

Pour le cas 1, j'ai le même résultat que scrablor en #17.

Ajouté :
Si ok(n) est le nombre de dispositions favorables avec n points sur chaque côté, la formule de récurrence utilisée pour le cas 2 est :

Code:

ok(1) = 1
ok(k) = k! - (Σ pour i=1→k-1)( ok(i) * (k-i)! )

 #19 - 04-07-2015 20:40:59

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3319

Gâtea u100

Enigmatus peut tu ajouter les commentaires sur tes programmes ?

Et vasimolo, moi j'avais compris qu'on cherchait la probabilité qu'il existe une ligne qui croise toutes les autres...

Shadock


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #20 - 04-07-2015 21:21:09

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2715
Lieu: Luxembourg

Gtâeau 100

Moi aussi non plus, je n'y étais pas du tout.

 #21 - 05-07-2015 08:25:49

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2955

Gâtea u100

Pour la question Gwen, il me semble que la solution est 1/e. En effet, pour un tel scénario, il faut et il suffit qu'il y ait désordre complet. Et cette proba a pour convergence rapide 1/e quand n grandit.

 #22 - 05-07-2015 09:06:19

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 401

gâteai 100

shadock #19 a écrit:

Enigmatus peut tu ajouter les commentaires sur tes programmes ?

J'ai ajouté des commentaires dans les scripts en #9.

 #23 - 05-07-2015 09:18:48

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 401

gâyeau 100

nodgim #21 a écrit:

il faut et il suffit qu'il y ait désordre complet

La condition ne semble ni nécessaire

Code:

1→4
2→2
3→3
4→1

ni suffisante

Code:

1→2
2→1
3→4
4→3

 #24 - 07-07-2015 23:20:21

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

âGteau 100

J'ai trouvé un peu de temps pour reprendre un peu de ce gâteau .

Il me semble qu'il manque des cas pour le problème initial . Par exemple dans le cas de deux fois cinq points , je trouve 43 configurations qui conviennent ( au lieu des 42 annoncées par le programme d'Enigmatus ou la formule de Scrablor ) .

Peut-être cette éventualité manque-t-elle à l'appel ?

http://www.prise2tete.fr/upload/Vasimolo-gateau100pb1.png

Vasimolo

 #25 - 08-07-2015 06:41:53

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 401

Gâtea u100

@Vasimolo #24 :
Il est normal que cette configuration n'apparaisse pas dans le cas n°1, car il n'y a pas de ligne diagonale.
Ou alors, le problème était qu'une ligne devait couper toutes les autres, et ce serait le cas n° 3. À confirmer…

Réponse rapide

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

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

Sujet Date Forum
23-09-2012 Enigmes Mathématiques
P2T
Gâteau 127 par Vasimolo
23-09-2016 Enigmes Mathématiques
P2T
Gâteau 43 par Vasimolo
05-11-2011 Enigmes Mathématiques
P2T
Gâteau 109 par Vasimolo
25-10-2015 Enigmes Mathématiques
P2T
Gâteau 93 par Vasimolo
14-02-2015 Enigmes Mathématiques
15-01-2012 Enigmes Mathématiques
P2T
Gâteau 89 par Vasimolo
17-01-2015 Enigmes Mathématiques
P2T
Gâteau 32 par Vasimolo
05-09-2010 Enigmes Mathématiques
P2T
Gâteau 101 par Vasimolo
10-07-2015 Enigmes Mathématiques
P2T
Gâteau 118 par Vasimolo
11-01-2016 Enigmes Mathématiques

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