Hola

´ Olimpiada Mexicana de Matematicas Notas Introductorias
Veracruz Diciembre de 2004

´ndice general I
1. Combinatoria 1.1. Permutaciones y Combinaciones . . . . . . . . . . . . . . . 2. Teor´a de Numeros ı ´ 2.1. Los enteros . . . . . . . 2.2. Propiedad de Tricotom´a ı 2.3. Divisibilidad . . . . . . . 2.4. Primos . . . . . . . . . . ´ 2.5. Algoritmo de la Division 2.6. Sucesiones . . . . . .. 3. Geometr´a ı 3.1. Rectas coincidentes . . ´ 3.2. Angulos . . . . . . . . . ´ 3.3. Triangulos . . . . . . . . 3.4. Criterios de Semejanza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 13 13 14 14 16 18 22 23 23 25 26 28

1

Cap´tulo 1 ı Combinatoria
1.1. Permutaciones y Combinaciones
´ Definicion 1. Dado n ∈ N denotaremos por n! al producto de todos los numeros naturales menores o iguales que n; esto es, ´ n! = n · (n − 1) · (n− 2) · . . . · 3 · 2 · 1 ´ Definicion 2. 0! = 1 Principio 1. Fundamental de Conteo (P.F.C.) Si existen m formas de que ocurra un evento A y n formas de que ocurra otro evento B distinto; el total de formas en que pueden ocurrir A y B juntos es m · n. Ejemplo 1. Considere las ciudades A, B, C y D como se indica en la figura. Para ir de la ciudad A a la ciudad B existen 3 caminos, de B a ´ C hay 4caminos y de C a D solamente se tienen 2 caminos. Calcule el numero de rutas posibles para ir de A a D pasando por B y C y regresar ´ sin usar alguno de los caminos utilizados al ir de A a D.

A

B
2

C

D

1.1. PERMUTACIONES Y COMBINACIONES

´ Solucion. Por el Principio Fundamental de conteo, tenemos que las rutas posibles para ir de A a D son el numero de caminos para ir de A a ´ B porel numero de caminos para ir de B a C por el numero de caminos ´ ´ para ir de C a D; esto es: A −→ D = 3 · 4 · 2 = 24 Ahora, como no podemos ocupar el mismo camino que esogimos para ir de A a D para regresar, tenemos que nos queda 1 camino para regresar de D a C, 3 caminos para regresar de C a B y 2 caminos para regresar de B a A; asi, A ←− D = 2 · 3 · 1 = 6 ´ Finalmente, usando una vez mas elPrincipio Fundamental de Conteo, tenemos que las maneras en que podemos ir de A a D y regresar sin usar el mismo camino son 144 rutas. ´ Definicion 3. Un arreglo de objetos en un orden determinado se llama ´ una permutacion. Ejemplo 2. Si tenemos un conjunto de tres elementos {a, b, c}; determinar el numero de permutaciones de esos tres elementos si no se repiten ´ objetos.

3

2

1

´ ´Solucion. Pensemos en el arreglo de los tres elementos en funcion de los lugares; es decir, cada arreglo consta de tres lugares; en el primero, podemos colocar cualquiera de los tres elementos que tenemos; en el segundo ´ lugar solo podemos colocar dos elementos (pues ya se ha colocado uno ´ en el lugar anterior) y finalmente en el ultimo lugar solo podemos colo´ car un elemento; as´, se tiene que,aplicando el Principio Fundamental de ı ´ Conteo, la solucion es 6 permutaciones. Teorema 1. El total de formas en que se pueden permutar n objetos tomados de n en n es n Pn = n! OMM Veracruz 3

1.1. PERMUTACIONES Y COMBINACIONES

´ Teorema 2. El numero de permutaciones de n objetos en k lugares esta da´ do por n! n Pk = (n − k)! para k ≤ n. ´ Demostracion. Volvamos a pensar en las permutacionescomo acomodar n objetos en k lugares.

n
Es claro entonces que

n-1

n-k+1

n Pk = n · (n − 1) · . . . · (n − k + 1) n · (n − 1) · . . . · (n − k + 1) · (n − k) . . . · 2 · 1 = (n − k)! n! = (n − k)!

Ejemplo 3. De cuantas formas pueden sentarse 4 personas en un cuarto con nueve sillas diferentes? ´ Solucion. Este problema lo podemos pensar de la iguiente manera: la primera persona...