Discreta Examen Julio 2023 Sol - Pagenumber

SOLUCIÓN – Examen
Matemática Discreta I
Viernes 28 de Julio de 2023
MO1 MO2 MO3 MO4 MO5
B A C B E
Múltiple Opción 1
Sea G un grafo simple, plano y conexo con 8 vértices, todos ellos de grado 3. Sea r la
cantidad de regiones de una inmersión plana de G. Entonces:
(A) r = 5; (B) r = 6; (C) r = 7; (D) r = 8; (E) Tal grafo no existe.
Solución - Múltiple Opción 1

Por el lema de handshaking 2|E| = 3|V | = 24, por lo que |E| = 12. Como el grafo es
simple, plano y conexo, vale la fórmula de Euler: |V | − |E| + r = 2, por lo que r = 6.
Un grafo conexo 3-regular con 6 caras, 8 vértices y 12 aristas es el cubo. Por lo tanto, la
opción correcta es la B.
Hallar la cantidad de relaciones de equivalencia en A = {1, 2, 3, 4, 5, 6} que tienen
exactamente 3 clases de equivalencia. (A) 90; (B) 120; (C) 150; (D) 180; (E) 210.

Se pide determinar la cantidad de particiones de {1, 2, 3, 4, 5, 6} en 3 conjuntos, que vale
S(6, 3) = Sob(6, 3)/3!. A partir del principio de inclusión y exclusión se deduce que
Sob(6, 3) = 36 − 31 26 + 32 16 = 540, por lo que S(6, 3) = 540/6 = 90, y la respuesta

correcta es la A.
Encontrar el menor entero positivo n que permita asegurar que, de cualquier forma que
se elijan n enteros distintos entre 1 y 100 inclusive, habrá dos de ellos cuya suma sea igual
a 50. (A) 75; (B) 76; (C) 77; (D) 78; (E) 79.

Notemos que N = {{1, 49}, {2, 48}, . . . , {24, 26}, {25}, {50}, {51}, . . . , {100}} tiene
precisamente 76 elementos. Sea X un subconjunto cualquiera de {1, . . . , 100} con 77
elementos. Definamos los nidos como los elementos de la partición N , y las palomas
como los elementos de X. Cada elemento de X pertenece a algún subconjunto de N ,
porque N es una partición de {1, . . . , 100}. En particular, cada paloma pertenece a
algún nido. Como |X| = 77 y |N | = 76, por el Principio del Palomar existe algún nido
que posee al menos dos palomas. En términos de X y de N , esto es que existen dos
elementos de X que son de la forma {i, 50 − i} para algún i ∈ {1, . . . , 24}, o
equivalentemente, que existen dos elementos diferentes pertenecientes a X cuya suma es
igual a 50. Esto prueba que todo subconjunto X de {1, . . . , 100} con 77 elementos
cumple la propiedad estudiada. Construyamos ahora un subconjunto de {1, . . . , 100}
con 76 elementos que no cumple la propiedad deseada. De hecho, si elegimos
Y = {1, 2, . . . , 25, 50, 51, . . . , 100} entonces Y tiene 76 elementos, y además no existen
dos elementos pertenecientes a Y cuya suma sea igual a 50. Luego el menor entero
positivo n que cumple la propiedad estudiada es n = 77, y la opción correcta es la C.
1
Sea an la cantidad de secuencias de largo n formadas con los números 0, 1, 2, 3 y 4 tales
que dos entradas consecutivas difieren en magnitud exactamente en 1 y además la última
entrada de la secuencia es 1 o 3. Hallar a21 .
Sugerencia: plantear una recurrencia homogénea de segundo orden para an .
(A) 3 × 210 ; (B) 2 × 310 ; (C) 311 ; (D) 5 × 210 ; (E) 4 × 310 .

Por simetrı́a, la cantidad de secuencias an que terminan en 1 es la misma que la de las
secuencias que terminan en 3. De hecho, toda secuencia x1 x2 · · · xn que termina en 1 se
corresponde de manera biyectiva con la secuencia y1 y2 · · · yn , donde yi = 4 − xi para cada
i ∈ {1, 2, . . . , n}, y dicha secuencia termina en 3.
Ahora, observemos que toda secuencia de largo n que termina en 1 tiene exactamente
3 maneras de ser extendida a una secuencia de largo n + 2 que termina en 1 o en 3, que
tienen precisamente los sufijos 121, 101, o bien 123. Por lo visto en el párrafo anterior,
también hay exactamente 3 maneras de extender a toda secuencia de largo n que termina
en 3 para obtener una secuencia de largo n + 2 que termina en 1 o en 3. Pero entonces se
cumple que an+2 = 3an , y además a1 = 2 (puesto que podemos empezar con 1 o bien con
3 Luego a21 = a1 × 310 = 2 × 310 , y la opción correcta es la B.
Sean A = {1, 2, . . . , 100} y B = {1, 2, . . . , 51}. Determinar la cantidad de funciones
sobreyectivas f de A en B tales que f (1) ≤ f (2) ≤ . . . ≤ f (100).
Sugerencia: considerar la cantidad de preimágenes de cada elemento de B.
A) 150!/(51!99!); (B) 150!/48!; (C) 150!/99!; (D) 99!/(48!51!); (E) 99!/49!50!.

Como f es sobreyectiva, cada i ∈ B tiene al menos un elemento de A que lo alcanza. Sea
xi la cantidad de preimágenes que tiene el elemento i. Como f es sobreyectiva, entonces
xi ≥ 1 para cada i ∈ B. Como f es función, cada elemento de A alcanza exactamente un
elemento de B, y hay en total 100 elementos en el conjunto A. Entonces x1 +x2 +· · ·+x51 =
100. Por último, notemos que como f es creciente entonces f se determina de manera
única con la cantidad de veces que se alcanza cada elemento. Hemos reducido el problema
a contar la cantidad de soluciones naturales de la ecuación x1 + x2 + · · · + x51 = 100 sujeto
a que xi ≥ 1 para cada i ∈ B. Tomando cambios de variable x′i = xi − 1 para cada i ∈ B
y reemplazando cada xi por x′i + 1 en la igualdad anterior, reducimos el problema a contar
soluciones naturales de (x′1 + 1) + (x′2 + 1) + · · · + (x′51 + 1) = 100, donde cada variable x′i
tiene dominio en los naturales. Entonces, basta con determinar la cantidad de soluciones
51
naturales de la ecuación x′1 + x′2 + · · · + x′51 = 100 − 51 = 49, que es igual a CR49 , y es lo
mismo que 99!/49!50!. Luego, la opción correcta es la E.
Ejercicio de Desarrollo 1
Sea (A, ≤) una relación de orden parcial, donde A es un conjunto finito y no vacı́o.
Queremos probar que A tiene algún elemento que es maximal. Primero consideremos la
relación (A, <), donde a < b si y sólo si a ≤ b y a 6= b. Notemos que < es transitiva.
Supongamos por absurdo que A no tiene ningún elemento maximal. Primero, como A
es no vacı́o, tomemos un elemento cualquiera a0 de A. Como a0 no es maximal, entonces
existe a1 ∈ A tal que a0 < a1 . Como a1 tampoco es maximal, entonces existe a2 ∈ A
tal que a1 < a2 . Repitiendo este razonamiento obtenemos un conjunto S = {an }n∈N ,
incluido en A. Además todos los elementos de S son distintos: dados m < n ∈ N, la
propiedad transitiva nos da que am < am+1 < · · · an , de donde am < an . Esto implica que
S es infinito, lo cual es una contradicción porque A es finito. La contradicción proviene
de haber supuesto inicialmente que el conjunto A no tiene ningún elemento maximal.
Entonces, existe algún elemento de A que es maximal, como querı́amos demostrar. 2
(1) Asumiremos como cierto el siguiente resultado.

Lema 1. Todo árbol con al menos dos vértices tiene algún vértice de grado 1.
Probaremos, mediante el principio de inducción completa sobre el número de
vértices, que todo árbol finito T = (V, E) cumple que |E| = |V | − 1. Para cada
entero positivo n consideremos la siguiente proposición:
P (n): todo árbol con exactamente n vértices tiene exactamente n − 1 aristas.
Queremos probar que ∀n ∈ Z+ se cumple P (n). El paso base consiste en

probar P (1). El único árbol con exactamente 1 vértice no tiene aristas. Como
0 = 1 − 1, entonces el paso base es cierto.
A continuación vamos a probar el paso inductivo. Sea h un entero positivo fijo

cualquiera. La hipótesis inductiva consiste en asumir que P (h) es cierta, es decir
que todo árbol con exactamente h vértices tiene exactamente h − 1 aristas.
Debemos probar que P (h + 1) es cierta.
Consideremos un árbol cualquiera T = (V, E) que tiene exactamente h + 1

vértices, es decir que |V | = h + 1. Como h es entero positivo entonces h + 1
también, y además h + 1 ≥ 2. Entonces, T satisface las hipótesis del Lema 1, y
por lo tanto existe algún vértice v de V que tiene grado 1. Sea T ′ = (V ′ , E ′ ) el
grafo que se obtiene de eliminar el vértice v de T , es decir que T ′ = T − v. Notar
que T ′ no tiene ciclos, puesto que T no los tenı́a y eliminar vértices no genera
ciclos. Además, el grafo T ′ también es conexo. De hecho, dados dos vértices
distintos x e y de T ′ , el mismo camino simple que existe en T con extremos x e y
no contiene al vértice v, puesto que v tiene grado 1. Entonces, V ′ es un árbol.
Además, por construcción, tenemos que T ′ tiene exactamente un vértice menos
que T y exactamente una arista menos que T , por lo que |E ′ | = |E| − 1 y
|V ′ | = |V | − 1. Como T ′ es un árbol que tiene exactamente h vértices, por
hipótesis inductiva se sigue que T ′ tiene exactamente h − 1 aristas. Pero entonces
|E| = |E ′ | + 1 = (h − 1) + 1 = h. Hemos probado que cualquier árbol con
exactamente h + 1 vértices tiene exactamente h aristas, es decir que hemos
probado que la proposición P (h + 1) es cierta.
Como Z+ es un conjunto que satisface el principio del buen orden y tanto el

paso base como el paso inductivo son ciertos, por el principio de inducción
completa concluimos que ∀n ∈ Z+ se cumple P (n), como querı́amos demostrar.
(2) Sea ahora G = (V ′ , E ′ ) un grafo simple conexo. Si G es acı́clico entonces es un

árbol, y por la parte anterior se cumple que |E ′ | = |V ′ | − 1. Si no, existe algún
ciclo Cn en G. Sea e una arista del ciclo. Notemos que G − e es conexo. En efecto,
cada vez que se utiliza la arista e dentro de un camino simple en G es posible
reemplazar su aparición por el camino dado por C − e. Si el grafo resultante G − e
fuese acı́clico, entonces el grafo G − e serı́a un árbol. Este mismo procedimiento
se repite una cantidad finita de veces, hasta obtener un grafo conexo y sin ciclos,
es decir, un árbol. Como debimos eliminar aristas del grafo G para obtener un
árbol, entonces se cumple que |E ′ | ≥ |V ′ | − 1, como querı́amos demostrar.
3
Examen – Matemática Discreta I
Miércoles 8 de febrero de 2023
Número de lista APELLIDO, Nombre Cédula de identidad
MO1 MO2 MO3 MO4 MO5 Des. 1 Des. 2 Puntaje Total
Sugerencia: pasar las respuestas de los ejercicios de múltiple opción cuidadosamente.

Lo completado aquı́ será lo único tenido en cuenta a la hora de corregir.
Cada respuesta correcta de múltiple opción vale 10 puntos.
Cada ejercicio de desarrollo correcto y completo vale 25 puntos.
Respuestas incorrectas restan 1 punto.
El examen se aprueba con 60 puntos. La duración del examen es de tres horas y media.
Sea A un subconjunto de n elementos distintos (n ≥ 2) del conjunto {1, 2, . . . , 100}.
Indicar el mı́nimo valor de n que garantiza que existen dos elementos distintos de A que
suman 50.
A) 74; B) 75; C) 76; D) 77; E) 78.
Determinar la cantidad de soluciones enteras de la ecuación x1 +x2 +x3 = 17 que cumplen
las siguientes restricciones −2 ≤ x1 ≤ 6, −2 ≤ x2 ≤ 6, −1 ≤ x3 ≤ 7.
(A) 5; (B) 6; (C) 7; (D) 8; (E) 9.
Determinar la cantidad de palabras que se pueden formar permutando las letras de la
palabra TACUAREMBO que verifican simultáneamente las siguientes tres condiciones:
i. Comienzan en T.
ii. Terminan en O.
iii. Contienen la palabra REM en alguna parte.
(A) 60; (B) 120; (C) 360; (D) 720; (E) 10080.
Se considera la sucesión de números reales (an )n∈N definida por la relación de recurrencia
an+2 − 5an+1 + 6an = 2n , (n ≥ 0) con a0 = 0 y a1 = −1. Entonces:
(A) a100 = 102 × 2100 ; (B) a100 = 42 × 3100 ; (C) a100 = 0; (D) a100 = −50 × 2100 ;
(E) a100 = −42 × 3100 .
Dados tres enteros positivos r, s y t, se define el grafo tripartito completo Kr,s,t como un
grafo tal que el conjunto de sus vértices es igual a la unión disjunta de tres subconjuntos
V1 , V2 y V3 con |V1 | = r, |V2 | = s, |V3 | = t, y cuyas aristas son todos los pares {a, b} tales
que a ∈ Vi , b ∈ Vj para algunos i 6= j ∈ {1, 2, 3}.
El grafo tripartito completo Kr,s,t tiene un circuito euleriano si y solo si
(A) r, s y t son todos pares;
(B) r, s y t son todos impares;
(C) r, s y t son todos pares o si hay dos pares y un impar;
(D) r, s y t son todos pares o si hay uno par y dos impares;
(E) r, s y t son todos pares o todos impares.
4
Se considera la relación binaria R de divisibilidad sobre N = {0, 1, 2, 3, 4, . . .}, definida
por:
a R b sii ∃n ∈ N, an = b .
(Es decir: a R b si y solo si b es múltiplo de a)
(1) Demostrar que R es una relación de orden sobre N
(2) ¿El orden R tiene mı́nimo? ¿máximo? Justificar las respuestas.
(3) ¿El orden R es un retı́culo? Justificar la respuesta.
(1) Enunciar (sin demostrar) la fórmula de Euler para grafos planos conexos.
(2) Probar que si G = (V, E) es un grafo plano sin lazos y conexo tal que |V | ≥ 3,
entonces |E| ≤ 3|V | − 6.
(3) Probar usando (2) que K5 no es plano.
Importante: justificar detalladamente cada paso de las demostraciones.
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

Discreta Examen Julio 2023 Sol - Pagenumber

Cargado por

Copyright:

Formatos disponibles

Discreta Examen Julio 2023 Sol - Pagenumber

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Discreta Examen Julio 2023 Sol - Pagenumber

Cargado por

Copyright:

Formatos disponibles

SOLUCIÓN – Examen

Solución - Múltiple Opción 1

Solución - Múltiple Opción 2

Solución - Múltiple Opción 3

Solución - Múltiple Opción 4

Solución - Múltiple Opción 5

(1) Asumiremos como cierto el siguiente resultado.

P (n): todo árbol con exactamente n vértices tiene exactamente n − 1 aristas.

Queremos probar que ∀n ∈ Z+ se cumple P (n). El paso base consiste en

A continuación vamos a probar el paso inductivo. Sea h un entero positivo fijo

Consideremos un árbol cualquiera T = (V, E) que tiene exactamente h + 1

Como Z+ es un conjunto que satisface el principio del buen orden y tanto el

(2) Sea ahora G = (V ′ , E ′ ) un grafo simple conexo. Si G es acı́clico entonces es un

MO1 MO2 MO3 MO4 MO5 Des. 1 Des. 2 Puntaje Total

Sugerencia: pasar las respuestas de los ejercicios de múltiple opción cuidadosamente.

Importante: justificar detalladamente cada paso de las demostraciones.

También podría gustarte