miércoles, 19 de enero de 2011

Triángulos en polígonos regulares (Prob del dia: Miercoles 19 Enero - COM)

Sean $P_1$, $P_2$, $\ldots$, $P_n$ los vértices de un polígono regular de $n$ lados. Determina el número de triángulos no congruentes de la forma $P_iP_jP_k$ donde $i$, $j$ y $k$ son enteros distintos entre $1$ y $n$.

(Básicamente, ¿cuántos triángulos no congruentes se pueden encontrar en un polígono de $n$ lados?)

8 comentarios:

Georges dijo...

Primero nos fijamos que el número de triangulos no congruentes en un poligono de n vertices es igual al número de formas de dividir n en suma de 3 enteros positivos sin que nos importe el orden de estos 3 enteros.

Para ver esto veamos que si tenemos un triangulo con vertices en el poligono podemos asignarle 3 enteros que suman n estos 3 enteros son la cantidad de lados que tienes que recorrer para llegar de un vertice a otro por el poligono, y si tienes 3 enteros que sumen n tambien puedes de la misma forma asignarle un triangulo. Por lo tanto es una funcion biyectiva y son la misma cantidad.

Ahora para ver de cuantas formas podemos dividir a n en 3 enteros positivos sin que nos importe el orden, definamos:
a=ternas de la forma (x,y,z) x,y,z distintos entre si
b=ternas de la forma (x,x,y) x distinto de y
c=ternas de la forma (x,x,x).

Ahora es facil ver usando separadores que el numero de formas de escoger 3 enteros positivos donde si nos importe el orden es ((n-1)en 2) y eso tambien es igual a 6a+3b+c.

Ahora la suma que queremos es a+b+c, y es facil calcular b,c, y a "a" la podemos calcular despejando la formula.

Para calcular b,c veamos que c=1 si 3 divide a n y sino es 0, y b=techo(n/2)-1-c (solo consideras cuantas parejas hay de la forma (x,x,y))

Osea para mas bonito lo puedes ver mod 6 y da que:

6x---3x^2
6x+1--3x^2+x
6x+2---3x^2+2x
6x+3---3x^2+3x+1
6x+4---3x^2+4x+1
6x+5---3x^2+5x+2

Segun yo esta bien, cualquier error diganme.

Manuel Alejandro dijo...

Lo estaba resolviendo, y ya llevaba buena parte, hasta que me surgió la siguiente duda: ¿es el mismo triángulo si lo volteamos?, por ejempo, en un hexágono, ¿P1P3P6=P1P4P6?

Jorge 'Chuck' dijo...

Trazando dos lados, automáticamente determina el tercero.

Como podemos ver, si unimos vértices desde un punto hacia la derecha y les vamos asignando un número natural a partir del 1 dependiendo de la cantidad de vértices que hay entre un vértice y otro del lado. De manera que si recorriendo desde un punto del lado hasta el otro hay k vértices, entonces el número asignado al lado es k+1. De modo que los números de los tres lados suman n.

Si los números son a,b y n-a-b tales que a=<b=<n-a-b entonces con seleccionar a y b el último está determinado, sin importar con qué vértice comencemos.
Como a,b=<n-a-b entonces a+b=<2(n-a-b)
3(a+b)=<2n por lo que a+b=<2n/3 y como a,b son Naturales, a+b=<[2n/3] y 2a=<[2n/3]
Por lo que a=<[n/3]
Contar todas las maneras de escoger a y b de esta manera es lo mismo que contar lo que nos pide el problema. Ya que como a es el menor y mide necesariamente menos de [n/2] los otros lados no pueden medir menos que el que tiene a y por ese lado no hay problemas. Además de que una vez determinado a, el lado con b es de tamaño mayor o igual al de a y menor o igual al último lado, por nuestra construcción.
Para cada valor de a, b puede ser cuando mucho la mitad de lo que queda y tiene que ser mayor o igual a a (por eso restamos a y sumamos uno, porque pierde la opción de tener esos valores) [n-a/2]-a + 1 = [n-3a/2] + 1 (en dicha función los valores que puede tomar b decrecen intercaladamente, en 1 y 2 por lo que se pierden los números con una misma congruencia módulo 3) valores posibles para b y en esto podemos ver cuando “n” es par o impar, su congruencia módulo 3 o no (para ver el valor máximo que a puede tomar a).
Caso 1) 6|n
n=6x con x un natural y a=< 2x, en este caso como 6|n, cuando a=1 b tiene 3x-1 posibles valores, con a=2, b tiene 3x-2 posibles valores, luego si a=3, b tiene 3x-4 posibles valores y así sucesivamente (como lo describí arriba) hasta que cuando a=2x, b puede ser únicamente 2x (tiene 3x-(3x-1) posibles valores) y el último lado igual entonces si contamos el total de posibles valores es igual a la sumatoria de todos los números del 3x-1 al 1 pero debemos quitarle a eso los valores múltiplos de tres del 3x-3 al 3 (donde le restamos a 3x un múltiplo de 3, porque no aparece esa posibilidad para b) entonces es por Gauss:
3x(3x-1)/2 – 3(x(x-1)/2)= (9xˆ2- 3x- 3xˆ2 + 3x)/2 = 3xˆ2
Caso 2) n=1(mod 6)
n=6x+1 con x natural y a=<2x, análogamente al caso anterior vemos que la suma de los valores de b es la sumatoria de todos los enteros desde 3x hasta 1 y debemos quitar los números congruentes a 2 módulo 3 desde 3x-1 hasta 2 (cuando restamos a 3x un número congruente a 1 módulo 3) que por Gauss es:
3x(3x+1)/2 – (3(x(x+1)/2) - (x)) = (9xˆ2 + 3x – 3xˆ2 – 3x)/2 + x= 3xˆ2 + x

Jorge 'Chuck' dijo...

Caso 3) n=2(mod 6)
n=6x + 2 con x natural y a=<2x, de la misma forma que en los casos anteriores la suma de los valores posibles de b es la sumatoria de todos los enteros desde 3x hasta 1 menos los números congruentes a 1 módulo 3 desde 3x-2 hasta 1 y por Gauss es:
3x(3x+1)/2 – (3(x(x+1)/2) - 2(x))= (9xˆ2 + 3x – 3xˆ2 – 3x)/2 + 2x= 3xˆ2 +2x
Caso 4) n=3(mod 6)
n=6x + 3 con x natural y a=<2x + 1, de la misma forma que en los casos anteriores la suma de los valores posibles de b es la sumatoria de todos los enteros desde 3x + 1 hasta 1 menos los números múltiplos de 3 desde 3x hasta 3 y por Gauss es:
(3x+2)(3x+1)/2 – 3(x(x+1)/2)= (9xˆ2 + 9x + 2 - 3xˆ2 - 3x)/2 = 3xˆ2 + 3x + 1
Caso 5) n=4(mod 6)
n=6x + 4 con x natural y a=<2x + 1, de la misma forma que en los casos anteriores la suma de los valores posibles de b es la sumatoria de todos los enteros desde 3x + 1 hasta 1 menos los números congruentes a 2 módulo 3 desde 3x-1 hasta 2 y por Gauss es:
(3x+2)(3x+1)/2 – (3(x(x+1)/2) - (x)) = (9xˆ2 + 9x + 2 – 3xˆ2 – 3x)/2 + x= 3xˆ2 + 4x + 1
Caso 6) n=5(mod 6)
n=6x + 5 con x natural y a=<2x + 1, de la misma forma que en los casos anteriores la suma de los valores posibles de b es la sumatoria de todos los enteros desde 3x +2 hasta 1 menos los números congruentes a 1 módulo 3 desde 3x+1 hasta 1 y por Gauss es:
(3x+2)(3x+3)/2 – (3((x+2)(x+1)/2) - 2(x+1))= (9xˆ2 + 15x + 6 – 3xˆ2 – 9x - 6)/2 + 2x= 3xˆ2 +5x + 2

Leo dijo...

Manuel: Todo es con respecto a congruencia. Como los triángulos que señalas con congruentes, entonces cuentan como el mismo.

Al final puedes ajustar tus cuentas para resolver el otro problema.

Manuel Alejandro dijo...

Denotamos como $f(n)$ el número de triángulos que se pueden formar para el polígono de n lados.
Llamamos longitud de un lado, al número de lados del polígono que le corresponden a un lado de un triángulo.
Observamos que:

$f(3)=1$
$f(4)=1$
$f(5)=2$
$f(6)=3$
$f(7)=4$
$f(8)=5$

Ahora, para cada $n\geq6$, tenemos que:

Si n es par: $f(n)=f(n-3)+\frac{n-2}{2}$
Si n es impar: $f(n)=f(n-3)+\frac{n-1}{2}$
Esto lo comprobamos de la siguiente manera. $f(n-3)$ representa la cantidad de triángulos que se pueden formar con sus lados de longitud mayor o igual a 2 (ya que si hay un triángulo en P(n-3), a todos sus lados le sumamos uno, y corresponde a un triángulo en P(n). Ahora, $\frac{n-2}{2}$ y/o $\frac{n-1}{2}$ representa la cantidad de triángulos que se pueden formar tal que su lado menor es igual a 1. Es fácil notar que la biyección es correcta.

Ahora, notamos que $f(3)=1=\frac{3-1}{2}$, $f(4)=1=\frac{1-1}{2}+\frac{4-2}{2}$, $f(5)=2=\frac{2-2}{2}+\frac{5-1}{2}$, $f(6)=3=\frac{3-1}{2}+\frac{6-2}{2}$, $f(7)=4=\frac{1-1}{2}+\frac{4-2}{2}+\frac{7-1}{2}$, $f(8)=5=\frac{2-2}{2}+\frac{5-1}{2}+\frac{8-2}{2}$.

Ahora, tenemos que:

Si $n\equiv1(mod6)$, tenemos que $f(6k+1)=f(6k-2)+\frac{6k+1-1}{2}=\frac{1-1}{2}+\frac{4-2}{2}+\frac{7-1}{2}+\cdots+\frac{6k+1-1}{2}=\frac{3(0+1+2+3+...+2k)+2k+1-(3k+1)}{2}=\frac{(2k+1)(3k+1)-(3k+1)}{2}=3k^{2}+k$

Si $n\equiv2(mod6)$, tenemos que $f(6k+2)=f(6k-1)+\frac{6k+2-2}{2}=\frac{2-2}{2}+\frac{5-1}{2}+\frac{8-2}{2}+\cdots+\frac{6k+2-2}{2}=\frac{3(0+1+2+...+2k)+2(2k+1)-(3k+2)}{2}=\frac{(2k+1)(3k+2)-(3k+2)}{2}=3k^{2}+2k$

Si $n\equiv3(mod6)$, tenemos que $f(6k+3)=f(6k)+\frac{6k+3-1}{2}=\frac{3-1}{2}+\frac{6-2}{2}+\frac{9-1}{2}+\cdots+\frac{6k+3-1}{2}=\frac{3(1+2+3+...+2k+1)-(3k+1)}{2}=\frac{(k+1)(6k+3)-(3k+1)}{2}=3k^{2}+3k+1$

Si $n\equiv4(mod6)$, tenemos que $f(6k+4)=f(6k+1)+\frac{6k+4-2}{2}=3k^{2}+k+3k+1=3k^{2}+4k+1$

Si $n\equiv5(mod6)$, tenemos que $f(6k+5)=f(6k+2)+\frac{6k+5-1}{2}=3k^{2}+2k+3k+2=3k^{2}+5k+2$

Si $n\equiv6(mod6)$, tenemos que $f(6k)=f(6k-3)+\frac{6k-2}{2}=3(k-1)^{2}+3(k-1)+1+3k-1=3(k^{2}-2k+1+k-1+k)=3k^{2}$

Y ya lo habíamos probado para el menor caso en cada residuo módulo 6, así que funciona.

DANIELIMO dijo...

por simetría es fácil ver uqe para cualquier triangulo ABC en el poligono, podemos tomarnos uno conguente que tenga como vertices los puntos PQR(con P un vertice fijo del poligono y Q,R otros dos de los vertices), por lo tanto basta contar los triagulos congruentes que tengan como vertice a P(en total hay n-1 en 2 triangulos con vetice en P), hay 3 casos:

1 ABC equilatero solo abra un equilatero dentro del poligono con vertice en P y sera si n=3k

2 ABC isosceles (hay parte entera de (n-1)/2 triangulos isoscelesno congruentes y con vertice en P, para contarlos vemos que P no sea un vertice de la base y queda fácil la cuenta)
notamos que para cada uno de estos habra exactamente 3 tiangulos congruentes con ABC y con vertice en P [cuando P no esta en la base, solo hay uno, cuando P es parte de la base y el otro punto de la base queda en sentido de las manecillas del reloj, y cuando queda al contrario, (q es su reflejado con respecto a P y el centro del poligono)]

3 ABC escaleno, que para cada uno de estos hay 6 triangulos congruentes con vertice en P [cuando P coincide con A hay 2,(el punto que coincida con B este en direccion derecha de A, o cuando este en direccion izquierda) y analogamente hay otros 2 para B y 2 mas para C]

Ahora solo hay que contar, vemos si hay equilatero, checamos la cantidad de isosceles distintos(restando 1 si hay equilatero),y para calcular la cantidad de escalenos distintos es mas facil ver la cantidad total de triangulos, restarle 1 si hay equilatero, y restale 3 veces la cantidad de isosceles distintos, luegodividir entre 6, y sumar las cantidades. Checamos 6 casos dependiendo de la congruencia modulo 6 de n

si n=6k
hay un equilatero
3k-2 isosceles distintos
y 3k^2 -3k +1 escalenos
en total 3k^2

si n=6k+1
no hay equilatero
3k isosceles distintos
y 3k^2 -2k escalenos
en total 3k^2 +k

si n=6k+2
no hay equilatero
3k isosceles distintos
y 3k^2 -k escalenos
en total 3k^2 +2k

si n=6k+3
hay un equilatero
3k isosceles distintos
y 3k^2 escalenos
en total 3k^2 + 3k +1

si n=6k+4
no hay equilatero
3k+1 isosceles distintos
y 3k^2 +k escalenos
en total 3k^2 +4k+1

si n=6k+5
no hay equilatero
3k+2 isosceles distintos
y 3k^2 +2k escalenos
en total 3k^2 +5k +2

angel95 dijo...

un triangulo formado con los vertices divide en tres regiones al poligono, cada region tiene L numero de lados, sean estos L_1, L_2, L_3, es facil ver que L_1+L_2+L_3=n, ademas que triangulo congruentes generan L`s iguales, ademas que si hay tres naturales que sumen n, se puede formar un triangulo en el poligono con esas "medidas". Ademas si dos triangulos generan regiones con el mismo numero de lados, estos son congruentes, por lo que el problema se traduce a encontrar todos los conjuntos de 3 numeros naturales que sumen n.
para esto hay 3 casos
caso 1
tres numeros iguales, hay de este tipo solo si n es multiplo de 3
Caso 2
dos numeros iguales y uno diferente, de estos hay (piso de (n/2) menos 1) si n es par, y (piso de (n/2) si n es impar. en ambos casos se les resta el caso 1, ya que se repetiria el caso equilatero.
caso 3
tres numeros diferentes, la cantidad es la sumatoria desde i=1.
, hasta el piso de n/3, menos 1. del techo de n-i/2.
haciendo los casos modulo 6 da
0=3x^2
1=3x^2+x
2=3x^2+2x
3=3x^2+3x+1
4=3x^2+4x+1
5=3x^2+5x+2

Publicar un comentario