CyM2006, Ronda Nacional, Problema 3

CyM2006, Ronda Nacional, Problema 3

Rodrigo Belfiore 10 Nov 2007 22:34

Enunciado. Aparentemente sin problemas:
x es la distancia entre las rectas, a el area de media parte de abajo del círculo.
x seguro es menor que 2, sino no corta al círculo.

dim d as double, x as double, pi as double, a as double
pi=acos(-1)
d=0.000001
do while x < 2
   x+=d
   a+=d*(1-(1-x)^2)^(1/2)
   if x*pi-8*a < 0 then
       print x
       exit do
   end if
loop
sleep
'RTA:0,1836

Mi pregunta es cómo justifico el error.

Sobre cómo escribir en CyM

pabloh 11 Nov 2007 16:30

Antes de responder la consulta, quiero decir algo para los demás lectores del foro. Rodrigo escribe así porque es una consulta a Consultorio CyM, él tiene claro su resolución, y supone que con lo que escribió arriba es suficiente para que Consultorio CyM entienda su pregunta.

Pero que quede claro que eso no es la forma de responder en una prueba del Torneo. Hay que explicar bien qué es cada cosa, qué cuentas hacemos, justificar, explicar qué hace el programa (sin comentar línea por línea, sabemos leer código fuente; es la intención lo que hace falta explicar, porque no está en el código fuente), tratar de justificarlo.

Por ejemplo, acá habría que escribir sobre las cuentas hechas, hacer algunos diagramas en papel, y en cuanto al programa, se puede decir algo como “el programa aproxima la superficie de la parte inferior sumando muchos pequeños rectangulitos, y en cada punto evalúa la resta de los cocientes de áreas [simplificada a $x \cdot \pi - 4 \cdot 2a$] en busca de un cambio de signo”.

Re: CyM2006, Ronda Nacional, Problema 3

pabloh 11 Nov 2007 17:30

Respondo la consulta.

En tu resolución justificar el error es bastante difícil… Dividir una superficie en muchas partecitas chiquitas y sumar sus áreas es una técnica general para calcular áreas, pero acumula un error de aproximación, y es mejor usarla cuando no hay alternativas. En este caso se comete un error de aproximación al reemplazar la parte de círculo entre dos cuerdas paralelas por un rectángulo. Por supuesto que si no se nos ocurre nada más está bien usarlo.

Quiero decir que en CyM, por el momento, no somos muy estrictos con el tema de justificar la precisión de las cuentas numéricas¹. ¡Por ahora!

Para justificar bien bien, además de justificar que el error de cada operación aritmética es suficientemente chico (cosa que en CyM por ahora dejamos de lado, de hecho incluso los matemáticos no suelen hacerlo), tendríamos que ver que las partecitas de superficie que contamos de más, todas juntas, suman menos que el error que acepta el problema…

---

Si en cambio la resolución de este problema fuera:

1. encontramos fórmulas que para cada distancia $x$ nos den el cociente de las áreas del círculo y el cociente de las áreas del cuadrado (para el cuadrado es fácil: $4 \cdot (4 - x) / (4 \cdot x)$);
2. encontramos un $x_1$ donde la resta de cocientes da positiva, y un $x_2$ donde la resta de cocientes da negativa;
3. como la resta de cocientes es una función contínua, entre $x_1$ y $x_2$ hay un $x_0$ donde la resta da 0, que es lo que queremos (sólo que al $x_0$ no lo conocemos);
4. pero si $|x_1 - x_2|$ es suficientemente chico, hemos logrado aproximar la solución con la precisión deseada, por ejemplo $|x_1 - x_2| < 0.001$;

haciendo algo así podemos justificar el error más fácilmente.

Footnotes

1. Claro que puede hacer la diferencia entre un puesto y otro. ;-)

Última edición el 11 Nov 2007 19:46 por pabloh Mostrar más

Re: CyM2006, Ronda Nacional, Problema 3

pabloh 11 Nov 2007 17:34

Por cierto, la respuesta está bien. El valor exacto está entre 0.183633 y 0.183634 .

Re: CyM2006, Ronda Nacional, Problema 3

maxi 14 Nov 2007 23:17

LLamo A1 y A2 a las áreas mayor y menor del cuadrado.
Y también B1 y B2 a las áreas mayor y menor del círculo.
Entonces A1/A2 = B1/B2.
Sea x la distancia entre las rectas.
F(x) = A1/A2 - B1/B2.
Es decir, tengo que encontrar la raiz de F(x).
A1/A2 = (4-x)/x = 4/x - 1;
B1 + B2 = PI;
B1 = PI - B2;
B1/B2 = (PI-B2)/B2 = PI/B2 - 1;
La recta trazada corta a la circunferencia en 2 puntos que llamo p y q. Sea "beta" el ángulo del sector de cuerda pq y "alfa" la mitad de "beta".
Además, sea "o" el centro de la circunferencia.
B2 = PI*beta/360 - Área(poq);
Por ser circunferencia trigonométrica, tenemos que:
cos(alfa) = 1-x, de donde alfa = acos(1-x);
Área(poq) = sen(alfa) * (1-x) = sen(acos(1-x)) * (1-x);
beta = 2 * alfa = 2 * acos(1-x);
B2 = PI*2*acos(1-x)/360 - sen(acos(1-x)) * (1-x);
B2 = PI*acos(1-x)/180 - sen(acos(1-x)) * (1-x);
B1/B2 = PI/(PI*acos(1-x)/180 - sen(acos(1-x))*(1-x)) - 1;
Finalmente,
F(x) = (4/x - 1) - (PI/(PI*acos(1-x)/180 - sen(acos(1-x))*(1-x)) - 1);
F(x) = 4/x - PI/(PI*acos(1-x)/180 - sen(acos(1-x))*(1-x));
Entonces tengo que crear un programa con un lazo FOR de 0.0001 a 1, y para cada ciclo calcular F(x). Si F(X) < ERROR, entonces tenemos la respuesta.
En este caso, ERROR = 0.001, es decir, el error debe ser menor que 0.001
La respuesta que obtengo es: x = 0.18363

Me gustaría saber si la justificación es válida. Si alguno encontró una forma más simple de resolverlo o tiene alguna sugerencia, es bienvenida jeje. Gracias!

Saludos!

Re: CyM2006, Ronda Nacional, Problema 3

Rodrigo Belfiore 17 Nov 2007 19:07

Tenemos que $\frac{A1}{A2} = \frac{4-x}{x} = \frac{4}{x}-1$ y $\frac{B1}{B2} = \frac{\pi-B2}{B2} = \frac{\pi}{B2}-1$. Entonces $\frac{4}{x} = \frac{\pi}{B2}$.
Si $a=B2$, entonces $\pi x - 8a = 0$
Si tomo dos puntos $a$ y $b$ de una curva (de una función continua), digamos $(a_x; a_y)$ y $(b_x; b_y)$ sabemos que cuanto mas chico sea $a_x-b_x =dx$ el área bajo la curva (entre a y b) se acerca a $f(b_y)dx$ , y el error es menor al area del rectángulo de vertices $a_x,a_y,b_y,b_x$ cuya área es $|f(b_y)-f(a_y)|dx$.
Si acumulamos en $a$ y en $e$ estos dos valores, tenemos, en $a$ ,el área con un error menor a $e$.
Con un for buscamos cuando $\pi x - 8a < 0$ que inicialmente es positivo.
$f(x)=\sqrt{1-(1-x)^2}$ que es una circunferencia desplazada una unidad.

dim d as double, x as double, pi as double, a as double, e as double
pi=acos(-1)
d=0.000001
do while x < 1
   x+=d
   a+=d*(1-(1-x)^2)^(1/2)
   e+=d*((1-(1-x)^2)^(1/2)-(1-(1-x+d)^2)^(1/2))
   if x*pi-8*a < 0 then
       print x,"Error menor a";e
       exit do
   end if
loop
sleep

El resultado en pantalla:

 0.183632000000163          Error menor a 5.77532067139837e-007

Última edición el 17 Nov 2007 22:52 por Rodrigo Belfiore Mostrar más