L’essai remplacera t’il la théorie ?

[invitedf3b174e]

Bonjour
Je jette 4 points au sol et je vois s’ils forment un triangle avec un point à l’intérieur du triangle.
Durant les deux premiers essais j’ai trouvé une fois sur 2 un triangle avec un point à l’intérieur du triangle (voir le coté gauche de la photo)
4 points.jpg

J’ai refais l’expérience plusieurs fois est j’ai remarqué que le nombre de fois que les 4 points forment un triangle avec un point à l’intérieur est inferieur au nombre de fois ne forment pas de triangle avec un point à l’intérieur
Le calcul théorique de la probabilité que quatre points forment un triangle avec point à l’intérieur n’est disponible pour le moment (j’ai lu ca dans la revue « science et avenir » des années 1990) pour

La question :
Si on prend 4 petits objets et on fait des essais des centaines de fois en trouve un résultat inferieur à 0,5 (par exemple 0,4)
Si on augmente le nombre des essais à des milliers ou des millions et on trouve un résultat semble. Pourra t’on conclure que définitivement la probabilité que 4 points forment un triangle avec point à l’intérieur est strictement inferieur à 0.5

Je vous invite à réaliser les essais, c’est simple, prenez n’importe qu’il objet (4 pièces de monnaies par exemple)
-----

[invitef29758b5]

Salut

Pourra t’on conclure que définitivement la probabilité que 4 points forment un triangle avec point à l’intérieur est strictement inferieur à 0.5

NON , car il y a un biais dans ton expérience .
Tu vise plus ou moins une zone et tes points ne sont donc pas distribués au hasard .
Il sont centrés vers le milieu de ta feuille .
Leur répartition suit une loi normale .

[invitedf3b174e]

Salut
NON , car il y a un biais dans ton expérience .
Tu vise plus ou moins une zone et tes points ne sont donc pas distribués au hasard .
Il sont centrés vers le milieu de ta feuille .
Leur répartition suit une loi normale .

Bonjour

C’est bon,
Pour un espace restreint (une feuille) et une répartition qui suit une loi normale, qu’elle est la probabilité que 4 points forment un triangle avec un point à l’intérieur du triangle ?

[invite75a796c1]

Salut,

on pourrait commencer par des variantes :

*** fixer un centre de cercle, prendre un rayon aléatoire et calculer la proba pour que le jeton soit dans le cercle ... avant d'intégrer sur le rayon aux longueurs possibles équiprobables.

*** on jette 3 jetons rouges,
- en considérant que tous ces lancers de 3 sont équiprobables, quelle est la probabilité pour que le 4e jeton noir soit contenu dans le 1er triangle aux sommets rouges ( question bien différente de l'originale )

et enfin
* se demander quelles sont les symétries de l'énumération que nous ferons pour calculer les probas si les 4 jetons étaient indifférenciés et quand les figures peuvent vérifier plus d'une fois la propriété complète ( 4 points distincts font 4 triangles ).
* Statuer sur la probabilité d'avoir un point sur une ligne d'un plan ( normalement, c'est 0 pour un point mais ici c'est un jeton )


Quelle est déjà la surface d'un triangle quelconque sachant ses coordonnées ? calcul trop compliqué pour ce qu'on veut en faire. Il faudrait trouver une formulation basée sur d'autres propriétés du triangle, avec des arrières pensées circulaires. Je parie, que comme pour le cercle, qu'il ne restera que le facteur d'échelle.

bon, il semble y avoir un peu de travail pour trouver le piège annoncé et sa difficulté.

Si le maitre des énigmes veut mener la danse, on pourrait bien s'amuser en visant un résultat partiel ( puisque ce serait insoluble au moins dans le cas général selon Sc. & Av. )

[A voir en vidéo sur Futura]

[obi76]

Bonjour,

un petit Monte-Carlo (je sais, c'est moche) pour répondre au problème : je trouve 0.50925... avec 10^8 tirages (ça tourne en une vingtaine de secondes).

Ci joint le code :

program MC_obi76
 implicit none
 integer :: nb_tirage = 100000000, i, nbtri
 real, dimension(2) :: X1, X2, X3, X4
 logical :: istri
 do i = 1, nb_tirage
   if (modulo(i, 10000)==0) write(*,*) i, '/', nb_tirage, ':', real(nbtri)/real(i)
   call random_number(X1)
   call random_number(X2)
   call random_number(X3)
   call random_number(X4)
   call triangle(X1, X2, X3, X4, istri)
   if (istri) nbtri = nbtri + 1
 enddo
 write(*,*) real(nbtri)/real(nb_tirage)

 contains
 subroutine triangle(X1t, X2t, X3t, X4t, istri)
  logical :: istri
  real, dimension(2) :: X1t, X2t, X3t, X4t
  istri = .false.
  if (in_triangle(X1t,X2t,X3t,X4t)) istri = .true.
  if (in_triangle(X1t,X2t,X4t,X3t)) istri = .true.
  if (in_triangle(X1t,X4t,X3t,X2t)) istri = .true.
  if (in_triangle(X4t,X2t,X3t,X1t)) istri = .true.
 end subroutine

 function in_triangle(X1p,X2p,X3p,X4p)
  implicit none
  Logical  :: in_triangle
  real, dimension(2) :: X1p, X2p, X3p, X4p
  real :: pvabac,pvabam,pvbcba,pvbcbm,pvcacb,pvcacm
!-
  pvabac = (X2p(1)-X1p(1))*(X3p(2)-X1p(2))-(X2p(2)-X1p(2))*(X3p(1)-X1p(1))
  pvabam = (X2p(1)-X1p(1))*(X4p(2)-X1p(2))-(X2p(2)-X1p(2))*(X4p(1)-X1p(1))
  pvbcba = (X3p(1)-X2p(1))*(X1p(2)-X3p(2))-(X3p(2)-X2p(2))*(X1p(1)-X2p(1))
  pvbcbm = (X3p(1)-X2p(1))*(X4p(2)-X2p(2))-(X3p(2)-X2p(2))*(X4p(1)-X2p(1))
  pvcacb = (X1p(1)-X3p(1))*(X2p(2)-X1p(2))-(X1p(2)-X3p(2))*(X2p(1)-X3p(1))
  pvcacm = (X1p(1)-X3p(1))*(X4p(2)-X3p(2))-(X1p(2)-X3p(2))*(X4p(1)-X3p(1))
  if ((pvabac*pvabam >= 0.0).and.(pvbcba*pvbcbm >= 0.0).and.         &
                                                 (pvcacb*pvcacm >= 0.0)) then
    in_triangle = .TRUE.
  else
    in_triangle = .FALSE.
  endif
 end function in_triangle
end program

[invite75a796c1]

Bonjour Obi,

merci pour le calcul !

J'ai perdu mon mess en voulant inclure une image et impossible de le restaurer en entier. Je reprendrai ce soir.

Le cas facile est le plan avec sa proba de 1/2 ; il faut ignorer l'intérieur qui est fini et rapporter le reste à un camembert.

Avec un support cercle, la limite tend vers 1/2 quand le facteur d'échelle ( surface du triangle / surface du cercle ) tend vers 0.

Avec un support rectangle, la limite est la même mais la courbe est différente. Elle dépend fortement du rapport longueur/largeur du rectangle avec des formules très moches, du fait de la perte de symétries. Même avec un carré, plusieurs symétries sont perdues.

Ce soir, il me faudra déterminer quelle est la distribution des surfaces quand on choisit 3 points au hasard.

[obi76]

Je précise : il sagit de 4 points dont les coordonnées sont uniformément réparties par direction entre 0 et 1.

[invite75a796c1]

4thpoint.png

Contrairement au programme ou à mon message d'hier, j'ai préféré calculer directement le cas 3 points + 1 en additionnant les 4 surfaces permettant au 4e point de finir un quadruplet solution.

( sans cette précision , mon message précédent est inintelligible )

[mach3]

c'est rigolo comme problème. A l'arrache comme ça, je trouve que pour un triangle donné, si je place un 4e point au hasard n'importe où, j'ai vraisemblablement une chance sur deux de former un triangle avec un point à l'intérieur. Il est à noter qu'il y a deux situations où cela arrive :
-le point au hasard tombe dans le triangle déjà existant : probabilité qui tend vers 0 car l'aire du triangle est négligeable devant l'aire infinie à disposition (on suppose qu'on place les points où l'on veut dans R²)
-le point au hasard forme un sommet du triangle final et l'un des points du triangle initial se retrouve à l'intérieur du triangle final, c'est là qu'à vu de nez la proba tend vers 1/2. On peut en fait découper l'extérieur du triangle en six secteurs, dont trois démarrent des sommets, avec des angles égaux au angles du triangle, donc avec une somme égale à (c'est ceux dans lesquels le point doit tomber pour obtenir un triangle avec un point dedans, en vert sur le schéma). Les trois autres secteurs démarrent des cotés du triangle (en orange sur le schéma), leurs angles sont également égaux aux angle du triangle et la somme fait également . Les deux sommes d'angles étant égale à , ces deux ensembles de secteurs se partagent équitablement le plan quand on fait tendre la taille du triangle vers 0.

triangle.PNG

Il s'agit par contre d'une probabilité conditionnelle (la proba d'avoir un triangle avec un point dedans, sachant qu'on a déjà un triangle donné) et je suis trop rouillé en proba pour l'exploiter. Toujours est-il qu'il me parait évident que cette probabilité conditionnelle est égale à 1/2 si on considère un plan illimité (R²) pour placer les points. Si on considère une surface finie en revanche, la proba d'avoir un point dans le triangle doit augmenter avec le rapport aire du triangle/aire de la surface finie.

m@ch3

PS : doublé par mike, deux fois

[invite75a796c1]

@mach3

C'est plus facile de commencer par la solution dans un cercle avant de passer au rectangle, pas tant pour le calcul du 4e point que pour l'intégration qui suit pour calculer la proba pour un tirage de 4

Il y a quand un problème dans notre approche car elle n'est pas portable si on veut traiter de la même façon un polygone dans un espace de dimension supérieure à la place du triangle dans un plan.

[mach3]

C'est plus facile de commencer par la solution dans un cercle avant de passer au rectangle, pas tant pour le calcul du 4e point que pour l'intégration qui suit pour calculer la proba pour un tirage de 4

oui, mais je n'étais pas d'une logique d'intégration, mais d'estimation d'aire à la serpe. Si on considère R², alors on peut rendre le triangle arbitrairement petit et alors la proba est clairement de 1/2, il suffit de prendre 3 droites qui s'intersectent en un point (un triangle dégénéré dont les longueurs de coté tendent vers 0), on voit que le plan est partitionné en deux surfaces composées (la verte et la orange) égales.
Cela devient assez bizarre quand je poursuis le raisonnement (je ne sais pas si je vais être très clair car n'ai pas le temps de faire un schéma) : si on décale ensuite l'une des droites légèrement (pour faire "pousser" le triangle), on fait apparaitre une bande où les propriétés s'inversent, on voit qu'une des sections orange est légèrement grignotée (elle devient verte, c'est le triangle) et que les deux sections vertes adjacentes sont fortement grignotées (elles deviennent orange). La proba devient alors inférieur à 1/2 car on a converti plus de vert en orange que de orange en vert... La bande sur laquelle l'inversion se produit possède une surface infinie, comme R², du coup je ne sais pas trop comment m'en sortir. Intuitivement pour moi la contribution de cette bande devrait être négligeable devant la surface de R², mais comme elles sont infinies toutes les deux c'est un problème d'infini plus petit qu'un autre que je ne maitrise absolument pas... La bande est finie en largeur, pas en longueur, alors que R² est infini en largeur comme en longueur, donc j'intuite quand même que la contribution de la bande est très petite. La proba doit tendre vers 1/2 mais est strictement inférieure.

Je reviens sur ton approche intégrale, en faisant des cercles concentriques. Il est clair que si on prend deux cercles, de rayon r et r+dr, centrés sur le centre du cercle circonscrit, alors la proba (qu'un point qui serait dedans mène à la situation "un point dans un triangle") tend vers 1/2 quand r tend vers l'infini. Elle est cependant quasi-nulle quand r=R le rayon du cercle circonscrit. La même démarche est difficile à mener pour r<R car elle dépend totalement de la forme du triangle : le centre du cercle circonscrit pouvant être à l'extérieur ou à l'intérieur du triangle. La proba dans ce cercle circonscrit va de 0.827 (triangle équilatéral) à 0 (triangle "plat" avec un angle qui tend vers ). La contribution du contenu de ce cercle circonscrit semble cependant négligeable si on considère qu'on est dans R². On aurait donc bien quelque chose qui tend vers 1/2 mais probablement strictement inférieur.

Je suis étonné que ce problème ne possède pas de solution. Où alors son énoncé est incomplet.

m@ch3

[obi76]

Et étonnamment, mon 0.509 a l'air convergé, donc ça tendrait vers un peu plus d'un demi...

[mach3]

wai, mais tu es sur une surface finie (coordonnées dans l'intervalle 0-1) avec un nombre fini de points (coordonnées tirées au hasard dans un ensemble discontinu de valeur, un flottant n'est pas un réel...), ça a peut-être un impact. Autre chose aussi, ce n'est peut-être pas la même proba (conditionnelle tout ça...).

m@ch3

[obi76]

Le seul biais c'est effectivement l'espace fini. Pour le flottant ça aurait un biais potentiel de l'ordre de 10-16, ce qui est loin du 10-5 que j'ai obtenu.

EDIT : je confirme, en 32 ou 64 bits, j'obtiens la meme chose.

[invite75a796c1]

Salut !

il ne s'agit pas vraiment de probabilité conditionnelle ; nous essayons de modéliser ce qui se passe au moment d'ajouter le 4e jeton, étant entendu que nous "saurions" intégrer ce résultat "sur" tous les triplets initiaux, qui sont aléatoires avec des distributions uniformes.

je vois un ordre croissant de difficultés avec ces variantes :
- support plan
- support cercle et trois points appartenant à un cercle de même centre que le support
- support cercle
- support carré
- support rectangle

Selon moi, donc à moins qu'un vif matheux ne trouve une super astuce, les 2 derniers cas sont lourds et pas nécessairement intéressants. Les 2 premiers cas sont faciles à traiter rigoureusement. La difficulté ( modérée ) tient au passage de 2 en 3.

Ceci dit, je ne vois pas non plus pourquoi l'une quelconque de ces variantes en dimension 2 avec 4 points serait NP-difficile ou pire.
Une idée de la difficulté cachée ?

[invite23cdddab]

Ce problème s'appelle le "problème des 4 points" de Sylvester

Et effectivement, le résultat dépend fortement de la géométrie du domaine

http://mathworld.wolfram.com/Sylvest...ntProblem.html

[obi76]

Ce problème s'appelle le "problème des 4 points" de Sylvester

Et effectivement, le résultat dépend fortement de la géométrie du domaine

http://mathworld.wolfram.com/Sylvest...ntProblem.html

Merci beaucoup !

Par contre il faudra que l'on m'explique pourquoi je trouve 0.5 et pas 0.66[...]...

[invite23cdddab]

Peut être une erreur dans le code qui dit si les points sont en position convexe?

[invite75a796c1]

L'algo pourrait être un tout petit peu optimisé ; mais pour quelques essais, pas la peine de faire mieux , il n'y a rien à dire ... A tout hasard, je le reprendrai ce soir en C ou en javascript si c'est très simple ( facile à tester pour tous )

Auriez vous trouvé quelque chose ?

Un bug dans le résultat officieux sur Wolfam pourrait sauver l'énigme du début de l'été ! est ce un espoir raisonnable ?

Ou alors, le challenge serait de trouver des calculs qui mènent aux mêmes résultats avec des points de vérification informatique.

Ou encore de se lancer dans le support rectangle qui n'est pas traité sur la page.

[obi76]

Peut être une erreur dans le code qui dit si les points sont en position convexe?

Je me suis posé la question, mais c'est un bout de code que j'ai utilisé et réutilisé assez souvent qui marche bien pour des polygones quelconques. La seule erreur potentielle que je voit est l'ordre des produits vectoriels que j'utilise pour voir si c'est dedans ou dehors. Je regarderai ça à ete reposée.

Quant à l'optim oui c'est largement optimisable, c'est juste un bout de code fait en 5 minutes pour ce cas précis, pas la peine d'y passer 3 jours...

[invite75a796c1]

Salut,

selon la page wolfam en lien , on devrait trouver 25/36 pour le carré ( 0.69444 ).
J'ai implémenté plusieurs algorithmes trouvés sur le web ( http://stackoverflow.com/questions/2...-a-2d-triangle ) et les apparemment-pas-buggués , c'est à dire ceux du haut de page , me renvoient 1 - 25/36 au lieu de 25/36.

Il y a un bug quelque part, surement dans les algos car 25/36 ( qui est > 1/2 ) est très crédible au contraire de son complément.

@Obi :
J'ai cherché l'erreur mais ne l'ai pas trouvée. J'ai testé un similaire qui a donné le même résultat. Et un autre qui est censé fonctionner sur la même base, qui lui renvoie 0.590. Je recommencerai un débug après cette fois avoir accordé les noms de variables, ce sera plus facile.

Si je n'arrive pas à retrouver ce 25/36 , il faudra revenir à la géométrie, surement par les angles pour la portabilité en cas d'extension de l' "énigme". Ce n'est pas la mer à boire mais j'avais souhaité ne pas réécrire du code disponible, par principe pratique ...

SVP : une question à propos de polygones : étant donnés n points, faut il relier chaque point aux 2 plus proches ou bien tous les chemins fermés, passant une seule fois par chaque point, sont acceptables ?

[invite75a796c1]

Désolé !
auto-correction : non, wolfam rend bien 25/36 pour la probabilité d'avoir un quadrilatère convexe et il n'y a donc pas de résultats trop souvent complémentaires.

Mais du coup j'ai perdu mes repères numériques. J'attendais plus de 1/2, comme quoi il y a des intuitions trompeuses parfois ...

@Obi

comme ça, je retrouve à un poil près le même résultat.

  pvabac = (X2p(1)-X1p(1))*(X3p(2)-X1p(2))-(X2p(2)-X1p(2))*(X3p(1)-X1p(1))
  pvabam = (X2p(1)-X1p(1))*(X4p(2)-X1p(2))-(X2p(2)-X1p(2))*(X4p(1)-X1p(1))
  pvbcba = (X3p(1)-X2p(1))*(X1p(2)-X3p(2))-(X3p(2)-X2p(2))*(X1p(1)-X3p(1))
  pvbcbm = (X3p(1)-X2p(1))*(X4p(2)-X2p(2))-(X3p(2)-X2p(2))*(X4p(1)-X2p(1))
  pvcacb = (X1p(1)-X3p(1))*(X2p(2)-X1p(2))-(X1p(2)-X3p(2))*(X2p(1)-X1p(1))
  pvcacm = (X1p(1)-X3p(1))*(X4p(2)-X3p(2))-(X1p(2)-X3p(2))*(X4p(1)-X3p(1))

le test avec 10 millions donne :

ref carré : 0,30555
go with :1000000 tests
proba :0.30613

[invitedf3b174e]

Bonjour

J’aimerai partager avec vous l’essai suivant :
Au lieu de lancer à chaque fois 4 points et voir le résultat avant de procéder au deuxième lancement, je préfère lancer 45 points une seul fois et voir les résultats 4 points par 4.

triangle avec point à interieur.jpg

J’ai obtenu les 45 points à l’aide de la formule ALEATOIRE de EXCEL.

Je numérote les points de 1 à 45, et je les examine 4 par 4.

Pour les points 1, 2, 3, 4 et 5 j’ai obtenu :
1234 = non
1235 = non
1245 = oui (point 4 à l’intérieur du triangle 125)
2345 = oui (point 4 à l’intérieur du triangle 235)

Soit une proba = 0.5

Je vais continuer pendant qq jours, qu’en pensez-vous du résultat final ?

[invite75a796c1]

45 points par groupes de 4, ça fait presque 150.000

Apparemment, ca n'introduit pas de biais mais il faudrait voir ça en détail.

Ca ne vaut pas la simu d'Obi qui fait la même chose efficacement ...
Pour un carré 100x100 vous devez trouver : 30.6%

[invitedf3b174e]

45 points par groupes de 4, ça fait presque 150.000

Apparemment, ca n'introduit pas de biais mais il faudrait voir ça en détail.

Ca ne vaut pas la simu d'Obi qui fait la même chose efficacement ...
Pour un carré 100x100 vous devez trouver : 30.6%

Bonjour

150000, en faisant 1000 examens visuels par jour il faudra 5 mois.

Je réduit le nombre à 20 points

[invitedf3b174e]

bonjour

triangle avec point à interieur 20.jpg

Pour les points 13, 14, 15, 16 et 17 il y a 10 possibilités et j’obtiens :
13-14-15-16 non
13-14-15-17 non
13-14-15-18 oui (15 au milieu)
13-14-16-17 oui (16 au milieu)
13-14-16-18 oui (15 au milieu)
13-14-17-18 oui (15 au milieu)
13-15-16-17 oui (16 au milieu)
13-15-16-18 oui (16 au milieu)
13-15-17-18 non
13-16-17-18 non
Soit P =0.6

Mais pour les points 8,9,10,11 et 12 j’obtiens P=0

La je fais la remarque que pour les triangles sans point à l’intérieur on peut obtenir 100 %
Mais pour des triangles avec un point à l’intérieur le max qu’on peut obtenir et 60%

Donc la probabilité d’obtenir un triangle avec un point à l’intérieur est inférieure à celle d’obtenir un triangle sans point à l’intérieur

[obi76]

Re,

@Obi

comme ça, je retrouve à un poil près le même résultat.

  pvabac = (X2p(1)-X1p(1))*(X3p(2)-X1p(2))-(X2p(2)-X1p(2))*(X3p(1)-X1p(1))
  pvabam = (X2p(1)-X1p(1))*(X4p(2)-X1p(2))-(X2p(2)-X1p(2))*(X4p(1)-X1p(1))
  pvbcba = (X3p(1)-X2p(1))*(X1p(2)-X3p(2))-(X3p(2)-X2p(2))*(X1p(1)-X3p(1))
  pvbcbm = (X3p(1)-X2p(1))*(X4p(2)-X2p(2))-(X3p(2)-X2p(2))*(X4p(1)-X2p(1))
  pvcacb = (X1p(1)-X3p(1))*(X2p(2)-X1p(2))-(X1p(2)-X3p(2))*(X2p(1)-X1p(1))
  pvcacm = (X1p(1)-X3p(1))*(X4p(2)-X3p(2))-(X1p(2)-X3p(2))*(X4p(1)-X3p(1))

nickel, merci de la correction !

[mach3]

Bonjour

150000, en faisant 1000 examens visuels par jour il faudra 5 mois.

allons, il y a bien plus simple et plus rapide que d'effectuer un examen visuel. Excel peut déterminer lui-même si 4 points forment un quadrilatère convexe ou non, il suffit de coder la bonne formule... Utilisez un ordinateur et ensuite faire un examen visuel, il y a comme un anachronisme là-dedans...

m@ch3

[obi76]

Des examens, on vient de vous en faire 100 millions, de quoi vous occuper toute votre vie (et meme les suivantes ), que vous faut-il de plus ?

[invite9dc7b526]

Une mathématicienne dont j'ai oublié le nom m'avait raconté qu'elle avait été l'élève de Fréchet, et que Fréchet s'intéressait à la loi de la surface entourée par une courbe aléatoire de longueur fixée. A l'époque il n'y avait pas d'ordinateurs et elle a dû lancer par une fenêtre des ficelles attachées en boucle, puis aller avec un calque quadrillé mesurer la surface entourée par la ficelle. Tout ça pour dire que l'expérimentation d'iharmed n'est pas sans précédents.