Puedo ver muchos enfoques posibles, pero permítanme esbozar un enfoque que creo que podría ser eficaz y podría dar una precisión razonable con una cantidad razonable de esfuerzo. Utiliza la simulación de Monte Carlo, la independencia y la linealidad de las expectativas. Voy a dividirlo en trozos pequeños, identificando un conjunto de subproblemas más pequeños y explicando cómo resolver cada subproblema, para luego mostrar cómo combinar esas soluciones a los subproblemas para resolver el problema original del concurso de programación.
Subproblema 1. Dados dos círculos $C,C'$ en el cuadrado, determinar si se cruzan.
Solución 1. Dejemos que $C$ estar centrado en el punto $(x,y)$ y tienen un radio $r$ y $C'$ estar centrado en $(x',y')$ con radio $r'$ . Obsérvese que los dos círculos se superponen si y sólo si la distancia entre los dos centros es como máximo $r+r'$ es decir, si y sólo si $(x-x')^2 + (y-y')^2 \le (r+r')^2$ . Esta condición es fácil de comprobar, en función de $x,y,r,x',y',r'$ .
Subproblema 2. Supongamos que el primer círculo viene dado por $C$ . Calcule la probabilidad $p(C)$ que el segundo círculo no se cruzará $C$ en función de $C$ .
Solución 2. Utilizaremos la simulación de Monte Carlo. En concreto, realizaremos 10.000 ensayos, en los que en cada uno de ellos, dejaremos caer aleatoriamente el segundo círculo $C'$ y comprobar si $C,C'$ intersección (utilizando la solución 1 anterior para comprobar la intersección). Cuente el número de ensayos en los que no se cruzan y divídalo por 10.000; esa es su estimación de $p(C)$ . (Puede ser posible resolver este subproblema analíticamente, resolviendo una integral tridimensional; sin embargo, eso no parece divertido. La simulación de Montecarlo es más fácil).
Subproblema 3. Supongamos que el primer círculo viene dado por $C$ . Calcule la probabilidad $p'(C)$ que ninguno de los restantes $N-1$ los círculos se cruzarán $C$ en función de $C$ .
Solución 3. Tenga en cuenta que, por la independencia, $p'(C) = p(C) \times \cdots \times p(C) = p(C)^{N-1}$ . Esto es fácil de calcular.
Subproblema 4. Calcule la probabilidad $q_1$ que, si se deja caer $N$ círculos al azar, ninguno de los últimos $N-1$ círculos tiene cualquier intersección con el primer círculo.
Solución 4. Obsérvese que, si dejamos que $C$ sea una variable aleatoria, tenemos $q_1 = E[p'(C)]$ donde la expectativa se hace cargo de $C$ . Utilice la simulación de Monte Carlo. Realiza 10.000 ensayos, en los que en cada ensayo elijas aleatoriamente un círculo $C$ , entonces se calcula $p'(C)$ (utilizando la solución 3). Haz la media de los resultados de todos los ensayos. Esa es tu estimación de la probabilidad $q_1$ .
Subproblema 5. Calcule la probabilidad $q_i$ que, si se deja caer $N$ círculos al azar, el $i$ El círculo no tiene intersección con ninguno de los otros $N-1$ círculos.
Solución 5. Por simetría, $q_i = q_1$ Por lo tanto, la solución 4 ya proporciona la respuesta.
El problema original. Calcule el número esperado de círculos que no tienen intersección con ningún otro círculo, si deja caer $N$ círculos al azar.
Solución. Por linealidad de la expectativa, esto es $q_1+q_2+\cdots+q_N$ . Por la solución 5, esto es $N \times q_1$ . Ahora utilice la solución 4 para calcular $q_1$ y ya tienes la respuesta al problema original.
2 votos
¿El radio sólo toma valores enteros en $\{0,\ldots,M\}$ o es una variable aleatoria continua que toma valores en $[0,M]$ ?
0 votos
R es un valor aleatorio uniformemente distribuido entre 0 y algún número entero M
2 votos
Incluso ese documento no es perfectamente claro en cuanto a su significado. Es curioso que hayan especificado un entero $M$ . Sin embargo, también dicen $R$ es un real número, con lo que supongo que se refieren a un número no necesariamente entero. Por lo tanto, parece que lo que se quiere decir es uniforme en $[0,M]$ a diferencia de los uniformes en $\{0,1,\ldots,M\}$ . En cualquier caso, no quieren una respuesta exacta, sólo una estimación de Monte Carlo.