Ricardo A. Sáenz

Fecha de entrega: 18 de marzo Problema 1 Formula y demuestra el siguiente enunciado como un teorema de grafos: " En un grupo de personas existen dos de ellas que conocen al mismo número de personas cada uno ". Problema 2 Por medio de un ejemplo, muestra que si eliminamos una arista de un grafo conexo  G , el resultado puede ser un grafo disconexo. Muestra que, si la arista eliminada pertenece a un ciclo subgrafo de  G , entonces el resultado es conexo. Problema 3 Sea  G un grafo y  u, v dos vértices de  G . Muestra que, si existe una caminata de u a v , entonces existe una trayectoria de u a v . Utiliza el inciso anterior para dar una demostración distinta a la vista en clase para el siguiente enunciado: si  p , q , y r son vértices de G tales que existe una trayectoria de p a q y una trayectoria de q a r , entonces existe una trayectoria de p a r . Problema 4 Muestra que si el grafo  G  con n vértices tiene más de $latex \binom{n-1}{2}$ aristas, entonces e...

Fecha de entrega: 11 de junio Problema 1 Sean $latex 2n$ puntos en un círculo. Muestra que el número de formas en que podemos unir estos puntos en pares, de tal manera que los $latex n$ segmentos no se crucen, es igual al número de Catalan $latex C_n$. Problema 2 Muestra que el número de arreglos de $latex 2\times n$ $latex \begin{pmatrix}x_{11}& x_{12}&\ldots& x_{1n}\\x_{21}& x_{22}&\ldots& x_{2n}\end{pmatrix}$ con los números $latex 1, 2, \ldots, 2n$ de tal forma que cada renglón y cada columna es creciente, es igual a $latex C_n$. Problema 3 Determina la división en diagonales del polígono convexo que corresponde a las siguientes multiplicaciones. $latex a_1\times(((a_2\times a_3)\times(a_4\times a_5))\times a_6)$ $latex ((a_1\times a_2)\times (a_3\times (a_4\times a_5)))\times((a_6\times a_7)\times a_8)$ Problema 4 Calcula la tabla de diferencias para la sucesión $latex x_n = 2n^2-n+3$, y encuentra una fórmula para $latex \sum_{k=0}^n x_k$. Si la suc...

Fecha de entrega: 4 de marzo Problema 1 ¿Cuántos subconjuntos de {1, 2, 3, ..., n} no contienen dos enteros consecutivos? Problema 2 Muestra que $latex F_{3n}$ es par. Muestra que $latex F_{5n}$ es divisible entre 5. Problema 3 Muestra las siguientes identidades. $latex F_1 + F_3 + \ldots + F_{2n-1} = F_{2n}$ $latex F_0^2 + F_1^2 + F_2^2 + \ldots + F_n^2 = F_n\cdot F_{n+1}$ $latex \displaystyle \binom{n}{0}F_0 + \binom{n}{1}F_1 + \binom{n}{2}F_2 + \ldots + \binom{n}{n}F_n = F_{2n}$ $latex \displaystyle \binom{n}{0}F_1 + \binom{n}{1}F_2 + \binom{n}{2}F_3 + \ldots + \binom{n}{n}F_{n+1} = F_{2n+1}$ Problema 4 Los números de Lucas $latex L_0, L_1, L_2, L_3, \ldots$ satisfacen la ecuación de recurrencia $latex L_n = L_{n-1} + L_{n-2}$ con términos iniciales $latex L_0 = 2, L_1 = 1$. Muestra que $latex L_n = F_{n-1} + F_{n+1}$ para $latex n\ge1$. Encuentra una fórmula explícita para $latex L_n$. Problema 5 Resuelve las siguientes ecuaciones de recurrencia. $latex x_n = x_{n...

Fecha de entrega: 26 de febrero Problema 1 Muestra que, si los eventos A y B son excluyentes, entonces $latex P(A) + P(B) = P(A\cup B).$ Muestra que, para cualquiera dos eventos A y B , $latex P(A\cap B) + P(A\cup B) = P(A) + P(B).$ Problema 2 Al tirar un dado, considera los eventos P = "par",  I = "impar",  T = "múltiplo de 3" y  G = "más grande que 3". ¿Cuáles parejas de estos eventos son independientes? ¿Cuáles son excluyentes? Problema 3 Muestra que $latex \emptyset$ es independiente de cualquier otro evento. ¿Existe otro evento así? Problema 4 Considera un experimento  S que se repite  n veces ($latex n\ge 2$), y sea $latex s\in S$. Si  A es el evento que  s sale primero, y  B es el evento que  s sale al final, muestra que  A y  B son independientes. Problema 5 Sea  S = {1, 2, ..., 100} y seleccionamos un subconjunto  X al azar uniformemente, de tal forma que cualquier subconjunto tiene la misma probabilidad de ser selec...