Matematicas para la Olimpiada

45 %
55 %
Information about Matematicas para la Olimpiada

Published on June 20, 2007

Author: joemmanuel

Source: slideshare.net

Introducción a los algoritmos Algunas matemáticas necesarias… Joemmanuel Ponce Galindo

Introducción La computación surgió como apoyo para resolver problemas de carácter matemático que de haberse hecho a mano una persona seguramente hubiera tardado más años de los que viviría resolviendo el problema.

La computación surgió como apoyo para resolver problemas de carácter matemático que de haberse hecho a mano una persona seguramente hubiera tardado más años de los que viviría resolviendo el problema.

Introducción No es de extrañarnos que comúnmente tengamos que resolver problemas relacionados con matemáticas. La computación es una rama de las matemáticas.

No es de extrañarnos que comúnmente tengamos que resolver problemas relacionados con matemáticas.

La computación es una rama de las matemáticas.

Temas básicos Divisibilidad Números Primos Factorización Máximo Común Divisor Mínimo Común Múltiplo Conversión de Bases

Divisibilidad

Números Primos

Factorización

Máximo Común Divisor

Mínimo Común Múltiplo

Conversión de Bases

DIVISIBILIDAD

Divisibilidad Sean n y m dos números naturales. Decimos que n divide a m cuando existe otro entero positivo tal que: Entonces n es un divisor de m.

Sean n y m dos números naturales. Decimos que n divide a m cuando existe otro entero positivo tal que:

Entonces n es un divisor de m.

Divisibilidad La siguiente notación es empleada comúnmente: indica que n es divisor de m indica que n no divide a m

La siguiente notación es empleada comúnmente:

indica que n es divisor de m

indica que n no divide a m

Divisibilidad Si n no divide a m , entonces se cumple que existen q y r únicos tal que: Con A q le llamamos cociente y a r residuo.

Si n no divide a m , entonces se cumple que existen q y r únicos tal que:

Con

A q le llamamos cociente y a r residuo.

Propiedades de divisibilidad n|n siempre se cumple Si n|m y m|n entonces n=m Si n|m y m|s entonces n|s Si n|m entonces n|k(m). n divide a todos sus múltiplos

n|n siempre se cumple

Si n|m y m|n entonces n=m

Si n|m y m|s entonces n|s

Si n|m entonces n|k(m). n divide a todos sus múltiplos

NÚMEROS PRIMOS

Números primos Dentro de las ciencias computacionales, el estudio de los números primos es de suma importancia en muchos temas. Un ejemplo es los algoritmos de encriptación de datos como el RSA que se basa en el producto de números primos grandes (mayores que 10 100 )

Dentro de las ciencias computacionales, el estudio de los números primos es de suma importancia en muchos temas.

Un ejemplo es los algoritmos de encriptación de datos como el RSA que se basa en el producto de números primos grandes (mayores que 10 100 )

Números primos Un número primo se define como aquel número que es divisible solamente por el 1 y por sí mismo. Por ejemplo: 3, 7, 11, 311 son ejemplos de números primos. Números como el 4,8,32 no son números primos. Los números que no son primos se denominan compuestos.

Un número primo se define como aquel número que es divisible solamente por el 1 y por sí mismo.

Por ejemplo: 3, 7, 11, 311 son ejemplos de números primos.

Números como el 4,8,32 no son números primos.

Los números que no son primos se denominan compuestos.

Ejercicio 1 Escribe un método esPrimo que reciba como parámetro n, y devuelva true si n es un número primo. De lo contrario regresar false. Condiciones : Tu programa deberá correr en 1 segundo o menos. Recuerda el uso del operador % x%y = 0 si y divide a x

Escribe un método esPrimo que reciba como parámetro n, y devuelva true si n es un número primo.

De lo contrario regresar false.

Condiciones :

Tu programa deberá correr en 1 segundo o menos.

Recuerda el uso del operador %

x%y = 0 si y divide a x

Ejercicio 1… primer acercamiento Sin duda el primer acercamiento es un algoritmo O(n): int i; for (i=2;i<n;i++) if (n%i==0) return false ; return true ;

Sin duda el primer acercamiento es un algoritmo O(n):

int i;

for (i=2;i<n;i++)

if (n%i==0)

return false ;

return true ;

Ejercicio 1… primer acercamiento Sin embargo, necesitamos algo mucho mejor que O(n) para resolver 2147483647 en menos de 1 segundo, que es nuestro peor caso (el número primo más grande en el rango de n).

Sin embargo, necesitamos algo mucho mejor que O(n) para resolver 2147483647 en menos de 1 segundo, que es nuestro peor caso (el número primo más grande en el rango de n).

Ejercicio 1… Segundo acercamiento Pregunta: ¿Hasta dónde tenemos que revisar para asegurarnos que no necesitamos revisar más?

Pregunta:

¿Hasta dónde tenemos que revisar para asegurarnos que no necesitamos revisar más?

Ejercicio 1… Segundo acercamiento Respuesta:

Respuesta:

Ejercicio 2... Implementa un algoritmo de menor complejidad para resolver el problema anterior.

Implementa un algoritmo de menor complejidad para resolver el problema anterior.

Ejercicio 2 if (n<=1) return true; if (n==2) return true; if (n%2==0) return false; int i; int tope=(int)Math.sqrt(n); for (i=3;i<=tope;i+=2) if (n%i==0) return false ; return true ;

if (n<=1)

return true;

if (n==2)

return true;

if (n%2==0)

return false;

int i;

int tope=(int)Math.sqrt(n);

for (i=3;i<=tope;i+=2)

if (n%i==0)

return false ;

return true ;

Ejercicio 3 Escribe un método primos que reciba un entero n (n<1’000,000) como parámetro y que escriba todos los números primos del 1 al n

Escribe un método primos que reciba un entero n (n<1’000,000) como parámetro y que escriba todos los números primos del 1 al n

Ejercicio 3… primer acercamiento El primer acercamiento es llamar un millón de veces a nuestra función esPrimo

El primer acercamiento es llamar un millón de veces a nuestra función esPrimo

La criba de Eratóstenes La manera más eficiente de encontrar todos los primos pequeños fue propuesta por Eratóstenes, un matemático griego. Su idea fue poner en una lista todos los enteros menores a n y borrar secuencialmente los múltiplos de los primos menores o iguales a la raíz cuadrada de n. Después de este procedimiento sólo los números primos quedarán no tachados en la lista.

La manera más eficiente de encontrar todos los primos pequeños fue propuesta por Eratóstenes, un matemático griego.

Su idea fue poner en una lista todos los enteros menores a n y borrar secuencialmente los múltiplos de los primos menores o iguales a la raíz cuadrada de n.

Después de este procedimiento sólo los números primos quedarán no tachados en la lista.

La criba de Eratóstenes - Ejemplo Supongamos n=15 Primero tenemos la lista de los 15 números: Tomamos el primer número y tachamos sus múltiplos… 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Supongamos n=15

Primero tenemos la lista de los 15 números:

Tomamos el primer número y tachamos sus múltiplos…

La criba de Eratóstenes - Ejemplo Ahora tomamos el siguiente número no tachado, 3, y tachamos sus múltiplos… El 4 es mayor que la raíz cuadrada de 15, así que no tiene sentido revisarlo.

Ahora tomamos el siguiente número no tachado, 3, y tachamos sus múltiplos…

El 4 es mayor que la raíz cuadrada de 15, así que no tiene sentido revisarlo.

La criba de Eratóstenes -Ejemplo Podemos observar que han quedado no tachados los números primos menores que 15

Podemos observar que han quedado no tachados los números primos menores que 15

Ejercicio 4 Implementa la Criba de Eratóstenes.

Implementa la Criba de Eratóstenes.

Ejercicio 4 Para implementar la Criba de Eratóstenes necesitaremos un arreglo de booleanos donde arreglo en la posición i será true sí i es número primo. De lo contrario, el arreglo en la posición i será false.

Para implementar la Criba de Eratóstenes necesitaremos un arreglo de booleanos donde arreglo en la posición i será true sí i es número primo. De lo contrario, el arreglo en la posición i será false.

Ejercicio 4 - Criba void criba( int MAX) { int i,j; for (i=0;i<MAX;i++) primes[i] = 1; for (i=2;i<=(int)sqrt(MAX);i++) if (primes[i]) for (j=i;j*i<MAX;j++) primes[i*j] = 0; }

void criba( int MAX) {

int i,j;

for (i=0;i<MAX;i++) primes[i] = 1;

for (i=2;i<=(int)sqrt(MAX);i++)

if (primes[i])

for (j=i;j*i<MAX;j++)

primes[i*j] = 0;

}

FACTORIZACION

Teorema Fundamental de la Aritmética Cualquier número positivo puede ser expresado como producto de números primos de una única manera. El orden de los factores no altera el producto.

Cualquier número positivo puede ser expresado como producto de números primos de una única manera.

El orden de los factores no altera el producto.

¿Y el 1? El número 1 no es ni primo ni número compuesto. 1 no es compuesto porque no tiene dos divisores diferentes. Y si el 1 fuera primo, entonces, el número 10 por ejemplo, tiene dos diferentes representaciones como producto de primos: 10=5(2)(1) 10=5(2) Lo cual contradice el Teorema Fundamental de la Aritmética.

El número 1 no es ni primo ni número compuesto. 1 no es compuesto porque no tiene dos divisores diferentes. Y si el 1 fuera primo, entonces, el número 10 por ejemplo, tiene dos diferentes representaciones como producto de primos:

10=5(2)(1)

10=5(2)

Lo cual contradice el Teorema Fundamental de la Aritmética.

Teorema de Euclides La cantidad de números primos es infinita. Para demostrar esto, consideremos sólo n números primos, p 1 , p 2 , p 3 …p n . Pero no hay un número primo entre ellos que divida a: Así que N no puede ser compuesto, por lo tanto es número primo.

La cantidad de números primos es infinita.

Para demostrar esto, consideremos sólo n números primos, p 1 , p 2 , p 3 …p n . Pero no hay un número primo entre ellos que divida a:

Así que N no puede ser compuesto, por lo tanto es número primo.

Ejercicio 5 – Conjetura de Goldbach Para cualquier entero (n>3) existen dos números primos, p 1 y p 2 tales que p 1+ p 2 =n. Tu tarea es encontrar todas las parejas (p 1, p 2 ) con que cumplan la condición para cualquier n par ( ) Por ejemplo, para n=10 tenemos 2 parejas, 10=5+5 y 10=3+7

Para cualquier entero (n>3) existen dos números primos, p 1 y p 2 tales que p 1+ p 2 =n. Tu tarea es encontrar todas las parejas (p 1, p 2 ) con que cumplan la condición para cualquier n par ( )

Por ejemplo, para n=10 tenemos 2 parejas, 10=5+5 y 10=3+7

Ejercicio 6 – Tamaño de Mantas (Topcoder SRM 304 DIV2 250p) Las mantas se venden en varios tamaños. De hecho, podemos encontrar mantas de cualquier ancho y alto entero, excepto que no hay mantas que tengan diferentes tamaños de ancho y alto que sean pares ambos números. Por ejemplo, podemos encontrar una manta de 4x4 pero no una de 2x4. Queremos saber cuantas mantas diferentes podemos escoger dada el área.

Las mantas se venden en varios tamaños. De hecho, podemos encontrar mantas de cualquier ancho y alto entero, excepto que no hay mantas que tengan diferentes tamaños de ancho y alto que sean pares ambos números. Por ejemplo, podemos encontrar una manta de 4x4 pero no una de 2x4. Queremos saber cuantas mantas diferentes podemos escoger dada el área.

Ejercicio 6 – Tamaño de Mantas (Topcoder SRM 304 DIV2 250p) No cuentes la misma manta dos veces, una manta de 6x9 es la misma que una de 9x6 y debe ser contada sólo una vez.

No cuentes la misma manta dos veces, una manta de 6x9 es la misma que una de 9x6 y debe ser contada sólo una vez.

Ejercicio 7 – Primos Ingenieriles (Topcoder SRM 181 DIV2 1000p) Un número primo es un número que solo es divisible por 1 y por sí mismo. Se ha demostrado que un algoritmo de tiempo polinomial sublinear determina la primalidad de un número con certeza, no como las pruebas probabilísticas, pero es bastante complicado. Debe existir un mejor camino….

Un número primo es un número que solo es divisible por 1 y por sí mismo. Se ha demostrado que un algoritmo de tiempo polinomial sublinear determina la primalidad de un número con certeza, no como las pruebas probabilísticas, pero es bastante complicado. Debe existir un mejor camino….

Ejercicio 7 – Primos Ingenieriles (Topcoder SRM 181 DIV2 1000p) ..en ingeniería no son muy requeridas las soluciones exactas, sólo buenas aproximaciones. Entonces, un primo ingenieril de orden N es cualquier número que no es divisible por los primeros N números primos, dado que los primos más pequeños son mas fáciles de recordar: 2,3,5 y asi sucesivamente. Nota que 1 no es considerado como primo en este caso… Dado N entero, tu programa debe regresar el primo ingenieril más pequeño de orden N que no es primo.

..en ingeniería no son muy requeridas las soluciones exactas, sólo buenas aproximaciones. Entonces, un primo ingenieril de orden N es cualquier número que no es divisible por los primeros N números primos, dado que los primos más pequeños son mas fáciles de recordar: 2,3,5 y asi sucesivamente. Nota que 1 no es considerado como primo en este caso…

Dado N entero, tu programa debe regresar el primo ingenieril más pequeño de orden N que no es primo.

Factorización ¿Cómo se podría encontrar la descomposición en números primos de un número N ? :

¿Cómo se podría encontrar la descomposición en números primos de un número N ? :

Factorización La técnica más simple de factorización representa un método de “fuerza bruta” en donde vamos a intentar dividir a n por todos los números i no mayores a la raíz cuadrada de n .

La técnica más simple de factorización representa un método de “fuerza bruta” en donde vamos a intentar dividir a n por todos los números i no mayores a la raíz cuadrada de n .

Factorización void factorizar(int n) { int i; for (i=2;i<=(int)sqrt(n);i++) { while (n % i == 0) { System.out.println(i); n = n/i; } } if (n > 1) printf (&quot;%d&quot;,n); }

void factorizar(int n) {

int i;

for (i=2;i<=(int)sqrt(n);i++) {

while (n % i == 0) {

System.out.println(i);

n = n/i;

}

}

if (n > 1)

printf (&quot;%d&quot;,n);

}

MÁXIMO COMÚN DIVISOR

El MCD El Máximo Común Divisor (MCD) de dos números, n y m, es el número más grande tal que divide tanto a n como a m. Por ejemplo, MCD(205,10)=5 Es importante notar que siempre existe el MCD de dos números ya que el 1 divide a todos los naturales.

El Máximo Común Divisor (MCD) de dos números, n y m, es el número más grande tal que divide tanto a n como a m. Por ejemplo, MCD(205,10)=5

Es importante notar que siempre existe el MCD de dos números ya que el 1 divide a todos los naturales.

El MCD Un algoritmo para calcular el MCD podría ser el siguiente, recorremos con un ciclo a partir del mínimo de n y m hacia abajo hasta encontrar el primer divisor de ambos. Este entonces será el más grande. for (int i=min(n,m); i>=1; i--) if (n%i==0 && m%i==0) return i;

Un algoritmo para calcular el MCD podría ser el siguiente, recorremos con un ciclo a partir del mínimo de n y m hacia abajo hasta encontrar el primer divisor de ambos. Este entonces será el más grande.

for (int i=min(n,m); i>=1; i--)

if (n%i==0 && m%i==0)

return i;

El MCD Existe un método más rápido llamado el Algoritmo de Euclides, el cual itera sobre dos números hasta encontrar un 0.

Existe un método más rápido llamado el Algoritmo de Euclides, el cual itera sobre dos números hasta encontrar un 0.

El MCD Como ejemplo, encontremos el MCD de 205 y 10. Empezaremos a expresar el número mayor (205) en términos del menor (10) más un residuo: 205= ( 10 x20)+5 Ahora hacemos lo mismo con el 10 y el 5: 10= ( 5 x2)+0 El número que haga que se regrese un 0 como residuo será nuestro MCD. Por lo tanto, el 5 es el MCD de 205 y 10.

Como ejemplo, encontremos el MCD de 205 y 10. Empezaremos a expresar el número mayor (205) en términos del menor (10) más un residuo:

205= ( 10 x20)+5

Ahora hacemos lo mismo con el 10 y el 5:

10= ( 5 x2)+0

El número que haga que se regrese un 0 como residuo será nuestro MCD. Por lo tanto, el 5 es el MCD de 205 y 10.

Ejercicio 8 Implementa el Algoritmo de Euclides. Nota: la versión recursiva es más corta.

Implementa el Algoritmo de Euclides.

Nota: la versión recursiva es más corta.

Ejercicio 8 – Algoritmo de Euclides – Versión Recursiva public int MCD(int n , int m ) { if (m>n) return MCD(m,n); if (m==0) return n; return MCD(m,n%m); }

public int MCD(int n , int m )

{

if (m>n)

return MCD(m,n);

if (m==0)

return n;

return MCD(m,n%m);

}

MÍNIMO COMÚN MÚLTIPLO

El MCM El Mínimo Común Múltiplo de dos números n y m es el menor número que es múltiplo tanto de m como de n. Por ejemplo, el MCM de 4 y 6 es 12

El Mínimo Común Múltiplo de dos números n y m es el menor número que es múltiplo tanto de m como de n.

Por ejemplo, el MCM de 4 y 6 es 12

El MCM El MCM puede ser encontrado usando el MCD con la siguiente propiedad:

El MCM puede ser encontrado usando el MCD con la siguiente propiedad:

Ejercicio 9 – OIEG Escribe un programa que dadas n<100 fracciones expresadas calcule la suma y la exprese como una fracción irreducible. Ejemplo: Entrada Salida 3 1 5 3 2 3 10 19 10

Escribe un programa que dadas n<100 fracciones expresadas calcule la suma y la exprese como una fracción irreducible.

Ejemplo:

CONVERSIÓN DE BASES

Conversión de Bases Dado que en la computación es muy común el uso del sistema binario como representación de estados encendidos y apagados, también es muy común la necesidad de convertir de este sistema a decimal y viceversa.

Dado que en la computación es muy común el uso del sistema binario como representación de estados encendidos y apagados, también es muy común la necesidad de convertir de este sistema a decimal y viceversa.

Conversión de Bases Considera el número decimal12345. Lo podemos expresar de la siguiente manera: Observa como el exponente de la base ( 10 ) va aumentando en una unidad conforme avanzamos de derecha a izquierda en el número.

Considera el número decimal12345. Lo podemos expresar de la siguiente manera:

Observa como el exponente de la base ( 10 ) va aumentando en una unidad conforme avanzamos de derecha a izquierda en el número.

Conversión de Bases En el sistema binario ocurre lo mismo. Considera el número 111011, de igual manera lo podemos expresar así: Lo que acabamos de realzar es una conversión de base binario a base decimal. Para cualquier base aplica la misma metodología.

En el sistema binario ocurre lo mismo. Considera el número 111011, de igual manera lo podemos expresar así:

Lo que acabamos de realzar es una conversión de base binario a base decimal. Para cualquier base aplica la misma metodología.

Ejercicio 10 Haga un programa que convierta de un entero en base B ( ) a un número decimal.

Haga un programa que convierta de un entero en base B ( ) a un número decimal.

Ejercicio 10 int aDecimal(int n, int b){ int resultado=0; int multiplicador; while (n>0) { resultado+=(n%10)*multiplicador; multiplicador*=b; n/=10; } return result; }

int aDecimal(int n, int b){

int resultado=0;

int multiplicador;

while (n>0) {

resultado+=(n%10)*multiplicador;

multiplicador*=b;

n/=10;

}

return result;

}

Conversión Decimal > Otra base Para convertir desde un número decimal a cualquier otra base se sigue este algoritmo. Si queremos convertir el 23 a base 2: Tomamos los residuos y nos queda el número 10111 binario, que en decimal equivale al 23.

Para convertir desde un número decimal a cualquier otra base se sigue este algoritmo. Si queremos convertir el 23 a base 2:

Tomamos los residuos y nos queda el número 10111 binario, que en decimal equivale al 23.

Conversión Decimal > Otra base Para convertir a cualquier otra base solo se sustituye el 2 en el procedimiento anterior por la base b.

Para convertir a cualquier otra base solo se sustituye el 2 en el procedimiento anterior por la base b.

Ejercicio 11 Implementa el algoritmo anterior. Convierte un número decimal N a cualquier base B

Implementa el algoritmo anterior. Convierte un número decimal N a cualquier base B

Ejercicio 11 int decimalAOtraBase(int n, int b){ int resultado=0; int multiplicador; while (n>0) { resultado+=(n%b)*multiplicador; multiplicador*=10; n/=b; } return result; }

int decimalAOtraBase(int n, int b){

int resultado=0;

int multiplicador;

while (n>0) {

resultado+=(n%b)*multiplicador;

multiplicador*=10;

n/=b;

}

return result;

}

Add a comment

Related presentations

Related pages

Olimpiada Mexicana de Matemáticas - ommenlinea.org

Creatividad e ingenio para la resolución de problemas. Inicio; Acerca ... el entrenamiento Pre-Ibero en preparación para la XXXI Olimpiada Iberoamericana ...
Read more

Material para Entrenamiento - Entrenamientos de ...

Para la formación de clubes capacitamos profesores de la misma escuela o bien asignamos ... Información General sobre la Olimpiada de Matematicas.
Read more

Material | Olimpiada de Matemáticas en Guanajuato

Material sobre geometría, visto durante el entrenamiento del 28 de Marzo de la Olimpiada ... (Olimpiada de Matemáticas para ... Olimpiada-de-Matematicas ...
Read more

OMM - Problemas

A continuación se presenta una selección de problemas introductorios para la Olimpiada Mexicana de Matematicas:
Read more

Olimpiada Panameña de Matemática | Facebook

Olimpiada Panameña de Matemática. 174 likes · 1 talking about this. La Olimpiada Panameña de Matemática (OPM) busca fomentar el estudio y el interés ...
Read more

Olimpiada de Matemática: Problemas y Soluciones para Descargar

Un Pequeño Manual para la Resolución de Problemas. (420 Kb, zip) 1. Miscelánea de problemasy sus soluciones. 2. Número natural y entero ...
Read more

Problemas para la 21a Olimpiada Mexicana de Matem´aticas

Problemas para la 21a Olimpiada Mexicana de Matem´aticas (Problemas Introductorios) ... La Olimpiada Mexicana de Matematicas consta de tres etapas:
Read more

Entrenamientos de Matemáticas en Nuevo León

Para la formación de clubes capacitamos profesores de la ... Información General sobre la Olimpiada de Matematicas. ... Historia de la Olimpiada en ...
Read more

OLIMPIADA ESTATAL DE MATEMÁTICAS PARA ALUMNOS DE SECUNDARIA

OLIMPIADA ESTATAL DE MATEMÁTICAS PARA ALUMNOS DE SECUNDARIA Primer Examen de Selección 1° de marzo de 2008 NIVEL 2 (2° y 3° de Secundaria)
Read more

Olimpiada Mexicana de Matemáticas – Canguro matemático

Los exámenes que se apliquen en las escuelas no tendrán validez oficial para la Olimpiada; ... para la resolución de problemas .
Read more