lunes, 6 de agosto de 2018

Números de Catalan

Fue el gran Leonhard Euler (1707-1783) la primera persona en calcular los denominados números de Catalan. Le comunicó los primeros valores a Johann Segner (1704-1777), pero no le dijo la técnica que utilizó para calcularlos. Segner obtiene estos números, por recurrencia,  al estudiar las posibles triangulación de un polígono.

Una triángulación de un polígono es una forma de descomponerlo como una unión disjunta de triángulos cuyos vértices coinciden con los del polígono. Es fácil ver que para triangular un polígono de n+2 vértices se necesitan n triángulos y viceversa.

Sea Cn el número de maneras de descomponer un polígono utilizando exactamente en triángulos. Como se observa en la imagen: $$C_1=1, C_2=2, C_3=5, C_4=14 $$
La fórmula de recurrencia, dada por Signer en 1758, para obtener los números de catalán es: $$C_{n+1}=C_0·C_n+C_1·C_{n-1}+C_2·C_{n-2}+\cdots+C_{n-1}·C_1+C_n·C_0$$ siendo $$C_0=1$$
Demostración por inducción:

Si sabemos triangular los polígonos de n+2 lados, entonces podemos triangular un polígono de n+3 lados.

El polígono tiene los vértices 1,2,3,...n+3 y escogemos un 'lado favorito': el lado de vértices 1 y n+3, que pertenece a un triángulo Tde la triangulación, siendo i el tercer vértice que pertenece al conjunto {2,3,...n+2}.

En la figura se observa que sería el triángulo de vértices 1,4 y 8.
En general, si se elimina ese triángulo Ti, resultan dos polígonos:
  • Vértices 1,2,...i que puede ser triangulado de Ci-2 maneras.
  • Vértices i,i+1,,...n+3 que puede ser triangulado de Cn-i+2 maneras.
Ambas elecciones son independientes, por tanto la manera de triangular el polígono que contiene al triángulo Ti es:
$$C_{i-2}·C_{n-i+2}$$
Al variar Ti sobre todos los valores posibles {2,3...n+2} se obtiene la fórmula.

Alrededor de un siglo después Eugène Catalan (1814-1894), volverá a calcular el número de maneras de triangular un polígono. En su memoria, esos números  llevan  su nombre.

Es una fórmula que evita la recurrencia y permite obtener directamente los números:
$$C_n=\frac{1}{n+1} \binom{2n}{n}=\frac{(2n)!}{(n+1)!·n!} \wedge n\geq 0$$
A partir de esta fórmula se puede obtener una fórmula de recurrencia más sencilla:
$$\frac{C_{n+1}}{C_n}=\frac{(2n+2)!}{(n+2)!(n+1)!}:\frac{(2n)!}{(n+1)!n!}=\frac{2(2n+1)}{n+2}$$
$$C_{n+1}=\frac{2(2n+1)}{n+2}{C_n}\wedge n\geq 1$$
Existen infinidad de situaciones en las que aparecen los números de Catalan. Una de ellas es el número de caminos monótonos crecientes a través de una retícula de tamaño nxn y que no atraviesen la diagonal:
Las aplicaciones sucesivas de un operador binario pueden representarse con un árbol binario. 
En este caso, Cn es el número de árboles binarios de n + 1 hojas, en los que cada nodo tiene cero o dos hijos:

En su página de internet Richard Stanley, nos reta con 95 familias de objetos enumerados por los números de Catalan.

sábado, 23 de junio de 2018

Selectividad ciencias-Curso 17/18

A continuación aparecen los enunciados y las soluciones de los problemas de selectividad de la Comunidad Valenciana en formato .pdf, de junio y de julio para el bachillerato de ciencias del curso 17/18.

Enunciados y soluciones de junio
Enunciados y soluciones de julio

miércoles, 20 de junio de 2018

Selectividad ciencias sociales-Curso 17/18

A continuación aparecen los enunciados y las soluciones de los problemas de selectividad de la Comunidad Valenciana en formato .pdf, de junio y de julio para el bachillerato de ciencias del curso 16/17.

Enunciados y soluciones de junio
Enunciados y soluciones de julio

martes, 29 de mayo de 2018

El problema de la dote del sultán

Un sultán tiene 100 hijas y decide dar la mano de una de ellas al súbdito que supere la siguiente prueba: Cada hija desfilará delante del pretendiente indicando la dote que tiene asignada. El súbdito sólo podrá casarse con la hija de mayor dote si adivina cuál de ellas es. Para ello debe decidir si la elige o prefiere continuar viendo el resto. Una vez rechazada una de las hijas, la decisión no se  puede cambiar. Se supone que todas las dotes son distintas y que no tiene información previa sobre su cuantía.

¿Cuál es la mejor estrategia para superar la prueba?

Una estrategia es dejar pasar n hijas y después elegir aquella que tenga una dote que supere a todas las precedentes (incluidas las n primeras).  ¿Cuál es el número n que maximiza la probabilidad de elgir la dote más alta?
Supongamos que hay 3 hijas, cuyas dotes se numeran de mayor (1) a menor (3). En la tabla se muestran las diferentes ordenaciones y para qué valor de n se obtiene la dote mayor. Se observa que cuando se descarta una hija, se consigue la mayor dote en tres casos: p(n=1)=3/6=1/2.

La probabilidad de acertar con N hijas habiendo rechazado las n primeras es:
$$\frac{1}{N} \frac{n}{n+k}$$
ya que acertamos si la mayor está en el puesto n+1, que ocurre con probabilidad 1/N. También si la mayor está en el puesto n+k+1 que ocurre con probabilidad 1/N y la mayor de las n+k precedentes está entre las n primeras, que ocurre con probabilidad n/(n+k).

La probabilidad de acertar es la suma de estas probabilidades extendidas a todos los valores posibles de k, desde 0 hasta N-n-1: $$p=\frac{n}{N} \left( \frac{1}{n}+\frac{1}{n+1}+\frac{1}{n+2}+ \ldots +\frac{1}{N-1} \right)$$ 
Teniendo en cuenta la serie armónica:
$$H_n=1+\frac{1}{2}+\frac{1}{3}+\ldots + \frac{1}{n}$$
la probabilidad de acertar se puede expresar:
$$p=\frac{n}{N} \left(H_{N-1} - H_{n-1}\right)$$
Y como la serie armónica se puede aproximar con la fórmula que utiliza la constante de Euler-Mascheroni: $$H_n=ln(n)+\gamma$$ la probabilidad de éxito será: $$p=-\frac{n}{N}ln\left(\frac{n-1}{N-1}\right)$$
Cuando N y n son grandes, se puede aproximar a: $$p=-\frac{n}{N}ln\left(\frac{n}{N}\right)=-\alpha ln(\alpha)$$ Optimizando se obtiene: $$\alpha=\frac{n}{N}=\frac{1}{e}=0,3679\ldots$$ y por tanto habría que dejar pasar el 36,79% de las hijas antes de empezar a elegir una de ellas.

Descargar .XLS
Sigue las instrucciones de utilización del modelo de Excel que puedes descargar a continuación:
  • Con las flechas se elige el número de novias descartadas n.
  • Con el botón 'elige' se muestran las siguientes dotes, deteniéndose si una dote supera a las anteriores y se habilita el botón 'comprobar'.
  • El botón 'comprobar' muestra las dotes ocultas y se comprueba si ha habido éxito.
  • Con las flechas se elige el número de novias N y el número de novias descartadas n.
  • Se observa numérica y gráficamente las probabilidades de éxito para cada supuesto.

sábado, 28 de abril de 2018

Curva del pez

Se traza una circunferencia de radio AB. En la circunferencia el punto B es fijo y el punto C es variable. Se traza una circunferencia de centro C y radio AB+k·BC. Este radio varía al desplazarse C. La parelela al radio AB por C determina un diámetro DE. Al desplazar el punto C,  los puntos D y E se desplazan obteniéndose un lugar geométrico en forma de pez.

Al mover el punto C de la circunferencia, los puntos D y E recorren el lugar geométrico. Al desplazar A y B podemos modificar la circunferencia. El deslizador permite fijar el valor deseado de k. Se puede observar la construcción 'paso a paso'.

sábado, 24 de marzo de 2018

Teorema de Mikami y Kobayashi

Es una de las figuras que aparecen en “tablillas de madera”, Sangaku en japonés, en los templos budistas y santuarios sintoístas. Generalmente, contenían relevantes descubrimientos matemáticos de contenidos geométricos. Estas tablillas se construyeron durante el periodo EDO que duró desde 1603 hasta 1867. Un periodo caracterizado por el aislamiento de Japón del mundo occidental, lo que provocó que no se conociese en ese país el gran desarrollo que en esos siglos tuvo la Matemática en Europa, de tal manera que algunos teoremas, que llamaríamos europeos, fueron también realizados independientemente por japoneses. La aparición de las tablillas en este periodo EDO, va desde la más antigua conservada de 1683 en la prefectura de Tochigi, hasta la de Kinshouzan en 1865. En algunos casos se descubrieron muchos años más tarde de su creación, así por ejemplo, una tablilla realizada en 1814, se descubrió en 1994. Actualmente se conservan algo más de 800 tablillas pero se sabe que su número ha sido muy superior, pues se han perdido o quemado un gran número de ellas.

Al unir los incentros de los triangulos ABC, ACD, ABD y CBD formados al trazar las diagonales de un cuadrilátero inscrito en una circunferencia se forma un rectángulo.
La recta AQ divide al ángulo MQP en dos ángulos alfa y beta. Por ser M el incentro de ABC se cumple que: $$\frac{\widehat{BAC}}{2}+\frac{\widehat{ACB}}{2}+\frac{\widehat{CBA}}{2}=90$$ y en el triángulo AMB: $$\widehat{BAM}+\widehat{AMB}+\widehat{MBA}=\frac{\widehat{BAC}}{2}+\widehat{AMB}+\frac{\widehat{CBA}}{2}=180$$ Por tanto: $$\widehat{AMB}=90+\frac{\widehat{ACB}}{2}$$ De forma similar, por ser Q el incentro de ABD se cumple que: $$\widehat{AQD}=90+\frac{\widehat{ADB}}{2}$$ Se cumple que: $$\widehat{ACB}=\widehat{ADB}=\widehat{AMB}=\widehat{AQD}$$ por ser ángulos inscritos que abarcan el mismo arco.

El cuadrilátero AQMB está inscrito en una circunferencia siendo: $$\alpha=\frac{\widehat{CBA}}{2}$$ De manera análoga, el cuadrilátero AQPD está inscrito en una circunferencia siendo: $$\beta=\frac{\widehat{ADC}}{2}$$ Entonces: $$\widehat{MQP}=\alpha+\beta=\frac{\widehat{CBA}+\widehat{ADC}}{2}=\frac{180}{2}=90$$ De forma similar se comprobaría que los ángulos restantes del cuadrilátero son rectos y por tanto AQMB es un rectángulo.

Se pueden desplazar el centro de la circunferencia y los cuatro vértices del rectángulo (los incentros) y así cambiar el tamaño de la figura y comprobar el teorema.

lunes, 26 de febrero de 2018

Principio de Wardrop

Supongamos que 1000 vehículos desean ir de A a B y tienen dos formas de hacerlo: ACB (ADB). Ambas rutas tienen un tramo de autopista AC (DB) en los que se tarda un tiempo que no depende del número de vehículos debido a su alta capacidad y un tramo CB (AD), que al ser una vía convencional, en el que el tiempo aumenta 1 minuto por cada 100 vehículos que la transitan.
Si se elige la ruta ACB:
$$t_{AC}+t_{CB}=t_{AC}+\frac{X_{CB}}{100}$$ Si en esta ruta se tardan 15 minutos por autopista y circulan 600 vehículos, el tiempo total empleado será: $$t_{ACB}=15+\frac{600}{100}=21$$
Si se elige la ruta ADB:
$$t_{AD}+t_{DB}=\frac{X_{AD}}{100}+t_{DB}$$
Si en esta ruta se tardan 10 minutos por autopista y circulan 400 vehículos, el tiempo total empleado será:  $$t_{ADB}=\frac{400}{100}+10=14$$ Una parte de los conductores, los más avispados, que fueron por la ruta ACB eligirán la próxima vez la ruta ADB que es más rápida. Esto hará que ahora la ruta ADB sea más rápida (menos vehículos) pero la ruta ADB no lo sea tanto (más vehículos). El proceso seguirá hasta alcanzar un equilibrio que se producirá cuando los tiempos de viaje sean los mismos para ambos trayectos. A nadie le interesará cambiar en el próximo viaje.

Estamos ante un Equilibrio de Nash de la teoría de juegos: no hay cambio de estrategia individual que permita a un jugador aumentar su 'ganancia'.

En el ejemplo: $$t_{ACB}=t_{ADB}$$ $$15+\frac{250}{100}=\frac{750}{100}+10=17.5$$
 Principio de Wardrop (1952):

Los tiempos de viaje en todas las rutas es igual (entre ellas), y menor al tiempo que experimentaría cualquier vehículo que decidiera cambiar a otra ruta.
Descargar .XLS
Sigue las instrucciones de utilización del modelo de Excel que puedes descargar a continuación:

  • Con las flechas se puede modificar el número de vehículos iniciales por la ruta A.
  • Con las flechas se obtiene la evolución de los tiempos y vehículos en cada ruta.
  • Con la flechas se pueden fijar los tiempos por autopista.
  • Se muestran los valores de equilibrio de tiempo y vehículos.

sábado, 27 de enero de 2018

Radicales infinitos y jerarquizados

Es posible que el primer radical infinito jerarquizado  se deba a François Viète que en 1593 publicó su famosa fórmula del número pi: $$\frac{2}{\pi}=\frac{\sqrt 2}{2}\cdot \frac{\sqrt{2+\sqrt 2}}{2}\cdot \frac{\sqrt{2+\sqrt {2+\sqrt 2}}}{2} \cdot...$$ Veamos cuál es el valor del siguiente radical infinito y jerarquizado: $$\sqrt{2+\sqrt{2+\sqrt{2+...}}}$$ Resolviendo por autosemejanza: $$\sqrt{2+\underbrace{\sqrt{2+\sqrt{2+...}}}}=x \rightarrow \sqrt{2+x}=x$$ $$2+x=x^2 \rightarrow x=2$$ es la única solución positiva. Generalizando se tiene: $$\sqrt{a+\sqrt{a+\sqrt{a+...}}}$$ se llega a la ecuación: $$a+x=x^2 \rightarrow a=x(x-1)$$ Por tanto, todo número x>1 puede escribirse como un radical infinito y jerarquizado. Por ejemplo: $$3=\sqrt{6+\sqrt{6+\sqrt{6+...}}}$$ Generalizando un poco más: $$\sqrt{a+b\sqrt{a+b\sqrt{a+...}}}$$ se llega a la ecuación: $$a+bx=x^2 \rightarrow a=x(x-b)$$ Se observa que si x es un número natural, existen x-1 pares de números naturales: $$(a,b) \wedge 0 < b < x$$ que permiten representar los números naturales de más de una forma, por ejemplo: $$5=\sqrt{20+\sqrt{20+\sqrt{20+...}}}=\sqrt{15+2\sqrt{15+2\sqrt{15+...}}}=$$ $$\sqrt{10+3\sqrt{10+3\sqrt{15+...}}}=\sqrt{5+4\sqrt{5+4\sqrt{5+...}}}$$ En el caso de a=0 se tiene: $$\sqrt{b\sqrt{b\sqrt{b+...}}}=b^{\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+...}=b$$
Recordando la proprción aúrea:

se tiene que:
$$\frac{a}{b}=\phi \rightarrow \phi= 1+\frac{1}{\phi}\rightarrow 1=\phi(\phi-1)$$
y por tanto, el número de oro, solución positiva de la ecuación anterior, se puede expresar también mediante radicales infinitos jerarquizados:
$$\phi=\frac{1+\sqrt {5}}{2}=\sqrt{1+\sqrt{1+\sqrt{1+...}}}$$
En Los números metálicos podrás buscar las expresiones en radicales infinitos y jerarquizados de los números de plata, bronce, cobre y níquel. 

Pero también puede haber expresiones, con otro tipo de radicales, como: $$\psi=\sqrt[3]{1+\sqrt[3]{1+\sqrt[3]{1+...}}}$$ que da origen a la ecuación: $$\psi ^3-\psi-1=0\rightarrow \psi=1.32471...$$ que fue llamado número de plástico por el arquitecto Dom Hans van der Laanen en 1928.

sábado, 23 de diciembre de 2017

Alhacén y la cúbica de Barrow

Alhacén esta considerado como el padre de la óptica por sus trabajos sobre lentes, espejos, reflexión y refracción. En su obra principal Kitab al-Manazir (Libro de Óptica) plantea el problema siguiente:
En un plano se tiene una circunferencia y dos puntos exteriores A y B. Si la circunferencia funciona como un espejo se trata de encontrar el punto P de la circunferencia donde el rayo incidente desde A se refleje en el punto B. Para ello los ángulos deben ser iguales según la ley de la reflexión.
Lo resuelve de una manera muy tediosa y complicada por lo que matemáticos posteriores encuentran soluciones más sencillas. Isaac Barrow publicó en Cambridge Lectures en 1966 una solución al llamado 'Problema de Alhacén':
Dados dos puntos A(a,b) y B(c,d), se trata de encontrar sobre cualquier recta que pasa por el origen, un punto P(x,y) de forma que los ángulos que forman PA y PB con la recta sean iguales.

En el triángulo OPQ se tiene:
$$\alpha+\phi+(180-\theta)=180\rightarrow\alpha=\theta-\phi$$ Como: $$\tan \phi=\frac{y}{x} \wedge \tan \theta=\frac{b-y}{a-x}$$ se tiene que: $$\tan \alpha=\tan(\theta - \phi)=\frac{\tan \theta-\tan \phi}{1+\tan\theta·\tan \phi}=\frac{bx-ay}{ax+by-(x^2+y^2)}$$ Mediante un razonamiento análogo se obtiene: $$\tan \beta=\frac{cy-dx}{cx+dy-(x^2+y^2)}$$ Igualando ambas expresiones, eliminando denominadores y agrupando términos semejantes se obtiene: $$(x^2+y^2)[(b+d)x-(a+c)y]-(ad+bc)x^2$$ $$+(ad+bc)y^2+2(ac-bd)xy=0$$ Si se sitúan los puntos A y B de forma que el eje de abscisas sea la bisectriz del ángulo AOB, y entonces la ecuación se simplifica porque:
$$\frac{b}{a}=\frac{d}{c}\rightarrow bc+ad=0$$
Finalmente la ecuación se puede expresar de la forma: $$(x^2+y^2)(px+qy)+xy=0$$ siendo:
$$p=\frac{b+d}{2(ac-bd)} \wedge q=\frac{a+c}{2(ac-bd)} $$

Esta ecuación representa una curva algebraica de tercer grado. Si se centra la circunferencia en el origen de coordenadas, los puntos en los cuales ésta es cortada por la cúbica resuelven el problema. De las tres soluciones, sólo una tiene sentido físico.

Se pueden desplazar los puntos A y B mostrando sus coordenadas. Al mover el punto C se fija el tamaño de la circunferencia. Se comprueba, moviendo el punto P de la circunferencia, que cuando los ángulos coinciden el punto pertenece a la curva y por tanto es la solución. El botón 'curva' permite visualizarla o no.
  • Del libro Alhacén, el Arquímedes árabe. Ricardo Moreno Castillo.
    La Matemática en sus personajes. Editorial Nivola.

lunes, 27 de noviembre de 2017

Algoritmo de Irving

El llamado The Stable Rommates Problem o 'Problema de las Compañeras de Piso' fue resuelto mediante un algoritmo por Robert W. Irving en 1985. Cada participante ordena a sus posibles compañeras según sus preferencias. Cada chica elige una compañera y ésta acepta o no la oferta. En caso de no aceptar se entiende que rechaza a la chica que le ha hecho la propuesta. En el ejemplo de la tabla el AZUL indica la elegida, el VERDE la que acepta y el ROJO la rechazada.
  • 1ª ETAPA
    • Cada chica propone a su compañera favorita.
    • La elegida acepta, pero si es elegida por más de una, acepta la mejor propuesta y rechaza las demás.
    • Las rechazadas esperan para ser aceptadas más adelante.
    • Si alguna chica es rechazada por todas no existe una solución estable.
Aunque Berta elige a Delia, ella prefiere a Clara y es rechazada. Igualmente, aunque Eva elige a Flor, ella prefiere a Delia y es rechazada.
Ahora Berta propone a Eva que acepta y Eva propone a Clara que acepta.
  • 2ª ETAPA
    • Todas desechan las posibles compañeras que son menos deseadas que la actualmente aceptada.
Ana rechaza a Clara y a Eva, Berta rechaza a Clara, y así sucesivamente.
Así las opciones quedan reducidas a las siguientes:
  • 3ª ETAPA
    • Elige una participante X que tenga al menos dos opciones.
    • Busca su segunda preferencia Y.
    • Sea Z la última preferencia de Y.
    • Repite el proceso hasta que se llegue a X.
    • Elimina las parejas (Y,Z) y sus simétricas.
    • Repite el proceso hasta que todas tengan una única opción.
Los emparejamientos son: Ana y Flor, Berta y Eva, Clara y Delia.
En este caso no hay una solución estable, pues nadie quiere ir con D.