Examen final: Matemáticas discretas I, 2010

El examen se aplicó a los estudiantes de la licenciatura de Física-Matemáticas en dos fechas, el 30 de junio (la fecha programada) y otra opción el 6 de julio para quienes querían esperar algunos días.

Examen del 30 de junio.

INSTRUCCIONES: Selecciona 5 de los 6 problemas y resuélvelos.

Problema 1. Demuestra que el número de soluciones enteras y positivas de la ecuación x_1+x_2+x_3+x_4=9 es el mismo que el número de soluciones enteras y positivas de la ecuación x_1+x_2+x_3+x_4+x_5+x_6=9.

Problema 2. Las fichas en un juego de poker pueden ser rojas, azules o blancas. ¿De cuántas formas se puede hacer un montón con 12 fichas?

Problema 3. Demuestra mediante alguna biyección que si X es un conjunto con n elementos, entonces la
cantidad de subconjuntos con un número par de elementos es la misma que la cantidad de subconjuntos con un número impar de elementos.

Problema 4. Sea G una gráfica simple con 10 vértices y 28 aristas. Demuestra que contiene un ciclo de
longitud 4.

Problema 5. Demuestra usando un argumento combinatorio que
\binom{n}{1} + 2\binom{n}{2} + 3\binom{n}{3} + \cdots +  n\binom{n}{n}= n 2^{n-1}.

Problema 6. Encuentra dos gráficas simples y conexas que tengan la misma sucesión de grados pero que no sean isomorfas (¡demuestra que no lo son!).

Examen del 6 de julio.

INSTRUCCIONES: Selecciona 5 de los 7 problemas y resuélvelos.

Problema 1. ¿De cuántas formas puedes acomodar en fila 10 unos y 5 ceros de tal forma que no haya dos ceros en posiciones contiguas?

Problema 2. ¿Cuántas gráficas simples con 12 vértices existen?

Problema 3. ¿Cuántas soluciones tiene la ecuación x_1+x_2+x_3+x_4+x_5=24 si cada x_i es entera y positiva?

Problema 4. Si mn⩾2,
a) ¿Cuántos ciclos de longitud 4 hay en la gráfica K_{m,n}?
b) ¿Cuántas trayectorias de longitud 2 hay en K_{m,n}?
c) ¿Cuántas trayectorias de longitud 3 hay en K_{m,n}?

Problema 5. Demuestra usando un argumento combinatorio que (n-k)\binom{n}{k} = n\binom{n-1}{k}.

Problema 6. Si d_n es el número de formas de cubrir una cuadrícula de 2×n con dominós, demuestra que
d_{n+2}=d_0 + d_1 + d_2 + \cdots + d_{n-1}+d_n .

Problema 7. Sea X = {1,2,3,…,20}. Demuestra mediante alguna biyección que la cantidad de subconjuntos de
X con un número par de elementos es la misma que la cantidad de subconjuntos de X con un número impar de elementos.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s