Probabilmente è convesso

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

franco
Livello 8
Livello 8
Messaggi: 1172
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Probabilmente è convesso

Messaggio da franco »

Consideriamo il quadrato con i vertici di coordinate (1,1); (-1,1); (-1,-1); (1,-1) che è evidentemente suddiviso in 4 quadranti dagli assi cartesiani.
Nei quadranti NordEst, NordOvest, SudOvest e SudEst scelgo rispettivamente i punti casuali A, B, C e D.
È corretto affermare che il quadrilatero ABCD ha oltre il 90% di probabilità di essere convesso?

Da
www.diophante.fr
G1909
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

panurgo
Livello 9
Livello 9
Messaggi: 1330
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: Probabilmente è convesso

Messaggio da panurgo »

Le simulazioni dicono di sì: la dimostrazione è un'altra cosa...
il panurgo

Principio di Relatività: {\bb m} \not \right {\bb M} \ \Longleftrightarrow \ {\bb M} \not \right {\bb m}
"Se la montagna non va a Maometto, Maometto NON va alla montagna"

delfo52
Livello 9
Livello 9
Messaggi: 1486
Iscritto il: mer mag 25, 2005 4:19 pm
Località: bologna

Re: Probabilmente è convesso

Messaggio da delfo52 »

vogliamo accartocciarci sulla frase "scelgo casualmente"?
Come dato psicologico, credo che facendo scegliere a persone ignare, la percentuale sarebbe anche maggiore. Per avere forme concave, almeno un paio di punti devono essere piuttosto "eccentrici"; e chi deve scegliere a caso, tende a stare meno "estremo". Con un estrattore casuale , in teoria, non dovrebbe accadere
Enrico

panurgo
Livello 9
Livello 9
Messaggi: 1330
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: Probabilmente è convesso

Messaggio da panurgo »

panurgo ha scritto:
mer set 02, 2020 12:41 pm
Le simulazioni dicono di sì: la dimostrazione è un'altra cosa...
Simulazioni fatte, come d'uso, campionando da una distribuzione uniforme: con altre distribuzioni le cose possono cambiare...
il panurgo

Principio di Relatività: {\bb m} \not \right {\bb M} \ \Longleftrightarrow \ {\bb M} \not \right {\bb m}
"Se la montagna non va a Maometto, Maometto NON va alla montagna"

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1188
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Probabilmente è convesso

Messaggio da Gianfranco »

delfo52 ha scritto:
mer set 02, 2020 8:41 pm
vogliamo accartocciarci sulla frase "scelgo casualmente"?
Come dato psicologico, credo che facendo scegliere a persone ignare, la percentuale sarebbe anche maggiore. Per avere forme concave, almeno un paio di punti devono essere piuttosto "eccentrici"; e chi deve scegliere a caso, tende a stare meno "estremo". Con un estrattore casuale , in teoria, non dovrebbe accadere
Ipotesi interessante.
Chiedo agli esperti se c'è un nesso con la definizione soggettivistica di probabilità di De Finetti.
Nel frattempo, per mio divertimento personale, ho scritto un programmino che disegna 100 quadrilateri alla volta in nero i convessi e in rosso i concavi.
Ho detto 100, ma il numero, memorizzato nella variabile "cont" può variare da 1 a quanti volete.
Alcuni sembrano triangoli, ma sono tutti(?) quadrilateri. Non ho fatto il test di "quadrilateralità", ma qual è la probabilità che tre punti scelti a caso in tre quadranti diversi siano allineati?
Comunque bisognerebbe fare anche questo test.

Ecco alcuni risultati e di seguito il programma.
quadrilateri1.PNG
quadrilateri1.PNG (33.61 KiB) Visto 860 volte
quadrilateri2.PNG
quadrilateri2.PNG (34.14 KiB) Visto 860 volte


Poi ho inserito nel programma l'elemento psicologico di cui parla Enrico.
Diciamo un 20% di distanza dagli assi rispetto alla dimensione del riquadro.
Ed ecco che la probabilità di avere un quadrilatero concavo scende al disotto dello 0,25%.
quadrilateri3.PNG
quadrilateri3.PNG (34.09 KiB) Visto 860 volte

Codice: Seleziona tutto

DECLARE EXTERNAL FUNCTION acaso 'sceglie un numero casuale 0 < acaso < 1 
DECLARE EXTERNAL FUNCTION qconvesso 'stabilisce se un quadrilatero è convesso o concavo

RANDOMIZE
LET wind=500
SET WINDOW 0,wind,0,wind
LET cont=10 'quanti quadrilateri vuoi cont*cont
LET k=wind/(2*cont)
FOR i=1 TO cont
   FOR j=1 TO cont
      LET ox=k+(i-1)*2*k
      LET oy=k+(j-1)*2*k
      LET ax=k*acaso+ox
      LET ay=k*acaso+oy
      LET bx=-k*acaso+ox
      LET by=k*acaso+oy
      LET cx=-k*acaso+ox
      LET cy=-k*acaso+oy
      LET dx=k*acaso+ox
      LET dy=-k*acaso+oy
      SET LINE COLOR 15 !'grigio
      PLOT LINES : ox-k,oy;ox+k,oy
      PLOT LINES : ox,oy-k;ox,oy+k
      !'PLOT TEXT ,AT ax,ay :"A"
      !'PLOT TEXT ,AT bx,by :"B"
      !'PLOT TEXT ,AT cx,cy :"C"
      !'PLOT TEXT ,AT dx,dy :"D"
      SET LINE COLOR 1 !'nero
      IF qconvesso(ax,ay,bx,by,cx,cy,dx,dy)=0 THEN SET LINE COLOR 4
      PLOT LINES:ax,ay;bx,by;cx,cy;dx,dy;ax,ay
   NEXT j
NEXT i
!'PRINT ax;ay;bx;by;cx;cy;dx;dy
END

EXTERNAL FUNCTION acaso
DO
   LET n=RND
LOOP UNTIL n<>0
LET acaso=n
END FUNCTION

EXTERNAL FUNCTION qconvesso(ax,ay,bx,by,cx,cy,dx,dy)
LET qconvesso=0
LET e1=cx-ax
LET e2=cy-ay
LET f1=dx-bx
LET f2=dy-by
LET p1=-e2
LET p2=e1
LET cmb1=cx-bx
LET cmb2=cy-by
LET h=(cmb1*p1+cmb2*p2)/(f1*p1+f2*p2)

LET e1=dx-bx
LET e2=dy-by
LET f1=ax-cx
LET f2=ay-cy
LET p1=-e2
LET p2=e1
LET dmc1=dx-cx
LET dmc2=dy-cy
LET g=(dmc1*p1+dmc2*p2)/(f1*p1+f2*p2)
IF g>0 AND g<1 AND h>0 AND h<1 THEN LET qconvesso=1
END function
Pace e bene a tutti.
Gianfranco

delfo52
Livello 9
Livello 9
Messaggi: 1486
Iscritto il: mer mag 25, 2005 4:19 pm
Località: bologna

Re: Probabilmente è convesso

Messaggio da delfo52 »

mi fa piacere constatare che quella che era una mia intuizione "approssimativa" trova una conferma nell'algoritmo addomesticato da Gianfranco
Enrico

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1188
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Probabilmente è convesso

Messaggio da Gianfranco »

Emergono i veri mandanti di questo problema: i Cavalieri Templari.
quadilateri_4.PNG
quadilateri_4.PNG (51.96 KiB) Visto 805 volte
Pace e bene a tutti.
Gianfranco

Bruno
Livello 9
Livello 9
Messaggi: 1457
Iscritto il: lun nov 21, 2005 6:07 pm
Località: Bologna

Re: Probabilmente è convesso

Messaggio da Bruno »

Fantastico :D
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
(Biagio Marin)

franco
Livello 8
Livello 8
Messaggi: 1172
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Probabilmente è convesso

Messaggio da franco »

Ho provato a ragionare su questo problema ma sono arrivato ad un punto morto per cui condivido lo “stato d’avanzamento”; magari può dare lo spunto a qualcuno per ulteriori passi avanti.
Di base ho considerato che, dati due punti casuali in quadranti opposti, la probabilità che il quadrilatero ottenuto con gli altri punti sia pari all’area del triangolo compreso fra gli assi cartesiani e la congiungente i due punti.
Per chiarire meglio, rappresento il concetto in un’immagine nella quale i due punti di partenza sono nei quadranti NE e SO e il triangolo si trova nel quadrante NO (ma è evidente che il concetto vale anche se la congiungente sta nel quadrante SE):
Conv1.png
Conv1.png (25.85 KiB) Visto 796 volte
La prima parte è relativamente semplice; io sono arrivato a questa espressione:
Conv2.png
Conv2.png (5.07 KiB) Visto 796 volte
L’integrazione con 4 variabili però è fuori dalla mia portata …
Conv3.png
Conv3.png (5.66 KiB) Visto 796 volte
Forse si può esprimere $S$ in una forma più facilmente integrabile, o forse ho solo perso tempo in elucubrazioni sbagliate :D
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1188
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Probabilmente è convesso

Messaggio da Gianfranco »

franco ha scritto:
dom set 06, 2020 11:09 pm
Di base ho considerato che, dati due punti casuali in quadranti opposti, la probabilità che il quadrilatero ottenuto con gli altri punti sia pari all’area del triangolo compreso fra gli assi cartesiani e la congiungente i due punti.
Chiedo scusa, ma non ho capito il collegamento tra la tua considerazione e la domanda del problema.
Edit del 8/9/2020: ho capito.
Pace e bene a tutti.
Gianfranco

delfo52
Livello 9
Livello 9
Messaggi: 1486
Iscritto il: mer mag 25, 2005 4:19 pm
Località: bologna

Re: Probabilmente è convesso

Messaggio da delfo52 »

cerco di interpretare.
I primi due punti, in due quadranti opposti, li mettiamo random.
A questo punto il segmento che li congiunge, attraversa uno dei due quadranti rimanenti.
In quello non attraversato, possiamo mettere il punto in qualsiasi posto. Nel quadrante interessato, il quarto punto genera un poligono concavo se cade nell'area colorata.
La sua superficie, rispetto a quella del quadrante, è la probabilità che la figura sia concava.
Enrico

franco
Livello 8
Livello 8
Messaggi: 1172
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Probabilmente è convesso

Messaggio da franco »

Grazie Enrico, ho ragionato esattamente in quel modo.
Peraltro, essendo ogni quadrante di area unitaria, la superficie della parte colorata rappresenta la probabilità di scegliere il punto in modo da ottenere un poligono concavo e il suo complemento a 1 la probabilità di ottenere un poligono convesso.
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1188
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Probabilmente è convesso

Messaggio da Gianfranco »

delfo52 ha scritto:
lun set 07, 2020 9:16 pm
cerco di interpretare.
Grazie Enrico, la tua spiegazione mi ha illuminato.
Mi ero fermato su una difficoltà linguistica.
Pace e bene a tutti.
Gianfranco

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1188
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Probabilmente è convesso

Messaggio da Gianfranco »

franco ha scritto:
dom set 06, 2020 11:09 pm
Ho provato a ragionare su questo problema ma sono arrivato ad un punto morto per cui condivido lo “stato d’avanzamento”; magari può dare lo spunto a qualcuno per ulteriori passi avanti.
L'integrale è troppo impegnativo anche per me, ma, se può servire per un confronto, ho fatto girare varie volte la mia simulazione e il risultato si è stbilizzato su queste 3 cifre significative:

ProbConvesso=90,9%
Pace e bene a tutti.
Gianfranco

panurgo
Livello 9
Livello 9
Messaggi: 1330
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: Probabilmente è convesso

Messaggio da panurgo »

Lo formalizzo di più per essere certo di quello che faccio.

Prendiamo quattro variabili distribuite uniformemente, $0\leq x,y,z,t\leq 1$, e definiamo i punti $\text{A}\equiv\left(x;y\right)$ e $\text{C}\equiv\left(-z;-t\right)$ in modo che, al variare di $x$ e $y$, il punto $\text{A}$ scandisca il quadrato unitario del primo quadrante mentre, al variare di $z$ e $t$, il punto $\text{C}$ scandisce il quadrato unitario del terzo quadrante.

La retta passante per $\text{A}$ e $\text{C}$ ha equazione $Y=mX+q$ con

$\displaystyle m=\frac{\left(y+t\right)}{\left(x+z\right)}$

e

$\displaystyle q=\frac{\left(yz-xt\right)}{\left(x+z\right)}$

L’intersezione della retta con l’asse delle ordinate identifica il punto $\text{E}\equiv\left(0;q\right)$; l’intersezione con l’asse delle ascisse identifica il punto $\text{F}\equiv\left(-\frac{q}{m};0\right)$
ProbabilmenteE`Convesso.05.001.480x480.png
ProbabilmenteE`Convesso.05.001.480x480.png (11.2 KiB) Visto 595 volte
L’area del triangolo $\text{OEF}$, che misura la frequenza di punti che producono un quadrilatero concavo, è data dal semiprodotto del valore assoluto dell’ordinata di $\text{E}$ e del valore assoluto dell’ascissa di $\text{F}$.
Osserviamo che le due coordinate hanno segno discorde
ProbabilmenteE`Convesso.05.002.480x480.png
ProbabilmenteE`Convesso.05.002.480x480.png (11.1 KiB) Visto 595 volte
dimodoché la frequenza, dati $x$, $y$, $z$ e $t$, vale

$\displaystyle f\left(\frown\middle|x\wedge y\wedge z\wedge t\wedge \top\right)=\frac{q^2}{2m}=\frac{\left(yz-xt\right)^2}{2\left(x+z\right)\left(y+t\right)}$.

(ricordo che \frown, $\frown$, significa “concavo” mentre \smile, $\smile$, significa “convesso” :shock:)

La frequenza si ottiene per marginalizzazione

$\displaystyle f\left(\frown\middle|\top\right)=\int_0^1{\int_0^1{\int_0^1{\int_0^1 {f\left(\frown\wedge x\wedge y\wedge z\wedge t \middle|\top\right) \,dt} \,dz} \,dy} \,dx}
=\int_0^1{\int_0^1{\int_0^1{\int_0^1 {f\left(x\middle|\top\right)\times f\left(y\middle|\top\right)\times f\left(z\middle|\top\right)\times f\left(t\middle|\top\right)\times f\left(\frown \middle|x\wedge y\wedge z\wedge t\wedge \top\right) \,dt} \,dz} \,dy} \,dx}$

Ma $f\left(x\middle|\top\right)=f\left(y\middle|\top\right)=f\left(z\middle|\top\right)=f\left(t\middle|\top\right)=1$ per cui

$\displaystyle f\left(\frown\middle|\top\right)=\int_0^1{\int_0^1{\int_0^1{\int_0^1 {\frac{\left(yz-xt\right)^2}{2\left(x+z\right)\left(y+t\right)} \,dt} \,dz} \,dy} \,dx}$

Questo integrale non è poi così formidabile: l’unica preoccupazione è che converga perché quelle variabili al denominatore significano logaritmi nell’integrale e uno degli estremi di integrazione è $0$.

Vedremo.


Continua...
il panurgo

Principio di Relatività: {\bb m} \not \right {\bb M} \ \Longleftrightarrow \ {\bb M} \not \right {\bb m}
"Se la montagna non va a Maometto, Maometto NON va alla montagna"

Rispondi