domingo, 7 de febrero de 2016

Un triángulo con un extraño tipo de centro

Enunciado

Este problema no era tan difícil como para no obtener una buena puntuación. Si no fue así probablemente fue por el cansancio de realizar una prueba tan larga.

Mi forma favorita de enfrentar este tipo de problema es mediante geometría analítica. Si leemos bien el enunciado, seremos capaces de dar las coordenadas de tres puntos que cumplan las condiciones y acabaremos por dar respuesta al enunciado.

En primer lugar, voy a situar el punto donde concurren las tres rectas, bisectriz, altura y mediana, en el origen de coordenadas. La bisectriz, que pasa por A, será el eje X, con lo que el punto A, si lo represento hacia la derecha, tendrá unas coordenadas (a, 0) para algún número positivo a. La mediana, que pasa por B, será el eje Y, y si el punto B lo sitúo en la parte positiva, tendrá unas coordenadas (0, b) para algún número positivo b.

El lado AB tendrá, por tanto vector director (-a, b), y pendiente -b/a. Y como el eje X es la bisectriz del ángulo entre AB y AC, sabemos que el lado AC tendrá la pendiente opuesta (recuerda que la pendiente es la tangente del ángulo que forma el eje X con la recta o el vector). Si has dado producto escalar, también puedes razonar por productos escalares para obtener ese resultado.

Esto significa que el vector director del lado AC será (a, b), por lo que la ecuación de la recta será bx - ay = ba, ya que pasa por (a, 0). Eso significa que el punto de corte con la mediana ha de ser el (0, -b), y por ser el punto de corte de la mediana que pasa por B con el lado AC, tiene que ser el punto medio del lado. De esta forma, el simétrico de A respecto a este punto, (-a, -2b), será el punto C.

Necesitamos precisar más sobre los valores a y b para que la altura pase por el punto de concurrencia (recuerda, el eje de coordenadas). Así, un vector director de esta altura debe ser (a, 2b), ya que pasa por C y por (0, 0), y debe ser perpendicular al vector director del lado AB, (-a, b). Aplicando la propiedad de las pendientes de rectas perpendiculares (o el producto escalar, si ya lo conoces, tenemos que 2b/a = a/b, es decir, que 2b2 = a2, y, puesto que ambos son números positivos, tenemos que √2 b = a.

Si queremos que la distancia AB mida 1, podemos forzar que b2 + a2 = 1, pero también podemos encontrar cualquier trio de puntos A, B y C que cumplan las demás propiedades y después construir mediante una semejanza un triángulo como el solicitado, que yo veo mejor solución.

Optando por esta última aproximación, hacemos que b = 1, a = √2 y por tanto nuestros puntos serán A (√2, 0), B(0, 1) y C(-√2, -2). En este triángulo los lados miden AB = √ 3, AC = 2√3 y BC = √11. Si escalamos el triángulo para que AB mida 1, tendremos las medidas definitivas: AB = 1, AC = 2 y BC = √11/√3 = √33/3.

Un seguidor del blog, Ricard Peiró, nos remite otra solución basada en geometría clásica.

Sean la bisectriz AD, la mediana BE y la altura CF, tenemos que AE = CE = b/2.

Aplicando la propiedad de la bisectriz, CD/BD = b/c = b.

Sea P el punto donde concurren la bisectriz AD, la mediana BE y la altura CF.

El segmento AP es perpendicular a BE y el ángulo PAE = ángulo PAB y es la mitad del ángulo A.

Entonces, AE = BE = 1, y b = 2AE = 2.

Aplicando el Teorema de Ceva, se tiene que (CD/BD)(BF/AF)(AE/CE) = 1, por lo que (b/c)(a cos(B)/(b cos(A)) = 1, por lo que a cos(B)/cos(A) = 1.

Aplicando ahora el teorema del coseno al triángulo ABC, tenemos que a((b2 - a2 - c2)/(-2ac))/((a2 - b2 - c2)/(-2bc)) = 2(3 - a2)/(a2 - 5) = 1, y resolviendo la ecuación obtenemos a = √33/3.

domingo, 17 de enero de 2016

Formas de colorear un polígono

Enunciado

Se trata de construir una fórmula, y es casi un trabajo de investigación matemática, por lo que me parece muy complejo.

Lo más lógico es estudiar completamente un caso sencillo, luego un caso un poco más complejo, y luego empezar ya a efectuar hipótesis, para luego comprobarlas.

Empezamos a colorear los vértices de un triángulo (n = 3) sin atender a si sus lados cumplen o no la condición y luego clasificarlos. Como cada vértice puede tener un color entre tres, se presentan 3x3x3 = 27 casos. Llamaré a los colores A, B y C. Los casos son: AAA, AAB, AAC, ABA, ABB, ABC, ACA, ACB, ACC, BAA, BAB, BAC, BBA, BBB, BBC, BCA, BCB, BCC, CAA, CAB, CAC, CBA, CBB, CBC, CCA, CCB, CCC.

De estos, observamos que hay tres casos en los que ningún lado tiene colores diferentes, que no está contemplado en el problema (AAA, BBB y CCC), y de los 24 casos restantes, 18 tienen dos lados con colores diferentes (m = 2) (AAB, AAC, ABA, ABB, ACA, ACC, BAA, BAB, BBA, BBC, BCB, BCC, CAA, CAC, CBB, CBC, CCA y CCB) y 6 tienen los tres lados con colores diferentes (ABC, ACB, BAC, BCA, CAB y CBA). Observa que los lados están entre dos de los vértices (letras), y que la última letra tiene un lado que la une a la primera.

El siguiente caso completo (n = 4) tiene 81 elementos y puede llevar mucho tiempo clasificarlos, así que debemos descartarlo de momento y tratar de contar directamente un caso particular que nos ilumine mejor la forma de contar esta cantidad.

Vamos a estudiar, por ejemplo, el caso n = 7 y m = 4, es decir, un heptágono en el que exactamente cuatro lados tienen extremos de colores diferentes. Si queremos poner un ejemplo, lo primero que haremos será situar qué lados vamos a elegir, por ejemplo, el segundo, el tercero, el quinto y el séptimo. Eso conlleva que el primer y segundo vértice tienen el mismo color, el tercero lo tendrá diferente del segundo, el cuarto diferente del tercero, el quinto igual que el cuarto, el sexto diferente, y el séptimo igual que el sexto pero diferente del primero. En el dibujo, he rodeado con una elipse los vértices que deben ser del mismo color. De esta forma, en realidad sólo debo elegir cuatro colores diferentes a sus vecinos, y los otros tres se colorearán de forma automática. Por ejemplo, puedo elegir AABCCBB.

Entonces, si quiero contar la cantidad de formas en la que puedo hacer esto, se trata de elegir cuatro colores por un lado con la condición de ser diferentes de sus vecinos, y los cuatro lados que quiero que tengan la condición pedida. Por lo menos puedo estudiar por separado ambas elecciones.

El número de elecciones de los lados es un sistema más estudiado. Para el otro habrá que improvisar bastante.

Si has estudiado combinatoria, reconocerás que elegir cuatro lados entre 7 se llama combinaciones de cuatro elementos escogidos entre 7, y sabrás como calcularlos. En el siguiente párrafo razono la cantidad para aquellos que no tengan este concepto.

El primer lado lo selecciono entre 7 posibilidades, el segundo entre los 6 restantes, y así sucesivamente, de forma que tendría, en principio, 7*4*3*2 formas de elegir los cuatro, pero cada elección la estaría contando muchas veces. En efecto, una elección de 4 lado estaría contándola una vez por cada lado que tomara como primer lado (4), multiplicada por una vez cada vez que contara otro como segundo, y así sucesivamente, es decir, la estaría contando 4*3*2*1 veces. Por tanto, el número total de formas diferentes de elegir sería (7*6*5*4)/(4*3*2*1), en total en nuestro ejemplo eso da 35 formas diferentes.

Puede que conozcas la fórmula para este cálculo, es n!/(m!*(n-m)!).

Ahora, debemos elegir los cuatro colores diferentes, es decir, ver de cuantas formas lo podemos hacer. Para el primer color disponemos de 3 posibilidades, pero para el segundo sólo 2, para el tercero otros 2, y el cuarto es mucho más complejo, ya que depende de si el primer y el tercero son iguales o diferentes. Si son iguales, tendré dos formas diferentes de lograrlo, y si son diferentes, sólo una. Para esto, podemos partir del estudio que hemos hecho antes, para el triángulo. Había exactamente 6 casos en que todos los colores eran diferentes cada uno del siguiente, que derivarán en una única elección para el cuarto color. Si el primero y el tercero son iguales sólo eliges dos colores realmente diferentes antes de elegir el cuarto (3*2 posibilidades) y entonces tienes otras 2 de elegir el último, lo que hace un total de 12 posibilidades, es decir, tenemos 18 formas de elegir los colores.

Al final, tendremos 18*35 = 630 coloraciones diferentes para el heptágono con cuatro lados de diferente color en los extremos. No las voy a poner todas, desde luego.

La elección de los lados es sencilla de convertir en una fórmula, pero la selección de colores no. Tendremos que estudiarla más a fondo. Hay que calcular de cuántas formas se pueden conseguir elegir un cierto número de colores entre tres, diferentes cada uno del siguiente y el primero del último.

Además, tendremos que hacerlo a partir de 2. Para 2 son 6 las formas de hacerlo, para 3 ya sabemos que 6 también, y para 4 hemos visto que 18. Veamos para 5 y creemos una fórmula.

Si queremos escoger una cadena de 5 colores con esa condición, podemos partir de las anteriores. Si tomamos una cadena de 4 diferentes (18 formas) y añadimos un color diferente del primero y el último tendremos 18 formas diferentes, las 18 en las que el penúltimo y el primero son distintos. Para las restantes, como sabemos que primero y penúltimo han de ser iguales, partimos de una cadena de 3 diferentes (6 formas), añadimos otra igual que el primero (podemos, porque el tercero es diferente del primero), y luego disponemos de dos posibilidades para el último color, es decir, que tendremos 6*2 = 12 formas más, hasta un total de 30.

Observa que hemos calculado el valor para la cuarta elección a partir de la tercera y la segunda. De ahí se puede sacar una primera fórmula que nos ayude, que sería inductiva (a partir de los números previos). Se trataría de tomar la anterior y sumarle el doble de la anterior de la anterior. Es decir, Cm = Cm - 1 + 2 Cm - 2.

La secuencia vendría a ser 6, 6, 18, 30, 66, 126, ...

Si nos fijamos bien, se parece enormemente a las potencias de 2 (4, 8, 16, 32, 64, 128, ...), sólo que se le suma o resta 2. Esa fórmula se podría poner como 2m + 2*(-1)m.

Para comprobar que es válida, lo demostramos por inducción, ya que 2m - 1 + 2*(-1)m - 1 + 2*(2m - 2 + 2*(-1)m - 2) = 2m - 1 + 2*(-1)m - 1 + 2m - 1 + 4*(-1)m = 2m - 2*(-1)m + 4*(-1)m = 2m + 2*(-1)m, como se quería demostrar.

Por lo tanto, la fórmula para la cantidad de formas de elegir los colores con esa condición, para n y m genéricos, es (n!*(2m + 2*(-1)m))/(m!*(n-m)!).

Como veis, un problema muy largo y complejo para cerrar la olimpiada.