Espera que el número de puntos en el círculo para formar un agudo ángulo del triángulo

Question

Este problema se me preguntó en una entrevista.

Seguimos sumando puntos en un círculo de manera uniforme hasta que existen tres puntos en el círculo que forman un agudo ángulo del triángulo. ¿Cuál es el número esperado de puntos en el círculo cuando el proceso se detiene?

Answer 1

Bien, vamos a considerar la probabilidad de que 3 puntos formando un triángulo agudo. En primer lugar, debido a la simetría de un círculo, la posición del primer punto es irrelevante. A continuación, el siguiente punto está en algún lugar en $[0,\pi]$ radianes desde el primer punto. Finalmente, un triángulo en el círculo es aguda iff que contiene el centro del círculo, de modo que el ángulo de $\theta$ entre los dos primeros puntos, que se refleja sobre el origen, es la región en el tercer punto debe ocupar para formar un triángulo agudo. Denotando $P(n)$ la probabilidad de formación de un triángulo agudo después de$n$, e $p(n)$ la probabilidad de que el $n^{\mathrm{th}}$ punto constituye el primer ejemplo de un triángulo, $$p(3)=P(3)=\frac{\int_0^\pi \frac{\theta}{2\pi} \mathrm d\theta}{\pi}=\frac{\frac{1}{2}\theta^2|_0^\pi}{2\pi^2}=\frac{1}{4}$$

Ahora, el siguiente punto, si no se forma un triángulo equilátero, puede ocupar $2\pi-\theta$ rad, $\pi$ de que se amplíe el ángulo máximo entre los puntos.

Para la generalidad, vamos a llamar a $\theta_n$ la mayor separación angular entre dos puntos después de $n$ puntos han sido colocados, dado que no hay tres puntos forman un triángulo agudo. Podemos obtener una relación de recurrencia para $\overline{\theta_n}$, como la colocación de un nuevo punto aumenta $\theta$ linealmente cuando se entre $\theta$ $\pi$ a partir de uno de los la mayoría de los puntos extremos. Cuando es entre estos puntos, $\theta$ aumenta por $0$. Por lo tanto, $\overline{\theta_n}=\theta_{n-1}+\frac{2\int_0^{\pi-\theta_{n-1}}x\mathrm dx+\int_0^{\theta_{n-1}}0\mathrm dx}{2\pi-\theta_{n-1}}=\theta_{n-1}+\frac{(\pi-\theta_{n-1})^2}{2\pi-\theta_{n-1}}$. La media original $\theta_2$$\pi/2$, lo $\overline{\theta_3}=2\pi/3$, y por lo que las posibilidades de formar un ángulo agudo con el cuarto punto es $1/3$. Por el cuarto punto, la oportunidad de haber formado un agudo de ángulo de un triángulo es ahora $$ \frac{1}{4}+\frac{3}{4}\cdot\frac{1}{3}=\frac{1}{2} $$ Así que usted puede esperar de un $50/50$ de probabilidad de un triángulo agudo después de 4 puntos.

Ahora vamos a calcular el valor esperado:

De hecho, sustituyendo $\overline{\theta_n}$$\pi\left(1-\frac{1}{a_n}\right)$, obtenemos $$\begin{align} \overline{\theta_n}&=\pi\left(1-\frac{1}{a_{n-1}}\right)+\frac{\left(\pi-\pi\left(1-\frac{1}{a_{n-1}}\right)\right)^2}{2\pi-\pi\left(1-\frac{1}{a_{n-1}}\right)} \\ &=\pi\left(1-\frac{1}{a_{n-1}}+\frac{1}{a_{n-1}(1+a_{n-1})}\right) \\ &=\pi\left(1-\frac{1}{a_{n-1}+1}\right) \end{align}$$

Y, por tanto,$a_n=a_{n-1}+1$. Desde $a_2=2$, $\overline{\theta_n}=\frac{(n-1)\pi}{n}$:

$$\begin{align} P(n+2)&=\sum_{k=1}^n \left(\prod_{i=1}^k (1-p(i+1))\cdot\frac{p(k+1)}{1-p(k+1)}\right) \\ &=\sum_{k=1}^n \left(\left(\prod_{i=1}^k \left(1-\frac{i}{2(i+1)}\right)\right)\frac{k}{k+2} \right) \\ &=\sum_{k=1}^n 2^{-k} \left(\prod_{i=1}^k \frac{i+2}{i+1}\right) \frac{k}{k+2} \\ &=\sum_{k=1}^n \frac{k}{2^{k+1}} \\ &=1-\frac{n+2}{2^{n+1}} \end{align}$$

El producto es $1-\frac{\overline{\theta_{i+1}}}{2\pi}$, o la probabilidad de no obtener un triángulo agudo para $k+2$ puntos, multiplicado por el $k/(k+2)$, de modo que el último término es la probabilidad de obtener un triángulo agudo en lugar de no. Telescópico de la serie permite la simplificación del producto. La suma puede ser demostrado por inducción en $n$.

Entonces tenemos que $P(n)=1-2^{1-n}\cdot n$. También podemos determinar el valor esperado del número de puntos, $E(X)$:

$$E(X)=\sum_{n=3}^\infty n\cdot p(n)=\sum_{n=3}^\infty \frac{n(n-2)}{2^{n-1}}=\sum_{n=1}^\infty \frac{n(n-1)+3n}{2^{n+1}}$$ Desde $\sum_{n=0}^\infty {n\choose r}2^{-n}=2$, $\sum_{n=0}^\infty n\cdot 2^{-n}=\sum_{n=0}^\infty \frac{1}{2}n(n-1)2^{-n}=2$. $$ \Rightarrow E(X)=\sum_{n=0}^\infty \left({n\choose 2}2^{-n}+\frac{3}{2}{n\choose 1}2^{-n} \right)=2+3=5$$

Answer 2

Usted no tiene un triángulo acutángulo si todos los puntos están dentro de un semicírculo. Cuando la adición de un nuevo punto (suponiendo que no hay todavía un triángulo agudo), la probabilidad de que forma un triángulo acutángulo es la fracción del círculo cubierto por el menor arco que contiene los puntos existentes. Por tres puntos, la probabilidad es $\frac 14$, ya que la distancia entre los dos primeros puntos es el uniforme de $0$$\pi$, por lo que la probabilidad de que el tercer punto, que forma un triángulo acutángulo es el uniforme de $0$$\frac 12$. Dependiendo del trabajo, esto parece como un progreso suficiente para una entrevista, pero me gustaría ver una respuesta completa.