Matemática Discreta

Ingeniería Técnica en Informática

de Sistemas y Gestión

ESCET

Prácticas y problemas resueltos con Maple V

Práctica 1

Introducción a la
PROGRAMACIÓN EN MAPLE

Introducción

En la primera práctica de Bases de Matemáticas se han introducido los rudimentos de Maple (primeros comandos, sintaxis básica...), en esta práctica introduciremos las nociones elementales para poder programar con Maple.

El objetivo es que tras esta práctica y un poco de ejercicio por parte del alumno se puedan desarrollar los primeros y elementales procedimientos en maple.

Tipos de datos fundamentales

Para programar en Maple, es fundamental manejar los tipos básicos de datos, como son por ejemplo secuencia , lista  y conjunto , sus características y qué tipos de comandos se pueden aplicar a qué tipo de datos. No entraremos en otros tipos de datos como matrices y arrays. En la ayuda se puede leer la información sobre cada uno de los tipos de datos.

Secuencias

El tipo de datos más básico es la secuencia, una colección ordenada de objetos de Maple separados por comas .

>	sec1:=4,Pi,7.5,E,{1,2,3},x->3*x^2;

Se puede introducir cualquier tipo de objetos en una secuencia. Observa que entre los datos de la secuencia de arriba hay números, símbolos, conjuntos...

Puedes acceder a sus elementos escribiendo el lugar que ocupan en la secuencia entre corchetes:

Así por ejemplo el segundo elemento de sec1  es pi.

>

sec1[2];

El quinto es un conjunto:

>

sec1[5];

El sexto parece una función:

>

sec1[6];

 Mira ahora más detalles en la ayuda para secuencias.

Detente sobre la ayuda o vuelve sobre ella, es importante ir entendiendo bien los conceptos.

Continuar aquí

Como habrás visto en la ayuda, dos operadores importantes para la generación de secuencias son $  y seq :

Por ejemplo, para construir una secuencia de 10 ceros se puede escribir:

>

0$10;

Para construir la secuencia de los 20 primeros números impares:

>	seq(2*i-1,i=1..20);

O los 10 primeros múltiplos de 3:

>	seq(3*i,i=1..10);

Mira la ayuda para el comando seq .

Ejercicios.

Después de haber leído detenidamente  la ayuda para secuencias, deberías ser capaz de responder a las siguientes preguntas acerca de la siguiente secuencia:

>	sec1:=4,8,13,{Pi,E,I},seq([k,k+2],k=6..18);

(1) ¿ Qué comando te devuelve el séptimo elemento de sec1?

>

>

>

(2)   Escribe un comando que devuelva una secuencia con once palabras `bien`.

>

>

>

(3) Otra manera de hacer esto es....

>

>

>

(4)   Haz una secuencia formada por los cubos X^3 de números naturales que verifican X^3<1000.

>

>

Listas

Una lista  es una secuencia contenida dentro de corchetes []. Tanto en secuencias como en listas se pueden repetir elementos, y el orden en el que se escriben los elementos es importante.

>	sec1:=seq(i^4,i=1..5); lista1:=[seq(i^4,i=1..5)];

Dada una lista, puedes acceder a la secuencia de sus elementos mediante el comando op :

>	op(lista1);

Para añadir elementos al final de una secuencia, basta escribir una coma y después los elementos que queremos añadir. Pr ejemplo podemos añadir dos a'es al final de la secuencia sec1 :

>	sec2:=sec1,a,a;

Para añadir elementos al final de una lista, hay que extraer la secuencia de sus elementos, añadir los elementos nuevos, y volver a hacer una lista del resultado:

>	lista2:=[op(lista1),muchos,mas];

Para acceder a los elementos de una lista, se hace de la misma manera que para secuencias. El número de elementos de una lista se puede contar con el comando nops.

>	lista2[2]; nops(lista2);

>

Para sustituir elementos en una lista se usa el comando subsop

>	meses:=[enero, febrero, marzo, abril, mayo]:

>	subsop(2=junio,meses);

>	subsop(3=febrero,meses);

Y sirve para borrar elementos de una lista, sustituyendo por NULL

>	subsop(1=NULL,meses);

Ejercicios

Como en el caso de las secuencias, realiza los siguientes ejercicios sobre listas:

>	a:=seq(i,i=1..60):

>	s:=2,3,4,5,t,y,j,a,a,l^2;

(1) Determinar el número de elementos de la secuencia s :

>

>

(2) Construir la lista de los 30 primeros cuadrados (esto es, 1^2, 2^2, 3^2....)

>

>

( 3) Determinar el término que ocupa el lugar vigésimo en la lista [s].

>

>

Conjuntos

Un  conjunto es una secuencia contenida dentro de llaves{}. En un conjunto cada elemento sólo puede aparecer una vez y los datos no están ordenados.

Echa una ojeada a la ayuda para conjuntos.

Podemos definir por ejemplo los conjuntos A y B siguientes. Observa que los elementos repetidos sólo se tienen en cuenta una vez y que el orden no es relevante:

>

restart;

>	A:={1,2,3,4,1,4,5};

>	B:={1,2,1,b,s,b,c,4};

Y se pueden hacer operaciones con conjuntos. Es posible hacer uniones (coleccionar los elementos de ambos conjuntos), intersecciones (coleccionar los elementos que pertenecen simultáneamente a ambos conjuntos) y complementos (tomar los elementos de un conjunto que no están en otro):

>	A union B;

>	A intersect B;

>	A minus B;

Ejercicios.

Definimos los siguientes conjuntos, listas y secuencias:

>	s:={Luisa, Juan, Alicia, Pedro, Susana};

>	t:={Pedro, Julian, Sebastian, Juan, Ana};

>	lista:=[Lunes,Martes,Sabado,Jueves];

>	s1:=g,e,y,d,e,r,f,y,f,d,e,k,y,e,f,g,h,d,y;

>

(1) ¿Cómo puedes obtener los elementos comunes a s  y t ? ¿Y los elementos de s que no están en t ?

>

>

>

(2) Reemplaza el elemento S abado  por un nuevo elemento Miercoles en lista.

>

>

>

(3) ¿Cómo puedes saber cuántos elementos tiene el conjunto cuyos elementos son los de s1?

>

>

>

(4)   Genera la lista formada por la concatenación de los elementos   de lista   y lista2 (definida abajo)

>	lista2:=[elem1,elem2,elem3];

>

>

>

( 5) ¿Cuántos números menores que 1000 son a la vez el cuadrado y el cubo de un número entero?

>

>

Bucles y condicionales

Bucles

Una de las razones por las que los ordenadores a veces son útiles es su capacidad de repetir la misma tarea rutinaria una y otra vez sin equivocarse.

El elemento sintáctico que realiza estas repeticiones se llama bucle  y suele consistir de dos partes:

en primer lugar un comando o una serie de comandos que queremos ejecutar repetidamente, y luego un comando que controla cuántas veces se ejecuta el bucle.

Condicionales

Por otro lado están las condicionales  de la forma:

 

si  condición entonces  operación1 si no  operación 2

lo que significa que si se verifica la condición entonces se realiza la operación 1 y si no la operación 2. O de la forma:

mientras  condición operación

lo que significa que mientras se verifique la condición ha de realizarse la operación.

Y combinaciones de las mismas. Veremos algunos ejemplos.

Si se verifica la condición se realiza la operación 1, en caso contrario se realiza la operación 2 (si no se indica nada por defecto no se hace ninguna operación).

Generemos un procedimiento que calcula el máximo de dos números.

Los procedimientos en maple se denotan con proc  y se terminan con end . Las variables que se involucran en el procedimiento se definen como locales para que luego se puedan usar fuera de el procedimientos.

Las condicionales se empiezan por if y se terminan con fi.

if  condición then  operación1 else  operación 2 fi

Que significa que si se cumple la condición entonces se realiza la operación 1 y en caso contrario la operación 2. Después de else  pueden abrirse nuevas condicionales que se escriben else if  o de manera más abreviada elif .

Por ejemplo para calcular el máximo de dos números:

>	maximo:=proc(a,b) local c: if (a>b) then c:=a else c:=b fi: c; end:

La primera línea de código asigna un nombre al procedimiento, digamos máximo e indica que va a actuar sobre dos números a  y b

La variable c  que va a ser la salida se define como una variable local, esto es, sólo se considera dentro del procedimiento.

La sentencia condicional es exactamente la elección del máximo.

Como c va seguida de un punto y coma, será lo que se vea en la pantalla, la asignación a la salida..

El comando end  termina el procedimiento.

 

>	maximo(2,4);

Veamos un procedimiento que indica el signo de un número real:

>	signo:=proc(a) local s; if a<0 then s:=menos elif a=0 then s:=0 else s:=mas fi: s; end:

>	signo(27);

>	signo(-23);

>

signo(0);

>

>

El Bucle "for"

Como en muchos lenguajes de programación, los bucles for y while (mira la ayuda) sirven para la iteración de comandos, de manera parecida al comando seq.

En Maple, la forma general de un bucle es la siguiente:

for   variable   from   inicio  by   salto  to   final  while   expresión  do    operaciones  od

Cuando Maple encuentra este comando, primero asigna el valor inicio  a la variable. Si se cumple expresión ,  ejecuta las sentencias  entre do  y od . A continuación, se hayan ejecutado las  sentencias o no, incrementa la variable  por el valor del salto  (¡que puede perfectamente ser negativo!), y compara el nuevo valor de variable  con  final.
Si variable no es mayor (en el caso de ser salto positivo) respectivamente menor (si salto  es negativo) que final, y se cumple la condición que señala el while , ejecuta otra vez sentencias,  y así sucesivamente.

Si omitimos algunas de estas cláusulas, Maple les asigna un valor por defecto:

inicio  ---->1

salto  ---->1

final   ----> +

expresión  ---->true

Por ejemplo para sumar los números del 1 al 10000.

>	S:=0: for i from 1 to 10^4 do     S:=S+i: od: S;

Que coincide con el valor de la suma de los términos de una sucesión aritmética:

>	(10^4)*(10^4+1)/2;

Para sumar los elementos de una lista numérica:

>	a:=[1,2,3,4,5,6,7,8];

>	S:=0: for i from 1 to nops(a) do S:=S+a[i]: od: S;

>

>

Primeros programas en Maple

Suma de los términos de una sucesión

En la sección anterior fuimos capaces de sumar los elementos de una lista, esto lo podemos hacer como un procedimiento y así poder llamarlo cuando lo necesitemos:

>

restart;

>	suma:=proc(A::list) local S,i: S:=0: for i from 1 to nops(A)   do     S:=S+A[i]:   od: S; end:

Se puede declarar el tipo de variables que usa el procedimiento y así hemos considerado A  como una lista. Esto ayuda a determinar los errores en un procedimiento pues si introducimos variables no adecuadas manda mensaje de error. Puedes consultar la ayuda para ver los distintos tipos de variables.

>

?type;

>	suma(2,3,4,5,6,6);

Error, invalid input: suma expects its 1st argument, A, to be of type list, but received 2

Lo aplicamos a una sucesión aritmética cuyo primer término es a  y la diferencia entre dos consecutivos es d . La lista de los 50 primeros términos es:

>	L:=[seq(a+i*d,i=1..50)]:

Y su suma es:

>

suma(L);

>

Generar coordenadas de un rectángulo

Por ejemplo, queremos escribir una subrutina que tome como entrada un valor x y una altura h y que nos devuelva las coordenadas de un rectángulo cuyos lados estén paralelos a los ejes de coordenadas, que tenga anchura 0.5 y altura h ,  y cuyo borde inferior esté en el eje de las x  y centrado sobre el punto ( x ,0).

La primera línea de la subrutina especifica su nombre y los argumentos de entrada:

rectangulo:=proc(x,h::positive)

Esta línea de código informa a Maple que queremos escribir una subrutina  que se llama rectangulo y que toma como argumentos a x  y a h  . Si no se especifica el tipo de argumentos, maple acepta cualquiera. Especificamos h positivo.

El código que ejecuta la subrutina será el siguiente. No queremos nada más que la lista de las coordenadas de los extremos del rectángulo, las cuales a su vez consisten de listas de dos valores.  

>	rectangulo:=proc(x,h) [[x-.25,0],[x+.25,0],[x+.25,h],[x-.25,h]]: end;

Después de acabar la definición de la subrutina mediante la palabra clave "end", Maple nos confirma el código que ha sacado en claro de nuestra entrada. Si no se quiere esta información se puede terminar el procedimiento con los dos puntos, esto es, end:

Probemos unos ejemplos:

>	rectangulo(-2,3);

>	rectangulo(0,0);

>

Y se pueden representar gráficamente:

>	with(plots): polygonplot(rectangulo(5,3));

Warning, the name changecoords has been redefined

>

>

Búsqueda

Para buscar un elemento b en una lista a introducimos la lista y el elemento y vamos recorriendo la lista comparando con el elemento, continuando la ejecución del bucle si son distintos. Si el bucle se detiene antes de recorrer toda la lista la salida es sí y en caso contrario no. Desarrollaremos otros algoritmos de búsqueda.

>	busqueda:=proc(a::list,b::numeric) local i,c: c:=0: for i from 1 to nops(a) while c=0   do      if a[i]=b then c:=1 fi:   od: if c=0 then c:=No else c:=Si fi: c; end:

Veamos algunos ejemplos:

>	busqueda([1,2,3,4,7,8],8);

>	busqueda([1,2,3,4,7,8],9);

>	busqueda([1,4,5,6,7,9,10],5);

>	busqueda([1,3,4,5,2,3,4,8],4);

>	busqueda([1,3,4,5,2,3,4,8],8);

>

>

>

Media aritmética  

La media aritmética no es más que el cociente entre la suma de los elementos de la lista y el número de elementos, entonces:

>	media:=proc(a::list) local S,i: S:=0: for i from 1 to nops(a)   do      S:=S+a[i]   od: S/nops(a); end:

>	media ([1,2,3,4,5,6]);

>

Prueba con otros ejemplos.

>

>

Máximo

Podemos hacer un procedimiento para calcular el máximo de una lista de números. Sencillamente definimos una variable M donde inicialmente se almacena el valor del primer elemento de la lista y que se va comparando con cada elemento de la lista cambiando su valor por él si es necesario.

>	Maximo:=proc(a) local c,i: c:=a[1]: for i from 2 to nops(a)   do     if c<a[i] then c:=a[i] fi:   od: c; end:

Veamos algunos ejemplos.

>	Maximo([44,55,6,7,10]);

>	Maximo([45,789,10^6,45,6]);

Puedes probar con otros ejemplos.

>

>

Ejercicios

(1) Diseña un procedimiento para dada una lista L y dos enteros a  y b  tales que 0<a<b<nops( L ) calcular el producto de los elementos de L entre el a'ésimo y el b'ésimo.

>

>

(2) Diseña un procedimiento para saber qué lugares ocupa un elemento que está en una lista.

>

>

(3) Diseña un procedimiento para, dadas dos conjuntos A y B construir el producto cartesiano AxB.

>

>

Práctica 2

PRÁCTICA 2

 TEORÍA DE NÚMEROS  

1. Introducción

Instrucciones

1. Lee con atención el texto. Cuando aparezcan comandos o procedimientos de Maple (líneas en rojo), intenta averiguar para qué sirven (puedes emplear la ayuda de Maple) y después ejecútalos. Puedes ejecutarlos varias veces y cambiar en ellos lo que te parezca para entenderlo mejor o mejorarlo.

2. Párate cada vez que aparezca la señal  y trata de responder a la cuestión propuesta.

3. Lee los puntos 1 y 2 de la práctica. Después realiza el test. El punto número 3, de aplicaciones, puedes leerlo fuera de horario de la práctica para ver distintas aplicaciones de lo estudiado.

Contenidos

Teóricos:

-   Aritmética modular

- Máximo común divisor y mínimo común múltiplo

- Teorema chino del resto

- Factorización de enteros

- Test de primalidad

- La función de Euler

Aplicaciones :

- Criptografía clásica

- Criptografía de clave pública

Maple dispone de un paquete de funciones específicas para la Teoría de Números , numtheory , que cargaremos con la instrucción:

>	with(numtheory):

Warning, the protected name order has been redefined and unprotected

>

2. Fundamentos

2.1. Aritmética modular

Para calcular el resto de la división de dos números enteros a,b  se usa el comando mod.

>

5 mod 3;

>	10375378 mod 124903;

Para resolver congruencias lineales en una indeterminada, podemos usar msolve   .

Por ejemplo, supongamos que queremos resolver el siguiente problema: ¿Por qué número debo multiplicar 3 para obtener 1 módulo 7 ?  

>	msolve(3*y=1,7);

De esta forma hemos resuelto la congruencia puesto que:

>	3*5-1 mod 7;

Ahora resolvamos un problema similar cambiando 7 por 6:

>	msolve(3*y=1,6);

>

Parece que Maple ha fallado, pero en realidad no ha aportado ninguna solución porque no existe.

Para comprobarlo observemos la lista de los distintos productos por 3 módulo 6 y veamos que ninguno es igual a 1.

>	seq(3*i mod 6,i=0..5);

>

¿Cuál es la razón de que no tenga solución esta ecuación y sin embargo sí la tenga la anterior?

2.2. Máximo común divisor. Mínimo común múltiplo

La función igcd  ( i nteger g reatest c ommon d ivisor) de Maple sirve para calcular el máximo común divisor de un conjunto de enteros. En clase hemos definido el máximo común divisor de dos números pero la definición se amplía naturalmente para definir el mcd(a1,...,a_n)  como el máximo del conjunto de divisores comunes a a1, ..., an.   

Veamos algunos ejemplos de uso de la función igcd  y otras funciones relacionadas:

>	igcd(3,6);

>	igcd(6,4,12);

Para calcular el máximo común divisor de todos los enteros entre 10 y 100 hacemos:

>	igcd(seq(i,i=10..100));

Y debe ser 1 porque entre el 10 y el 100 hay números primos.

La función ilcm  ( i nteger l east c ommon m ultiple) permite calcular el mínimo común múltiplo (el menor de los múltiplos comunes):

>	ilcm(101,13);

>	ilcm(6,4,12);

>	ilcm(seq(i,i=10..100));

>

Comprueba con varios ejemplos la relación que existe entre el máximo común divisor, el mínimo común múltiplo y el producto de dos números enteros :  

a.b = mcd(a,b). mcm(a,b).

El comando is de la línea siguiente determina si dos expresiones son iguales.

>	is(125*3490=ilcm(125,3490)*igcd(125,3490));

>

>

Recuerda que la verificación de una igualdad en unos cuantos ejemplos no es una demostración, sólo nos convence de que la fórmula parece verdadera, no demuestra su veracidad.

Las funciones gcd  y lcm  de Maple calculan el máximo común divisor y mínimo común múltiplo respectivamente de polinomios. También pueden usarse con números enteros, ya que éstos pueden considerarse polinomios, pero las funciones igcd  e ilcm  lo hacen de forma más eficiente.

El máximo común divisor de dos números se puede expresar como combinación lineal de éstos con coeficientes enteros (Lema de Bezout). Por ejemplo, el máximo común divisor de 3 y 5 , que es 1, se expresa como:  

>

2*3-1*5;

>

Los coeficientes 2 y (-1) se obtienen del algoritmo de Euclides para calcular el máximo común divisor. La función igcdex  de Maple calcula estos coeficientes, si damos como parámetros los nombres de las variables a las que queremos que asigne dichos valores:

>	igcdex(3,5,a,b);

>

a,b;

>

Otro ejemplo:

>	igcd(324,779);

>	igcdex(324,779,x,y); x; y;

>	324*x+779*y;

>

2.3. Teorema chino del resto

Maple se puede usar para resolver sistemas de congruencias mediante el teorema chino del resto.

Observa el siguiente ejemplo:

Para resolver el sistema formado por las tres congruencias siguientes,

X = 2 (mod 3)

X = 3 (mod 5)

X = 2 (mod 7)

empleamos la función chrem  ( ch inese rem ainder theorem) del siguiente modo:

>	chrem([2,3,2],[3,5,7]);

>

La primera lista contiene los segundos miembros de las igualdades y la segunda los módulos respectivos.

Utiliza esta instrucción para encontrar un entero que sea congruente con 5 módulo 2, con 4 módulo 7 y con 3 módulo 11.

>

>

2.4. Factorización de enteros

Para descomponer números enteros en sus factores primos debemos cargar el paquete numtheory  (si no lo hemos hecho antes).

>	with(numtheory);

La función ifactor  descompone un número entero en sus factores primos:

>	ifactor(100);

>	ifactor(12345);

>	ifactor(39248675928359283654928364);

>	h:=2^33*3^55;

>	ifactor(h);

>

Los algoritmos de  factorización de números enteros son muy poco efectivos, números de tamaño muy grande hacen que el programa se quede bloqueado. Si quieres probar, graba primero lo que has hecho hasta ahora  e intenta factorizar, digamos, el número 1+2^200. Recuerda que la señal de STOP en la barra de instrucciones detiene un cómputo.

>

>

>

 

2.5. Test de primalidad

Obtener números primos grandes es muy importante en criptografía como se puede ver en la sección de aplicaciones. Aquí mostraremos algunas de las capacidades de Maple para encontrar números primos. Hemos visto ya cómo factorizar un número entero en sus factores primos. En consecuencia, podríamos usar como test de primalidad de un número su descomposición en factores. Si al factorizar el número a  el resultado es el mismo número a, el número es primo. Esto constituye un test de primalidad:

>	with(numtheory):

>	Testprimo1:=proc(a) local i,s,c: s:=0: for i from 2 to a-1 while s=0 do    if a mod i = 0 then  s:=1 fi:   od: if i<a then c:=compuesto else c:=primo fi: c; end:

Veamos algunos ejemplos:

>	Testprimo1(9);

>	Testprimo1(17);

>	Testprimo1(34567890);

>

En cualquier caso, como decíamos antes, este método es muy  poco eficiente. Actualmente apenas se pueden factorizar números de 100 cifras, y factorizar un número de 200 cifras es impensable (se necesitarían millones de años de cálculo con los mejores computadores para hacerlo).

En consecuencia, en lugar de intentar emplear métodos directos de factorización, para averiguar si un número es primo se emplean métodos probabilísticos. La función isprime  de Maple está basada en éstos métodos. Cuando responde true  significa que el número evaluado es primo con una probabilidad muy alta, pero sin garantizar al 100% el que lo sea.

>	isprime(101);

>	isprime(2342138342111);

>	isprime(23218093249834217);

>

Como éste número no es muy grande, puedes comprobar factorizándolo que, en efecto, no es primo.

>

>

>

>

>

La función ithprime  calcula el i -ésimo número primo. Esto es, el primo que ocupa el lugar i  en la lista creciente de los números primos. Los primeros números primos son 2, 3, 5, 7, 11, ... pero ¿cuál es el que ocupa el lugar 3000 en la lista de todos los primos?

>	ithprime(1);ithprime(2);ithprime(3);

>	ithprime(3000);

>

>

Esta función puede usarse para generar números primos. También pueden utilizarse las funciones   nextprime  y prevprime  , que, como su nombre indica, calculan respectivamente el número primo más próximo mayor y menor al número dado.

>	nextprime(1000);

>	prevprime(1000);

>	nextprime(13);

Observa que si el número es primo nextprime  te da el siguiente primo y prevprime  el primo anterior.

Conviene tener en cuenta que las funciones nextprime  y prevprime  están basadas en la función isprime , por lo que no podemos garantizar el resultado, aunque la probabilidad de que sea correcto es muy elevada.

Terminamos observando que la lista de números primos no se conoce, esto es, no hay una manera de determinar el primo enésimo. Es uno de los grandes problemas no resueltos de la matemática.

2.6. La función  de Euler

La función  de Euler phi(n)  (del paquete numtheory) computa el número de enteros positivos menores o iguales que n  y que son relativamente primos con n  (cuenta el 1  porque mcd(1,n)=1 ). Obsérvese que phi(n) = n-1  si y sólo si n  es primo. Así podemos determinar, mediante la función , la primalidad de n . Sin embargo, nuevamente, no es un test eficiente.

>

phi(1);

>

phi(2);

>

phi(10);

Este número, phi(10) , es exactamente el número de elementos del conjunto de números positivos menores que 10 y relativamente primos con 10, a saber, {1,3,7,9}.

>	is(phi(13)=12);

Esto indica que 13 es un número primo.

>

phi(5);

>

phi(10);

>

phi(107);

Así construimos otro test de primalidad:

>	Testprimo2:=proc(a) local c: if is(phi(a)=a-1)=true then c:=si else c:=no fi: c; end:

Veamos algunos ejemplos:

>	Testprimo2(37);

>	Testprimo2(5);

>	Testprimo2(107);

>	Testprimo2(32);

Si queremos determinar todos los números naturales k  tales que phi(k) = n  , esto es, todos aquello números naturales k  con exactamente n  números a<k  primos con k , podemos usar la función invphi  de Maple. Por ejemplo,

>	invphi(2);

>

Los únicos números cuyo valor de phi es 2 son el 3, el 4 y el 6.

>	phi(3),phi(4),phi(6);

>

Otro ejemplo:

>	s:=invphi(6);

>	p:=[]: for i from 1 to nops(s) do p:=[op(p),phi(s[i])]: od: p;

>

3. Aplicaciones

En esta sección veremos algunas aplicaciones de la aritmética modular y las congruencias.

3.1. Criptografía clásica

Vamos a emplear ecuaciones lineales en congruencias para cifrar y descifrar mensajes como lo hacía Julio César durante la guerra de las Galias.

Necesitamos convertir letras en números, para lo cual emplearemos la función letranumero.

Para asignar un número a cada letra definimos la función letranumero, antes debemos escribir la siguiente línea porque I y E tienen valores preasignados:

>	alias(I=I); alias(E=E);

Error, use interface(imaginaryunit=...) to set the imaginary unit

El alfabeto será:

>	alfabeto:=["A","B","C","D","E","F","G","H","I","J","K","L","M","N","Ñ","O","P","Q","R","S","T","U","V","W","X","Y","Z"]:

Y la función letranumero es, en general:

>	letranumerogen:=proc(a::list) local i: for i from 1 to nops(a) do letranumero(a[i]):=i-1; od: end:

En nuestor ejemplo

>	letranumerogen(alfabeto): letranumero("U");

>

También necesitamos convertir números en letras. Para ello emplearemos la función inversa numeroletra :

>	numeroletragen:=proc(a::list,b::list) local i: for i from 0 to nops(b) do numeroletra(i):=a[i+1]; od: end:

En nuestro ejemplo:

>	numeroletragen(alfabeto,[seq(i,i=0..nops(alfabeto)-2)]): numeroletra(21);

>

Un encriptador afin clásico es de la forma:

f(p) = (ap + b) (mod 26)

donde (a,b)  es la clave de cifrado (que nadie más que el emisor y el receptor debe conocer). El entero p  es el número correspondiente a una letra, y el número f(p)  es el correspondiente a esa letra encriptada. Para poder desencriptar un mensaje es preciso elegir la clave de forma que la función f  sea biyectiva.

¿Cuál es la condición para que eso ocurra, esto es, para que f  tenga inversa?

Emplearemos una función auxiliar Encripletra  para encriptar una sola letra. La ayuda te puede aclarar sobre el tipo de datos string:

>	Encripletra:=proc(s::string,clave::[integer,integer])  local factor,incremento;  if not length(s) = 1 then    ERROR(`el argumento debe ser una sola letra`);  fi;  factor:=clave[1];  incremento:=clave[2];  RETURN(numeroletra((letranumero(s)*factor+incremento) mod 26)); end:

>

La función de encriptado aplica mediante un bucle la función Encripletra a cada letra de la palabra que se va a encriptar:

>	Encripta := proc(s::string, clave::[integer,integer])  local i,textocifrado;  textocifrado:=NULL;  for i from 1 to length(s) do   textocifrado:= cat(textocifrado,          Encripletra(substring(s,i..i),clave));    od;  RETURN(textocifrado); end:

>

Una prueba:

>	Encripletra("A",[3,5]);

>	Encripta("QUIENSABEDONDE",[3,7]);

>

Una vez enviado el mensaje encriptado debemos desencriptarlo, calculando por la inversa de f  y la operación letra número la palabra de que proviene el mensaje anterior.

>

>

>

3.2. Criptografía de clave pública

Veremos ahora cómo implementar con Maple el sistema RSA de encriptado, que se explica a continuación. Construiremos procedimientos de Maple para generar claves, para encriptar y para descifrar mensajes.

Haremos una simplificación para hacer más ágil la práctica: en lugar de emplear números primos grandes (para que el sistema sea seguro conviene emplear dos números primos de 100 cifras) lo haremos con números más pequeños, sino las operaciones tardarían mucho tiempo.

 

Generación de claves

En primer lugar debemos obtener dos números primos grandes p  y q  . Con ellos generamos la clave pública que consta de n = pq  , y el exponente e. Se genera también la clave privada que consta de n  , y el inverso de e  módulo phi(n) , donde phi es la función de Euler. El número e  no tiene relación con los números p  y q . Se puede generar de muchas maneras. Dos valores clásicos para e  en los sistemas reales son 13 y el cuarto número de Fermat F4 = 2^2^4 + 1 = 65537. En nuestro caso tomaremos e  = 13. A n le llamamos módulo.

>

Generaclaves:=proc(p::integer,q::integer)  local n, #modulo        e, #exponente        d, #d*e=1 (mod phin)     phin; #phi(n)=(p-1)(q-1)    n:=p*q;   #calcula el modulo (publico) phin:=(p-1)*(q-1); e:=13;    #este numero se podria generar aleatoriamente #calculamos d tal que e*d=1 (mod phin) d:=op(1,op(Roots(e*x-1) mod phin)); RETURN([[n,e],[n,d]]); end:

>

Veamos un ejemplo:

>	Generaclaves(43,59);

Efectivamente cumplen lo que deben:

>	is(2537=43*59); is(13*937 mod phi(2537)=1);

Función de cifrado y descifrado

Ahora que sabemos generar claves, vamos a ver el método RSA de encriptado. El código es sencillo:

>	RSA:=proc(key,msg::list(posint))   local ct, #texto cifrado obtenido         pe, #exponente (público)         pm, #modulo (público)          i; #índice del bucle   pm:=key[1];   pe:=key[2];   ct:=[];   for i from 1 to nops(msg) do     ct:=[op(ct),msg[i]^pe mod pm];   od;   RETURN(ct); end:

En la línea 10 del código del procedimiento RSA está la idea de la encriptación, toma el número que ocupa el lugar i  en el mensaje lo eleva a pe  y calcula el resto módulo 13.

El primer argumento del procedimiento RSA es la clave. El segundo argumento es el mensaje que queremos encriptar, en forma de lista de enteros positivos. Para ver cómo funciona se lo aplicamos a un ejemplo concreto.

 

Ejemplo

Veamos cómo utilizar el sistema RSA para transmitir un mensaje:

Primero debemos codificar el mensaje en forma de lista de enteros positivos. Para ello podemos asignar a cada letra del alfabeto un número de dos cifras (por ejemplo A-> 10 , B-> 11, etc.). A continuación troceamos la lista numérica obtenida en bloques de 4 dígitos cada uno. La lista de esos bloques constituye la entrada para el procedimiento RSA de encriptado. La elección de la longitud de los bloques ha de escogerse de forma que, después de la conversión, el entero mayor obtenido sea menor que el módulo n .

Primero asignamos a cada letra un número de dos cifras (empezaremos por el 10 por comodidad) y al

espacio en blanco otro número para separar palabras.

>	alias(I=I); alias(E=E); alfabeto:=["A","B","C","D","E","F","G","H","I","J","K","L","M","N","Ñ","O","P","Q","R","S","T","U","V","W","X","Y","Z"," "]: for i from 1 to nops(alfabeto) do  letranumero(op(i,alfabeto)):=i+9: od:

Error, use interface(imaginaryunit=...) to set the imaginary unit

>

Ahora definimos un procedimiento para transformar el mensaje en una lista de enteros de cuatro cifras (el mensaje debe tener un número par de caracteres, es decir, letras mayúsculas o espacios en blanco),

>	bloques:=proc(msg::string)    local i,listabloques;  i:=1;listabloques:=[];  while i < length(msg) do    listabloques:=[op(listabloques),                     letranumero(substring(msg,i..i)) * 100 + letranumero(substring      (msg ,i+1..i+1))]:i:=i+2:  od; RETURN(listabloques); end:

>

>	bloques("HOLA QUE TAL");

Ahora vamos a generar una clave para poder utilizarla (nadie debe saber qué números primos estamos usando para crearla):

>	Generaclaves(83,61);

>

Cuando alguien quiera enviarnos el mensaje "HOLA QUE TAL" de forma cifrada, debe usar nuestra clave pública,

que previamente debemos comunicarle. La forma de hacerlo es la siguiente:

>	RSA([5063, 13],bloques("HOLA QUE TAL"));

>

De esta forma, el mensaje que nos enviarán será:

y no importa que nadie lo lea, porque no serán capaces de entenderlo.

Para desencriptar el mensaje, usamos nuestra clave privada, que es el segundo elemento de nuestra clave RSA, de la siguiente forma, aplicando nuevamente RSA:

>	RSA([5063, 757],[2780, 980, 2926, 3809, 119, 798]);

>

Como vemos esta lista se corresponde con el mensaje "HOLAQUETAL":

>	bloques("HOLA QUE TAL");

>

Bueno, emplea los primos más próximos a 100 y a 200 por exceso para generar la clave con la que está encriptado el siguiente mensaje. Así podrás descifrarlo.

4. Test resuelto del curso 2000/2001

>

>

>	restart; with(numtheory):

Warning, the protected name order has been redefined and unprotected

>	igcd(5643,985798); igcdex(5643,985798,a,b): a; b;

>

>

>

>	chrem([44,-8,25,0],[99,50,31,13]);

La respuesta correcta es la b).

>

>

>

>	[nextprime(10^6),nextprime(2*10^6),nextprime(3*10^6)];

La respuesta correcta es la c).

>

4. Calcula cuántos números primos hay entre 100.000 y 200.000.

>

>	c:=0; for i from 10^5 to 2*10^5 do if isprime(i) then c:=c+1 fi; od; c;

La respuesta correcta es la b).

>

5. Sea la función f(n)=n^17 mod 17. Señala la respuesta correcta:

>

>	seq([n,n^(17) mod 17], n=0..16);

La respuesta correcta es la a).

>

>

>

>	restart; with(numtheory): c:=0; for i from 0 to 10^3 do if isprime(i^2+i+41) then c:=c+1 fi; od; evalf(100*c/1001);

Warning, the protected name order has been redefined and unprotected

La respuesta correcta es la c).

>

7. Y en el conjunto {g(0),g(1),...,g(10.000)}, ¿cuál es el porcentaje de números primos?

>

>	restart; with(numtheory): c:=0; for i from 0 to 10^4 do if isprime(i^2+i+41) then c:=c+1 fi; od; evalf(100*c/10001);

Warning, the protected name order has been redefined and unprotected

La respuesta correcta es la c).

>

>

>	(1513 mod 7, 1513 mod 13, 1513 mod 19);

>	(1206 mod 7, 1206 mod 13, 1206 mod 19);

La respuesta correcta es la c).

9. La función f(p)=77p+42 (mod 98) es:

>

>	{seq(77*p+42 mod 98,p=0..97)};

La respuesta correcta es la c).

10. Los números menores que 1000 que tienen exactamente 100 números más pequeños que son relativamente primos con ellos:

>

>	invphi(100);

La respuesta correcta es la a).

>

5. Test resuelto del curso 2001/2002

 

1.   Dados los números enteros 712504 y 985898 determinar el conjunto de divisores comunes a ambos y su mcd.

>

>	restart; with(numtheory):

Warning, the protected name order has been redefined and unprotected

>	ifactor(712504);ifactor(985898); igcd(712504,985898);

>

>

>

>	chrem([42,-8,25,0],[99,50,17,13]); 99*50*17*13;

La respuesta correcta es la c).

>

3. Determina el número de múltiplos de 13 que hay entre el 115218 y el 369214 (ambos inclusive).

>

>	c:=0: for i from 115218 to 369214 do if (i mod 13)=0 then c:=c+1 fi od: c;

La respuesta correcta es la a).

>

4. Calcula el porcentaje de números primos entre el 30.000 y el 40.000 (ambos inclusive)

>

>	c:=0: for i from 3*10^4 to 4*10^4 do if isprime(i) then c:=c+1 fi; od; evalf(c/10001);

La respuesta correcta es la b).

>

5. Sea la función del conjunto cociente de Z por la relación de congruencia módulo 13 en sí mismo dada por la fórmula f(n)=n^13+1 mod 13. Señala la respuesta correcta:

>

>	seq([n,n^(13)+1 mod 13], n=0..12);

La respuesta correcta es la b).

>

6. Sean las congruencias 3x+1 congruente con 5 módulo 7 y 2x+3 congruente con 7 módulo 11.

>

>	msolve(3*x+1=5,7); msolve(2*x+3=7,11);

>	{seq(7*i+6,i=1..100)}intersect{seq(11*i+2,i=1..100)};

>

>

La respuesta correcta es la c).

>

7. Determinar la cantidad de números enteros menores o iguales que 1000 relativamente primos con 1000.

>

>	phi(1000);

La respuesta correcta es la a).

>

>

>	(1513 mod 11, 1513 mod 13, 1513 mod 17);

>	(1206 mod 11, 1206 mod 13, 1206 mod 17);

La respuesta correcta es la b).

9. El inverso de 7 módulo 5, el de 4 módulo 9 y el de 8 módulo 11 son:

>

>	msolve(7*x=1,5);msolve(4*x=1,9);msolve(8*x=1,11);

La respuesta correcta es la c).

10. El mcd(a,b,c) verifica que:

>

>	igcd(14,67,89); igcd(14,igcd(67,89));

>	igcd(1445,6785,8900); igcd(1445,igcd(6785,8900));

>

La respuesta correcta es la a).

>

6. Test resuelto del curso 2002/2003

1.  Los números enteros 9755076 y 3489755:

a) Son relativamente primos entre sí.

b) No tienen divisores comunes.

c) Tienen 4 divisores comunes.

>	restart; with(numtheory):

Warning, the protected name order has been redefined and unprotected

>	igcd(9755076,3489755);

>

>

>

>	restart; with(numtheory):

Warning, the protected name order has been redefined and unprotected

>	ifactor(99);ifactor(52);99*52*17*19;

>	chrem([42,-8,25,0],[99,52,17,19]);

La respuesta correcta es la b).

>

>

>

>	restart; with(numtheory):

Warning, the protected name order has been redefined and unprotected

>	listaprimos:=proc(n) local p,i,c; i:=1;c:=[]; for p from 2 to n do   if isprime(p) then c:=[op(c),p]; fi; od; c; end: listaprimos(100);nops(%);

La respuesta correcta es la a).

>

>

>

>	restart; with(numtheory):

Warning, the protected name order has been redefined and unprotected

>	f:=n->4*n^32+4 mod 8;

>	seq([n,4*n^32+4 mod 8], n=0..7);

La respuesta correcta es la b).

>

5. Calcula la cantidad de números primos entre los números  del tipo ,   ,  menores que 100000.

>

>	restart; with(numtheory):

Warning, the protected name order has been redefined and unprotected

>	solve(2^n-1<100000,n);

>	floor(ln(100001)/ln(2));

También,

>	seq(2^n-1,n=2..16);2^17-1;

>	c:=0:for i from 2 to  16 do if isprime(2^i-1) then c:=c+1: fi; od; c;

La respuesta correcta es la a).

>

>

>

>	restart; with(numtheory):

Warning, the protected name order has been redefined and unprotected

>	ifactor(4536789);

>	phi(4536789);

La respuesta correcta es la b) porque los múltiplos de 3 no son relativamente primos con 4536789.

>

7. Determinar cuántos números enteros mayores estrictamente que 10 y menores estrictamente que 1000 son, a la vez, primos y congruentes con 5 módulo 7.

>

>	restart; with(numtheory):

Warning, the protected name order has been redefined and unprotected

>	solve(7*i+5<1000,i);floor(995/7);

>	c:=0: for i from 1 to floor(995/7) do if isprime(7*i+5) then c:=c+1 fi: od: c;

La respuesta correcta es la a).

>

>

>	restart; with(numtheory):

Warning, the protected name order has been redefined and unprotected

>	chrem([1,1],[5,3]); chrem([1,1],[10,3]);

>

La respuesta correcta es la c).

>

>

>

>	restart; with(numtheory):

Warning, the protected name order has been redefined and unprotected

>	f:=n->a*n+2 mod 7;simplify(f(f(n))-n);

>	for a from 0 to 6 do if simplify(f(f(n))-n)=0 then print(a); fi; od;

La respuesta correcta es la c).

>

10. Los inversos de 3, 5 y 7 modulo 12 son respectivamente:

>

>	restart; with(numtheory):

Warning, the protected name order has been redefined and unprotected

>	msolve(5*n-1,12); msolve(7*n-1,12);

La respuesta correcta es la a).

Práctica 3

PRÁCTICA 3

COMBINATORIA

1
1, 1
1, 2, 1
1, 3, 3, 1
1, 4, 6, 4, 1
1, 5, 10, 10, 5, 1
1, 6, 15, 20, 15, 6, 1

1, 7, 21, 35, 35, 21, 7, 1

Introducción a la Combinatoria con Maple

Instrucciones

1. Lee con atención el texto. Cuando aparezcan comandos o procedimientos de Maple (líneas en rojo), intenta averiguar para qué sirven (puedes emplear la ayuda de Maple) y después ejecútalos. Puedes ejecutarlos varias veces y cambiar en ellos lo que te parezca para entenderlos mejor o mejorarlos.

2. Realiza el test de evaluación (en un fichero aparte), ayudándote de los test de otros cursos.

Comandos de Maple

En el paquete combinat  de Maple se recogen comandos relacionados con la combinatoria. Para cargar el paquete procedemos como siempre con la instrucción:

>	with(combinat);

Warning, the protected name Chi has been redefined and unprotected

>

Hay otro paquete de funciones más avanzadas, combstruct , que no emplearemos en esta práctica.

Cardinales de conjuntos

Comenzamos con las funciones que presenta Maple para trabajar con conjuntos finitos y calcular sus cardinales.

Recordamos que los conjuntos se definían con llaves.

>	A:={1,2,3,4};

Y que la operación nops  calculaba el número de elementos, es decir, el cardinal del conjunto A:

>

nops(A);

>	C:={seq(n^2,n=-10..10)}; nops(C);

Las operaciones habituales de conjuntos, como son la unión, la intersección, la diferencia de conjuntos y el producto cartesiano se pueden efectuar con Maple.

>	B:={1,a,b,c};

>	A union B;

>	A intersect B;

>	A minus B;

Podemos hacer un procedimiento simple para construir el conjunto producto cartesiano:

>	cartesiano:=proc(A::set,B::set) local i,j,C: C:={}: for i from 1 to nops(A) do    for j from 1 to nops(B) do    C:=C union {[[op(A)][i],[op(B)][j]]}   od: od: C; end:

Veamos unos ejemplos:

>	cartesiano({1,2},{l,m});

>	cartesiano({maria,juana,luisa},{pedro,pepe,juan});

>

Aplicamos la teoría de conjuntos para responder la siguiente cuestión: ¿cuántos números enteros positivos menores o iguales que 1000 son a la vez el cuadrado de un  número entero y múltiplos de 4?.

Definimos el conjunto de los cuadrados menores que 1000.

>	evalf(sqrt(1000));

>

32**2;

 

>	F:={seq(n^2,n=1..31)};

Definimos el conjunto de los múltiplos de 4 menores o iguales que 1000.

>	G:={seq(4*n,n=1..250)}:

Por tanto debemos calcular el cardinal de la intersección.

>	nops(F intersect G);

Los números enteros que cumplen ambas condiciones son exactamente:

>	F intersect G;

>

En efecto todos ellos son múltiplos de 4 y el cuadrado de un número entero.

Permutaciones

Comenzamos ahora a estudiar los comandos que tiene Maple para el cálculo de variaciones, permutaciones y combinaciones.

Aunque siguiendo el orden de los apuntes deberíamos empezar con las variaciones de m  elementos tomadas de n en  n  vamos a comenzar sin embargo con las permutaciones. Maple no tiene implementada una función para calcular las variaciones, pero sí que la tiene para permutaciones y combinaciones, de modo que con ellas podremos definir las variaciones.

El número de permutaciones de m elementos se calcula con numbperm :

>	numbperm(6);

También se puede usar el símbolo !  o la expresión factorial para calcular el factorial de un número:

>	6!; factorial(6);

La función numbperm  se puede aplicar a un conjunto en lugar de a su cardinal:

>	numbperm({a,b,c,d,e,f});

Para generar todas las permutaciones de un conjunto, esto es, las distintas maneras de ordenarlo, empleamos permute :

>	permute({a,b,c});

Observad que el resultado es una secuencia.

Y para generar aleatoriamente una permutación de los elementos de un conjunto usamos la función randperm :

>	randperm({a,b,c,d,e,f});

Si queremos introducir repeticiones , entonces debemos dar los datos con una secuencia:

>	permute([c,o,c,o,d,r,i,l,o]):

>	numbperm([c,o,c,o,d,r,i,l,o]);

La línea en que enumeran las permutaciones de la palabra cocodrilo la hemos terminado con dos puntos para no llenar pantallas con las 30240 permutaciones distintas de la palabra.

Y podemos verificar que es correcto según las fórmulas de clase:

>	9!/(2!*3!);

También la función multinomial  permite calcular las permutaciones con repetición. Mediante la función convert  podemos ver exactamente la fórmula que desarrolla multinomial:

>	multinomial(9,2,3,1,1,1,1); convert(multinomial(n,a,b,c,d),factorial);

De esta manera las permutaciones con repetición se pueden calcular por estos dos caminos:

>	is(numbperm([c,o,c,o,d,r,i,l,o])=multinomial(9,2,3,1,1,1,1));

>

Combinaciones

Para calcular el número de combinaciones de n elementos (por ejemplo 2 elementos) escogidos entre los elementos de un conjunto (por ejemplo el conjunto {María , Juan , Eva , Luis , Teresa, Pablo} ), esto es, sus subconjuntos de n  elementos, empleamos la función numcomb,

>	numbcomb({Maria, Juan, Eva, Luis, Teresa, Pablo},2);

Aunque también se puede hacer empleando los números combinatorios m sobre n  que son los coeficientes en el binomio de Newton.

>	binomial(6,2);

Para ver la fórmula con la que trabaja binomial  podemos usar de nuevo convert .

>	convert(binomial(m,n),factorial);

Si lo que queremos es obtener la lista de todas las combinaciones empleamos choose :

>	### WARNING: combinat[choose] with numeric first parameter now returns a sorted list rather than a set choose({Maria, Juan, Eva, Luis, Teresa, Pablo},2);

Obsérvese que el resultado es un conjunto.

Si a las funciones numbcomb  y choose   no se les da el segundo argumento, hacen el cálculo correspondiente a todos los valores desde cero hasta el número de elementos del conjunto.

>	numbcomb({Maria, Juan, Eva, Luis, Teresa, Pablo});

Que es el cardinal del conjunto partes de {María , Juan , Eva , Luis , Teresa, Pablo}  formado por todos sus subconjuntos.

>

2^6;

Este conjunto es:

>	### WARNING: combinat[choose] with numeric first parameter now returns a sorted list rather than a set choose({Maria, Juan, Eva, Luis, Teresa, Pablo});

>

Podemos generar una combinación de forma aleatoria con randcomb

>	randcomb({chocolate,vainilla,fresa,limon},2);

>	randcomb(5,3);

>

En el último caso se eligen al azar tres números del conjunto {1,2,3,4,5} .

De nuevo, como en el caso de las permutaciones,  si queremos que haya elementos repetidos los datos deben introducirse como una secuencia.

>	### WARNING: combinat[choose] with numeric first parameter now returns a sorted list rather than a set choose([a,b,a],2);

>	numbcomb([a,b,a],2);

Observa que éstas no son las combinaciones con repetición de 2 elementos tomadas de dos en dos, que son por la fórmula vista en clase:

>	binomial(2+2-1,2);

Ya que en las combinaciones elegidas arriba, falta la pareja (b,b) .

Se puede introducir una función en dos variables que permita calcular el número de combinaciones con repetición de m elementos tomadas de n  en n .

>	CR:=(m,n)->binomial(m+n-1,n);

>

CR(2,2);

>

Variaciones

Vamos a construir una fórmula para las variaciones y para las variaciones con repetición.

Como las combinaciones de m  elementos tomadas de n  en n  son el cociente de las variaciones de  m  elementos tomadas de n  en n  por las permutaciones de n , la fórmula oportuna será:

>	V:=(m,n)->binomial(m,n)*n!;

>

V(3,5);

>

V(3,3);

O como un procedimiento:

>	V2:=proc(m,n) local s,i: if n>m then s:=0 else s:=1: for i from 0 to n-1 do s:=s*(m-i): od: fi: s; end:

>	V2(5,3); V2(5,10);

Y también podemos construir una fórmula para las variaciones con repetición:

>	VR:=(m,n)->m^n;

>

VR(2,3);

Y dado un conjunto de m  elementos podríamos diseñar un procedimiento que construyera primero todas las combinaciones de n  elementos con el comando choose , y luego hiciera todas las permutaciones para cada una de estas combinaciones. El resultado es el conjunto de todas las variaciones de m  elementos tomados de n  en n , esto es, las listas ordenadas de n  elementos en un conjunto de m  elementos.

>	variaciones:=proc(A,n) local C,D,i: ### WARNING: combinat[choose] with numeric first parameter now returns a sorted list rather than a set C:=[op(choose(A,n))]: D:={}: for i from 1 to nops(C) do D:= D union {op(permute([op(C[i])]))}: od: D; end:

Veamos algunos ejemplos:

>	variaciones({a,b,c,d},3);

En efecto, se han obtenido todas:

>	is(nops(variaciones({a,b,c,d,e},3))=V(nops({a,b,c,d,e}),3));

Otros ejemplos:

>	variaciones({1,2,3},2);

>	variaciones({p,q,r,s,t,u,v},7):

>	is(nops(%)=7!);

>

Otras funciones combinatorias

Las funciones partition, numbpart  y randpart  sirven para calcular el número de formas distintas en que se puede descomponer un número natural en suma de otros, para hallar todas las posibles descomposiciones y para hallar una de ellas al azar respectivamente. Veamos un ejemplo:

>	partition(10);

Es decir, ha encontrado todas las maneras en que 10 se puede poner como suma de números naturales menores o iguales que 10.

Para contarlas se usa:

>	numbpart(10);

Y en efecto calcula el cardinal del conjunto anterior:

>	nops(partition(10));

De igual manera si se quiere conseguir una partición aleatoriamente:

>	randpart(10);

Observa que si se repite el comando anterior:

>	randpart(10);

>

Como la elección es aleatoria, es demasiada casualidad que  haya salido igual.

Test resuelto curso 2000/2001

1.-Sea un experimento de Bernoulli con probabilidad de éxito p=1/3. Entendiendo que las repeticiones del experimento son sucesos independientes. Calcula la probabilidad de obtener exactamente 3 éxitos al repetir el experimento 154 veces. La respuesta es:

>

>	with(combinat):

>	evalf(binomial(154,3)*(1/3)^3*(2/3)^(151));

>

>

>	evalf(add(binomial(154,i)*(1/3)^i*(2/3)^(154-i),i=0..75));

La respuesta correcta es la c).

3.  Con  el mismo enunciado del primer problema, calcula el mínimo número de veces que se ha de repetir el experimento para que la probabilidad de obtener al menos 1 éxito sea mayor que 0.75:

>

>	seq([n,evalf(1-(2/3)^n)],n=1..10);

La respuesta correcta es la a).

 4.- Sea el experimento aleatorio extraer una bola de un bombo con bolas numeradas del 1 al 100 todas ellas iguales. Dada una variable aleatoria X definida sobre el espacio muestral de este experimento de forma que X(s)=s^2, su valor esperado (o esperanza matemática) es:

>

>	evalf(add(s^2/100,s=1..100));

La respuesta correcta es la a).

>

 5.- La probabilidad de extraer un número primo en una urna que contiene los números enteros entre el 1 y el 5000 es:

>

>	c:=0; for i from 1 to 5000 do if isprime(i) then c:=c+1 fi; od; evalf(c/5000);

La respuesta correcta es la c).

 6.- Sea el conjunto de pares de palabras (p,q) donde la palabra p es una palabra de 9 letras que se obtiene permutando las letras de la palabra cocodrilo  y la palabra q es una palabra de 11 letras obtenida permutando las letras de la palabra abracadabra . ¿Cuál es la probabilidad de que al elegir una de ellas sea justamente la palabra (cocodrilo,abracadabra)?:

>

>	evalf(1/(numbperm([c,o,c,o,d,r,i,l,o])*numbperm([a,b,r,a,c,a,d,a,b,r,a])));

La respuesta correcta es la b).

7.- De cuantas maneras se pueden sentar 11 personas en dos mesas, una de 6 comensales y otra de 5 comensales, teniendo en cuenta tanto la distribución en las dos mesas, como el orden en cada mesa:

>

>	binomial(11,6)*6!*5!;

La respuesta correcta es la c).

8.- ¿Cual es el menor valor de n para el cual la probabilidad de que dos personas en un grupo de n personas cumplan los años el mismo día es mayor que 0.75?

>

>	f:=n->1-(binomial(365,n)*n!/365^n);

>	seq([n,evalf(f(n))],n=30..40);

>

>

>	A:={seq(i^2,i=1..100)}: B:={seq(i^3,i=1..100)}: nops(A intersect B);

La respuesta correcta es la a).

10.- De los números naturales menores o iguales que 10.000 cuántos múltiplos de 5 no son múltiplos de 7.

>

>	restart; C:={seq(5*n,n=1..2000)}: E:={seq(7*n,n=1..2000)}: nops(C minus E);

La respuesta correcta es la c).

Test resuelto curso 2001/2002

1.-Determinar cuántos números naturales menores que 10000 son múltiplos de 7 pero no son pares ni múltiplos de 3:

a) 477

b) 476

c) 478

>	evalf(10000/7);

>	A:={seq(7*i,i=1..1428)}:

>	B:={seq(2*i,i=1..5000)}:

>	C:={seq(3*i,i=1..3333)}:

>	nops(A minus B minus C);

>

La respuesta correcta es la b)

>	restart: with(combinat):

Warning, the protected name Chi has been redefined and unprotected

2.- Determinar cuántos subconjuntos de menos de 5 elementos (de 0 a 4 elementos) tiene el conjunto

>	E:={a,b,c,d,f,e,r,t,y,n,l}:

>

a) 432

b) 554
c) 562

>

nops(E);

>	c:=binomial(11,0): for i from 1 to 4 do c:=c+binomial(11,i): od: c;

>

La respuesta correcta es la c).

3.- Dado un conjunto de 54 personas hay que elegir un delegado, un subdelegado y un vocal. De entre los restantes hay que elegir a 3 personas para que les acompañen. Determinar cuántas posibles delegaciones hay.

a) 3099889800

b)

c) 3099889800

>	54*53*52*binomial(51,3);

>

La respuesta correcta es la b).

4.- Sea una urna que contiene los números del 1 al 10000. Se extraen dos bolas consecutivamente, reintroduciendo en la urna la bola extraída. Determinar la probabilidad de que ambas bolas sean números primos.

a) 0.02145

b) 0.01510

c) 0.01234

>	c:=0: for i from 1 to 10000 do if isprime(i) then c:=c+1: fi: od: c;

>	evalf((1229/10^4)^2);

>

La respuesta correcta es la b).

5.- Sea un conjunto de 357 personas. Sea el experimento aleatorio: seleccionar tres personas. Sea el suceso S: las tres personas son rubias. Determinar el número mínimo de personas que han de ser rubios para que la probabilidad de S sea mayor o igual que 1/3.

a) 248

b) 348

c) 249

>	restart: with(combinat):

Warning, the protected name Chi has been redefined and unprotected

>	p:=n->binomial(n,3)/binomial(357,3);

>	i:=0: while(evalf(p(i))<1/3) do i:=i+1: od: i;

>	evalf(p(247)); evalf(p(248)); evalf(p(249));

>

La respuesta correcta es la a).

6.- Determinar el número de palabras que se pueden construir permutando las letras de la palabra semaforos.

a) 90721

b) 91720

c) 90720

>	numbperm([s,e,m,a,f,o,r,o,s]);

>

La respuesta correcta es la c).

7.- Sean los conjuntos A y B descritos abajo. Determinar cuántos subconjuntos de 3 elementos comparten A y B.

a) 120

b) 130

c) 134

>	A:={1,2,3,4,5,e,r,t,y,u,i,o,p}: B:={1,2,3,4,5,e,r,t,g,y,u,h,j,l}:

>	### WARNING: combinat[choose] with numeric first parameter now returns a sorted list rather than a set ### WARNING: combinat[choose] with numeric first parameter now returns a sorted list rather than a set nops(choose(A,3) intersect choose(B,3));

>	### WARNING: combinat[choose] with numeric first parameter now returns a sorted list rather than a set nops(choose(A intersect B,3));

>

La respuesta correcta es la a).

8.- Cuántos números se pueden representar en el sistema binario con 10 dígitos.

a) Menos de 1000

b) Más de 1500 y menos de 2000

c) Más de 1000 y menos de 1100

>

2**10;

>

La respuesta correcta es la c).

9.- Sea un alfabeto con 27 letras. Determinar cuántos códigos alfanuméricos (formados por números y letras) de 7 símbolos se pueden establecer, sabiendo que los dos primeros símbolos han de ser letras y los dos últimos han de ser números.

a)

b)

c)

>	27*27*37*37*37*10*10;

>

La respuesta correcta es la c).

10.- Dados dos números naturales m y n   decimos que m es ascendente de n si se verifica que

>	m**3=n**2;

por ejemplo 1 es ascendente de 1 y 4 es ascendente de 8. Determinar la probabilidad de que al escoger aleatoriamente un número m menor o igual que 1000 exista n menor o igual que 1000 tal que m sea ascendente de n .

a) 0.01

b) 0.11

c) 0.21

>	c:=0: for m from 1 to 1000 do for n from 1 to 1000 do if m^3=n^2 then c:=c+1: fi: od: od: evalf(c/1000);

>

>

>

La respuesta correcta es la a).

Test resuelto curso 2002/2003

1)  En un taller hay 10 coches que necesitan reparaciones. Calcular de cuantas formas distintas se pueden

elegir y ordenar los primeros 4 coches que se van a arreglar.

a)  

b)

c)

>	restart;with(combinat):V:=(m,n)-> binomial(m,n)*n!;

Warning, the protected name Chi has been redefined and unprotected

>

V(10,4);

La respuesta correcta es la c).

>

2)  Determinar el número de palabras que se pueden construir permutando las letras de la palabra ALESSANDRA.

a)

b)

c)

>	restart;with(combinat): numbperm([A,L,E,S,S,A,N,D,R,A]);

Warning, the protected name Chi has been redefined and unprotected

La respuesta correcta es la c).

>

3) Determinar cuantos posibles resultados pueden acontecer al lanzar 25 monedas simultáneamente.

a)

b)
c) 26

>	restart;with(combinat): binomial(26,25);

Warning, the protected name Chi has been redefined and unprotected

La respuesta correcta es la c).

>

4) Sea un alfabeto con 27 letras. Determinar cuantas contraseñas alfanuméricas (formadas por números y letras, distinguiendo mayúsculas y minúsculas) de 8 símbolos se pueden establecer, sabiendo que los tres primeros símbolos han de ser letras y los

dos últimos han de ser números.

a)

b)

c)

>	54*54*54*64*64*64*10*10;

La respuesta correcta es la b).

>

5)  Sean S y S' dos sucesos de un mismo espacio muestral tales que: p(S)=0.5, p(S')=0.8 y p(S|S')=0.6.

Se verifica que:

a)  la probabilidad de S intersección con S' es 0.4

b)  S y S' no son sucesos independientes.

c)  S y S' son sucesos independientes.

Si S y S' fuesen independientes,  p(S|S') sería igual a p(S)  y la probabilidad de S intersección con S' sería igual a

>

0.5*0.8;

Pero p(S|S') no es igual a p(S).

La respuesta correcta es la b).

>

6) Calcular la probabilidad de que un número natural menor o igual a 10000 sea un cubo de un número natural y

congruente con 3 módulo 5.

a)  

b)  

c)    

>	restart;with(combinat):

Warning, the protected name Chi has been redefined and unprotected

>	floor(10^(4/3));

>	A:={seq(i^3,i=1..21)}:nops(A);

>	solve(3+5*k<=10^4,k);

>	floor(9997/5);

>	B:={seq(3+5*k,k=0..1999)}:nops(B);

>	nops(A intersect B)/10^4;

>

7) Tomamos una urna con bolas de distintos colores. Si la urna contiene 32 bolas y extraemos 5 bolas, determinar el número mínimo de bolas rojas en la urna para que la probabilidad de que las cinco bolas extraídas sean todas rojas sea al menos 1/5.

a) 24

b) 34

c) 25

>	restart: with(combinat):

Warning, the protected name Chi has been redefined and unprotected

>	p:=n->binomial(n,5)/binomial(32,5);

>	i:=0: while(evalf(p(i))<1/5) do i:=i+1: od: i;

>	evalf(1/5);evalf(p(23)); evalf(p(24));

La respuesta correcta es la a).

>

8)  Sea el experimento aleatorio consistente en el tirar dos dados consecutivamente. Calcular la probabilidad

que la suma de los resultados de ambos dados sea 7.

a)  

b)

c)

>

>	restart;with(combinat): suma:=partition(7);

Warning, the protected name Chi has been redefined and unprotected

>	c:=0: suma2:=[]: for i from 1 to nops(suma) do   if nops(suma[i])=2 then suma2:=[op(suma2),suma[i]]: c:=c+1; fi: od; c;suma2;

>

>

p:=6/36;

La respuesta correcta es la a).

>

9)  Sea un experimento de Bernoulli con probabilidad de éxito p=1/4.

Calcula la probabilidad de obtener exactamente 53 éxitos al repetir el experimento 200 veces.

La respuesta es:

>

>	restart;with(combinat):

Warning, the protected name Chi has been redefined and unprotected

>	evalf(binomial(200,53)*((1/4)^53)*((3/4)^(147)));

La respuesta correcta es la b).

>

10) La probabilidad de extraer un número relativamente primo con 567 de una urna que contiene los números enteros

entre el 1 y el 567 es:

>

>	restart;with(combinat):with(numtheory):

Warning, the protected name Chi has been redefined and unprotected

Warning, the protected name order has been redefined and unprotected

>	phi(567)/567;

La respuesta correcta es la b).

>

#fin

(Libro de referencia:   "EXPLORING DISCRETE MATHEMATICS WITH MAPLE"   de K.H.Rosen,   McGraw Hill 1997 )