## 1. (Estadística en el problema de selección de secretarie) Implemente el Algoritmo de generación de permutaciones uniforme mediante sorting en $S_n$, que vimos en clase.

### a) Escriba el código de su implementación
El siguiente código define una función en Python para generar una permutación aleatoria y uniforme de un conjunto de enteros desde 1 hasta n.
Utilizamos **random.shuffle()** debido a que es una manera eficiente de hacer esto en un **O(n)**, además utiliza el algoritmo de Fisher-Yates para mezclar los elementos, que es un algoritmo conocido por producir una permutación aleatoria uniforme.

import random

def generar_permutacion_uniforme(n):
    # Crear una lista de indices que representan 
    # los candidatos
    elementos = list(range(1, n+1))
    # Mezclar los elementos in situ para obtener 
    # una permutación uniforme
    random.shuffle(elementos)
    return elementos

if __name__ == '__main__':
    # Ejemplo de uso
    n = 10
    permutacion = generar_permutacion_uniforme(n)
    print(permutacion)

#Output: [4, 1, 3, 5, 10, 9, 8, 6, 2, 7]

### b) Para n = 20 candidatos genere una muestra de m = 100 permutaciones y escriba las 5 primeras y las 5 últimas.

Para resolver esta parte, generamos una muestra de $m = 100$ permutaciones para $n = 20$ candidatos utilizando Python. A continuación se muestra el código que realiza esta tarea y muestra las 5 primeras y las 5 últimas permutaciones:

import random

def generar_muestra_permutaciones(n, m):
    muestra = [generar_permutacion_uniforme(n) for _ in range(m)]
    return muestra

def imprimir_permutaciones(muestra):
    # Asumiendo que la muestra tiene al menos 10 elementos
    print("Las 5 primeras permutaciones son:")
    for permutacion in muestra[:5]:
        print(permutacion)
    
    print("\nLas 5 últimas permutaciones son:")
    for permutacion in muestra[-5:]:
        print(permutacion)

if __name__ == '__main__':
    # Utilizamos las funciones definidas anteriormente
    n = 20  # Numero de candidatos
    m = 100  # Tamaño de la muestra
    muestra_permutaciones = generar_muestra_permutaciones(n, m)
    imprimir_permutaciones(muestra_permutaciones)

""" Output
Las 5 primeras permutaciones son:
[2, 12, 19, 4, 16, 10, 17, 8, 14, 15, 13, 18, 7, 1, 11, 6, 20, 5, 9, 3]
[6, 12, 15, 9, 14, 11, 5, 1, 13, 17, 4, 19, 7, 8, 20, 18, 2, 16, 10, 3]
[6, 2, 17, 3, 16, 7, 4, 14, 1, 20, 9, 15, 10, 8, 5, 18, 12, 19, 13, 11]
[4, 6, 8, 9, 13, 1, 2, 20, 5, 16, 19, 11, 15, 3, 14, 10, 7, 12, 18, 17]
[8, 7, 9, 10, 13, 6, 16, 15, 1, 4, 19, 12, 2, 17, 18, 14, 3, 11, 5, 20]

Las 5 últimas permutaciones son:
[7, 17, 1, 15, 5, 13, 6, 19, 16, 10, 12, 3, 8, 11, 2, 14, 9, 20, 4, 18]
[8, 19, 3, 20, 2, 15, 11, 12, 16, 17, 14, 4, 10, 1, 7, 18, 6, 5, 9, 13]
[17, 6, 11, 15, 8, 16, 18, 14, 4, 3, 13, 5, 12, 19, 2, 7, 10, 20, 1, 9]
[4, 20, 6, 18, 1, 14, 15, 19, 9, 17, 16, 7, 11, 10, 12, 5, 8, 3, 13, 2]
[15, 20, 10, 4, 11, 12, 2, 3, 14, 1, 7, 13, 8, 18, 9, 5, 16, 19, 17, 6] """

### c) Marque los candidatos en que la firmas deberían hacer contrataciones si el ranqueo de candidatos está dado por las diez permutaciones que generó en el punto anterior (en el problema de selección de asistente que vimos en clase).

Utilizamos la estrategia clásica del problema de selección de secretaria. A continuación, se describe cómo podríamos marcar a los candidatos para la contratación basándonos en las permutaciones generadas:

1. Observar las primeras $\approx n/e$ permutaciones sin hacer ninguna contratación. Para $n = 20$, esto significa observar aproximadamente los primeros 7 candidatos.
2. Después del periodo de exploración, seleccionamos el siguiente candidato que es mejor que todos los que hemos visto hasta ese momento.
3. Repetimos este proceso para cada una de las 10 permutaciones que hemos generado.

Criterio: El candidato mejor ranqueado será aquel de menor valor númerico, es decir, el número del elemento permutado será su posición en el ranking.

El código para implementar esta estrategia en Python sería el siguiente:

import math

def encontrar_candidatos_para_contratar(permutacion):
    n = len(permutacion)
    mejor_hasta_ahora = min(permutacion[:int(n/math.e)])
    for i in range(int(n/math.e), n):
        if permutacion[i] < mejor_hasta_ahora:
            return i  #Retornar la posicion para contratacion
    return "Nadie"  # Si no se encuentra ninguno mejor, 
                    # no contratar a nadie

if __name__ == '__main__':
    candidatos_para_contratar = (
        [encontrar_candidatos_para_contratar(perm) for 
         perm in muestra_permutaciones[:5]] #Primeras 5
        + [encontrar_candidatos_para_contratar(perm) for 
           perm in muestra_permutaciones[-5:]] #Ultimas 5
    )

    for i in candidatos_para_contratar:
        print(i, end = ", ")
        
# Output: 13, 7, 8, Nadie, 8, Nadie, 13, 8, Nadie, 9

""" Result, seleccionados marcados como (*x*)
Las 5 primeras:
[2, 12, 19, 4, 16, 10, 17, 8, 14, 15, 13, 18, 7, *1*, 11, 6, 20, 5, 9, 3]
[6, 12, 15, 9, 14, 11, 5, *1*, 13, 17, 4, 19, 7, 8, 20, 18, 2, 16, 10, 3]
[6, 2, 17, 3, 16, 7, 4, 14, *1*, 20, 9, 15, 10, 8, 5, 18, 12, 19, 13, 11]
[4, 6, 8, 9, 13, 1, 2, 20, 5, 16, 19, 11, 15, 3, 14, 10, 7, 12, 18, 17]
[8, 7, 9, 10, 13, 6, 16, 15, *1*, 4, 19, 12, 2, 17, 18, 14, 3, 11, 5, 20]

Las 5 últimas permutaciones son:
[7, 17, 1, 15, 5, 13, 6, 19, 16, 10, 12, 3, 8, 11, 2, 14, 9, 20, 4, 18]
[8, 19, 3, 20, 2, 15, 11, 12, 16, 17, 14, 4, 10, *1*, 7, 18, 6, 5, 9, 13]
[17, 6, 11, 15, 8, 16, 18, 14, *4*, 3, 13, 5, 12, 19, 2, 7, 10, 20, 1, 9]
[4, 20, 6, 18, 1, 14, 15, 19, 9, 17, 16, 7, 11, 10, 12, 5, 8, 3, 13, 2]
[15, 20, 10, 4, 11, 12, 2, 3, 14, *1*, 7, 13, 8, 18, 9, 5, 16, 19, 17, 6] """

### d) Escriba un código que reciba una permutación y calcule el número de candidatos que la firma debería contratar en el problema de selección de asistente que vimos en clase).

Escribimos un código en Python que, dada una permutación de candidatos, calcule el número de candidatos que la firma debería contratar. Aplicaremos la estrategia óptima del problema de selección de secretaria.

El código es el siguiente:

import math

def calcular_contrataciones(permutacion):
    n = len(permutacion)
    umbral = int(n / math.e)  # Rechazar los primeros n/e candidatos
    mejor_hasta_ahora = min(permutacion[:umbral])
    contrataciones = 0
    
    for i in range(umbral, n):
        if permutacion[i] < mejor_hasta_ahora:
            contrataciones += 1
            mejor_hasta_ahora = permutacion[i]
    
    return contrataciones

if __name__ == '__main__':
    n = 20
    permutacion_ejemplo = generar_permutacion_uniforme(n)
    numero_contrataciones = calcular_contrataciones(permutacion_ejemplo)
    print(permutacion_ejemplo)
    print(f'Número de candidatos a contratar: {numero_contrataciones}')


#Output
# [17, 5, 6, 13, 9, 12, 19, 16, 15, 18, 11, 1, 20, 10, 2, 8, 7, 4, 3, 14]
# Número de candidatos a contratar: 1

### e) Para muestras de $m = 100$, $m = 500$ y $m = 1000$ permutaciones haga un dibujo que contenga, en un solo par de ejes:
1. Un histograma del número de contrataciones realizadas en cada permutación de su muestra (ver por ejemplo [matplotlib histograms](https://www.w3schools.com/python/matplotlib_histograms.asp))
2. Una recta vertical en el valor teórico que vimos en clase.
3. Una recta vertical en el número promedio de contrataciones realizadas.

#### Respuesta:
Usaremos Python junto con Matplotlib para generar histogramas y las líneas verticales requeridas. El código a continuación generará las muestras de permutaciones, creará un histograma del número de contrataciones para cada muestra y añadirá líneas verticales representando el valor teórico y el número promedio de contrataciones.

El código en Python es el siguiente:

import matplotlib.pyplot as plt
import numpy as np

def generar_histograma_contrataciones(muestras, valor_teorico):
    fig, ax = plt.subplots()
    for m in muestras:
        permutaciones = generar_muestra_permutaciones(20, m)
        contrataciones = [calcular_contrataciones(perm) for 
                          perm in permutaciones]
        promedio_contrataciones = np.mean(contrataciones)

        # Histograma de contrataciones
        ax.hist(contrataciones, bins=range(1, max(contrataciones)
           + 2), alpha=0.5, label=f'm={m}')
        
        # Linea vertical para el valor promedio de contrataciones
        ax.axvline(promedio_contrataciones, color='red', 
                   linestyle='dashed', linewidth=1)
        
    # Linea vertical para el valor teorico
    ax.axvline(valor_teorico, color='blue', linestyle='solid', 
               linewidth=2, label='Valor teorico')
    
    ax.set_xlabel('Número de contrataciones')
    ax.set_ylabel('Frecuencia')
    ax.legend()
    plt.show()

if __name__ == '__main__':
    muestras = [100, 500, 1000]
    valor_teorico = 20/math.e  
    generar_histograma_contrataciones(muestras, valor_teorico)


## 2. (Puntos fijos en permutaciones aleatorias) Recuerde que los puntos fijos de una permutación $\sigma \in S_n$ son aquellos índices $i \in \{1, \ldots, n\}$ con $\sigma(i) = i$

### a) Para un entero $j$ cualquiera defina la variable aleatoria $Y(j) : S_n \to \mathbb{R}$ dada por
$$
Y(j)(\sigma) =
\begin{cases}
1, & \text{si } \sigma(j) = j \\
0, & \text{de lo contrario}
\end{cases}
$$
Si $P$ es la medida de probabilidad uniforme en $S_n$, calcule $E[Y(j)]$ dando un argumento preciso para su respuesta.

#### Respuesta:

Para calcular la esperanza $E[Y(j)]$ de la variable aleatoria $Y(j)$, definida en el conjunto de permutaciones $S_n$ con la medida de probabilidad uniforme, observamos que $Y(j)$ toma el valor de 1 si $\sigma(j) = j$ y 0 de lo contrario.

Todas las permutaciones en $S_n$ son igualmente probables, por lo que significa que la probabilidad de que un elemento específico $j$ sea un punto fijo en una permutación aleatoria, es decir, que $\sigma(j) = j$, es la misma para cada $j$.

Para un $j$ fijo, hay exactamente $(n-1)!$ permutaciones en $S_n$ que mantienen $j$ como un punto fijo, porque las permutaciones de los restantes $n-1$ elementos pueden ser cualquiera. Dado que hay $n!$ permutaciones totales en $S_n$, la probabilidad $P(Y(j) = 1)$ de que $j$ sea un punto fijo es:

$$
P(Y(j) = 1) = \frac{(n-1)!}{n!} = \frac{1}{n}
$$

Por otro lado, la probabilidad de que $j$ no sea un punto fijo es $P(Y(j) = 0) = 1 - \frac{1}{n}$.

La esperanza de $Y(j)$, o sea $E[Y(j)]$, se calcula ponderando cada posible valor que $Y(j)$ puede tomar con su respectiva probabilidad de esta forma:

$$
E[Y(j)] = 1 \cdot P(Y(j) = 1) + 0 \cdot P(Y(j) = 0) = 1 \cdot \frac{1}{n} + 0 \cdot \left(1 - \frac{1}{n}\right) = \frac{1}{n}
$$

Por lo tanto, para cualquier $j$, la esperanza de $Y(j)$ en una permutación aleatoria uniforme de $S_n$ es $\frac{1}{n}$, lo que significa que se espera que cada elemento sea un punto fijo con probabilidad $\frac{1}{n}$, independientemente de $j$.

### b) Use la parte (a) para encontrar el número esperado de puntos fijos de una permutación aleatoria de $S_n$, elegida uniformemente.

Ya que establecimos que $E[Y(j)] = \frac{1}{n}$ para un punto fijo $j$ específico, el número esperado de puntos fijos en una permutación aleatoria será la suma de las expectativas para cada posición individual desde 1 hasta $n$.

Dado que las variables aleatorias $Y(j)$ para $j=1, \ldots, n$ son todas idénticas e independientes (cada una indicando si el elemento $j$ es un punto fijo o no), el número esperado de puntos fijos en total es simplemente la suma de sus esperanzas individuales.

Si llamamos $X$ al número total de puntos fijos en una permutación, entonces $X = Y(1) + Y(2) + \ldots + Y(n)$ y la esperanza de $X$ es la suma de las esperanzas de las $Y(j)$ individuales:

$$
E[X] = E[Y(1)] + E[Y(2)] + \ldots + E[Y(n)] = n \cdot \frac{1}{n} = 1
$$

Por lo tanto, el número esperado de puntos fijos en una permutación aleatoria uniforme de $S_n$ es 1.

## 3. (Probabilidad de éxito de nuestra construcción de permutaciones aleatorias). Suponga que $p_1, \ldots, p_N$ son variables aleatorias independientes, cada una uniforme en $\{1, 2, \ldots, N^3\}$.

### a) Demuestre que la probabilidad de que $(p_1, \ldots, p_N)$ no tenga repeticiones es por lo menos $1 - \frac{1}{n}$.

Para calcular la probabilidad de que todas las variables aleatorias sean distintas, es decir, que no haya repeticiones, consideramos cada variable una por una:

- La primera variable, $p_1$, puede tomar cualquier valor sin restricciones.
- La segunda variable, $p_2$, debe ser diferente de $p_1$. Hay $N^3$ opciones posibles y solo una de ellas está restringida, por lo que la probabilidad de que $p_2$ no sea igual a $p_1$ es $\frac{N^3 - 1}{N^3}$.
- De forma similar, $p_3$ debe ser diferente de $p_1$ y $p_2$, y la probabilidad de que esto suceda es $\frac{N^3 - 2}{N^3}$.

Continuamos este proceso hasta llegar a la última variable, $p_N$, cuya probabilidad de ser distinta de todas las anteriores es $\frac{N^3 - (N - 1)}{N^3}$.

La probabilidad de que no haya repeticiones es el producto de estas probabilidades individuales:

$$
P(\text{sin repeticiones}) = \frac{N^3}{N^3} \times \frac{N^3 - 1}{N^3} \times \frac{N^3 - 2}{N^3} \times \ldots \times \frac{N^3 - (N - 1)}{N^3}
$$

Este producto se puede simplificar cancelando un factor de $N^3$ de cada término en el numerador y el denominador:

$$
P(\text{sin repeticiones}) = \left(1 - \frac{0}{N^3}\right) \left(1 - \frac{1}{N^3}\right) \left(1 - \frac{2}{N^3}\right) \ldots \left(1 - \frac{N - 1}{N^3}\right)
$$

Como $N$ se hace grande, los términos de la forma $\frac{k}{N^3}$ (donde $k$ es un entero entre 0 y $N - 1$) se vuelven muy pequeños, y la probabilidad $P(\text{sin repeticiones})$ se acerca a 1. Esto nos da:

$$
P(\text{sin repeticiones}) \geq \left(1 - \frac{N - 1}{N^3}\right)^N
$$

Podemos notar que $N - 1 < N$ y $N^2 < N^3$ para $N > 1$, lo que nos permite estimar:

$$
P(\text{sin repeticiones}) \geq \left(1 - \frac{N}{N^3}\right)^N = \left(1 - \frac{1}{N^2}\right)^N
$$

Usando la desigualdad $(1 - \frac{1}{x})^x \geq 1 - \frac{1}{x}$ para $x > 1$, obtenemos:

$$
P(\text{sin repeticiones}) \geq 1 - \frac{1}{N}
$$

Por lo tanto, hemos demostrado que la probabilidad de que no haya repeticiones en $(p_1, \ldots, p_N)$ es al menos $1 - \frac{1}{N}$.

### b) Una moneda cae cara con probabilidad $p$ y sello con probabilidad $q = 1 - p$. Calcule el número esperado de lanzamientos hasta que la moneda caiga cara por primera vez.

Para calcular el número esperado de lanzamientos hasta que la moneda caiga cara por primera vez, utilizamos el valor esperado de una distribución geométrica.

El valor esperado $E[X]$ para una variable aleatoria $X$ que sigue una distribución geométrica con probabilidad de éxito $p$ (en nuestro caso, obtener cara) se calcula como:

$$
E[X] = \frac{1}{p}
$$

Por lo tanto, el número esperado de lanzamientos hasta obtener la primera cara es simplemente el recíproco de la probabilidad de obtener cara en un lanzamiento $p$.

### c) Combinando los dos items anteriores, calcule el número esperado de ejecuciones que debe hacer nuestro Algoritmo de permutación uniforme mediante sorting antes de que genere una permutación (recuerde que el algoritmo se ejecuta repetidas veces hasta que las prioridades $p_i$ salgan todas distintas así que el problema pregunta por el número esperado de intentos antes de que esto suceda). (Sugerencia: Mezcle las partes (a) y (b) y note que su respuesta debe depender de $N$).

Para calcular el número esperado de ejecuciones que se deben hacer en el algoritmo de permutación uniforme mediante sorting antes de generar una permutación sin repeticiones, consideramos el número esperado de intentos en una distribución geométrica donde la "probabilidad de éxito" es la probabilidad de no tener repeticiones en una sola ejecución del algoritmo.

De la parte (a), sabemos que la probabilidad de que no haya repeticiones en una sola ejecución del algoritmo es por lo menos $1 - \frac{1}{N}$. Por lo tanto, el número esperado de ejecuciones del algoritmo hasta obtener una permutación sin repeticiones es el inverso de esta probabilidad.

Si denotamos la probabilidad de no tener repeticiones como $P(\text{sin repeticiones})$, entonces el número esperado de ejecuciones del algoritmo, denotado como $E[\text{ejecuciones}]$, es:

$$
E[\text{ejecuciones}] = \frac{1}{P(\text{sin repeticiones})}
$$

Dado que $P(\text{sin repeticiones}) > 1 - \frac{1}{N}$, podemos deducir que:

$$
E[\text{ejecuciones}] < \frac{1}{1 - \frac{1}{N}}
$$

Haciendo el inverso, obtenemos:

$$
E[\text{ejecuciones}] < \frac{N}{N - 1}
$$

Esto nos indica que el número esperado de ejecuciones del algoritmo es menor que $\frac{N}{N - 1}$, el cual depende del valor de $N$. A medida que $N$ se hace grande, el número esperado de ejecuciones se acerca a $1$, lo que significa que es muy probable obtener una permutación sin repeticiones en las primeras ejecuciones del algoritmo.

## 4. (Coincidencias planetarias) Un planeta está habitado por $k$ habitantes $1,2,...,k$ y da una vuelta a su estrella cada $n$ días (donde un día es un giro del planeta alrededor de su propio eje).

### a) Para habitantes $i,j \in \{1,...,k\}$ sea

$$
X_{ij} = \begin{cases}
1, & \text{si los habitantes } i \text{ y } j \text{ cumplen años el mismo día} \\
0, & \text{de lo contrario}
\end{cases}
$$

Calcule $E[X_{ij}]$ asumiendo que los cumpleaños se distribuyen de manera uniforme en los distintos días. Justifique su respuesta de manera precisa.

#### Respuesta:

Cuando decimos que los cumpleaños se distribuyen de manera uniforme en los $n$ días del año, estamos asumiendo que no hay preferencia hacia ningún día en particular para que ocurran los cumpleaños. Esto implica que cada día es igualmente probable para ser el cumpleaños de cualquier habitante. Esto significa que la probabilidad de que cualquier habitante celebre su cumpleaños en un día específico es de $1/n$.

Por lo tanto, para dos habitantes diferentes $i$ y $j$, hay $n$ días posibles en los que el habitante $i$ podría celebrar su cumpleaños. Independientemente de qué día sea, la probabilidad de que el habitante $j$ también celebre su cumpleaños ese mismo día es de $1/n$. Esto se debe a la suposición de la distribución uniforme, que no cambia la probabilidad basada en la elección del día del primer habitante.

La variable aleatoria $X_{ij}$ indica si los habitantes $i$ y $j$ comparten el mismo cumpleaños. Tomará el valor de $1$ si ambos cumplen años el mismo día, lo cual ocurre con una probabilidad de $\frac{1}{n}$, y tomará el valor de $0$ si no cumplen años el mismo día, lo cual ocurre con una probabilidad de $1 - \frac{1}{n}$. La esperanza $E[X_{ij}]$ es entonces la suma ponderada de estos valores posibles por sus probabilidades correspondientes:

$$
E[X_{ij}] = 1 \cdot P(X_{ij} = 1) + 0 \cdot P(X_{ij} = 0) = 1 \cdot \frac{1}{n} + 0 \cdot (1 - \frac{1}{n}) = \frac{1}{n}
$$

Todos los días tienen la misma probabilidad de ser elegidos como el cumpleaños de cualquier habitante, lo que lleva a la probabilidad de coincidencia de cumpleaños de $\frac{1}{n}$ para cualquier par de habitantes.

### b) Sea $X$ la variable aleatoria que cuenta el número de parejas de los $k$ individuos que cumplen años el mismo día. Se pide utilizar la parte (a) para calcular $E[X]$, justificando matemáticamente la respuesta.

En la parte (a), calculamos $E[X_{ij}]$ para una pareja de individuos $(i, j)$ y encontramos que era $\frac{1}{n}$. Dado que $X$ es la suma de todas las variables aleatorias $X_{ij}$ para cada par único de individuos, podemos sumar las esperanzas de cada $X_{ij}$ para obtener $E[X]$.

Hay $\binom{k}{2} = \frac{k(k-1)}{2}$ pares únicos de individuos en un conjunto de $k$ individuos. Dado que cada par tiene una esperanza de $\frac{1}{n}$ de cumplir años el mismo día, y asumiendo la independencia de los cumpleaños de cada par de individuos, la esperanza de $X$ es:

$$
E[X] = \binom{k}{2} \cdot E[X_{ij}] = \frac{k(k-1)}{2} \cdot \frac{1}{n}
$$

Por lo tanto, la esperanza del número de parejas que cumplen años el mismo día es $\frac{k(k-1)}{2n}$.

### c) Use el punto anterior para demostrar que si hay por lo menos $1 + \sqrt{2n}$ individuos en un cuarto entonces deberíamos esperar que al menos dos tengan el mismo cumpleaños.

Partimos de la esperanza calculada en b), $E[X] = \frac{k(k-1)}{2n}$. Se plantea la situación en la que esta esperanza es al menos 1, lo que significaría que se espera al menos una pareja de individuos que cumplan años el mismo día:

$$
\frac{k(k-1)}{2n} \geq 1
$$

Resolviendo la desigualdad para $k$, se obtiene que:

$$
k^2 - k - 2n \geq 0
$$

La solución negativa no tiene sentido en este contexto porque estaríamos hablando de un número negativo de personas, así que tomamos la solución positiva de la ecuación cuadrática $k^2 - k - 2n = 0$ que es:

$$
k = \frac{1 + \sqrt{1 + 8n}}{2}
$$

Dado que buscamos un número entero de individuos que sea al menos tan grande como esta solución, redondeamos hacia arriba y obtenemos que al menos $1 + \sqrt{2n}$ individuos garantizarán que se espere al menos una coincidencia de cumpleaños.

### d) Convierta en resultados numéricos el cálculo anterior para el planeta Tierra. ¿Cómo explicaría este resultado en una frase sencilla?

En la Tierra consideramos que hay $n = 365$ días en un año (sin tener en cuenta años bisiestos). Sustituyendo esto en la fórmula encontrada en c), obtenemos:

$$
k = \frac{1 + \sqrt{1 + 8 \cdot 365}}{2} \approx 1 + \sqrt{2 \cdot 365}
$$

Realizando el cálculo:

$$
k \approx 1 + \sqrt{730} \approx 1 + 27 \approx 28
$$

Por lo tanto, en una habitación con 28 personas o más, esperaríamos que al menos dos individuos cumplan años el mismo día. En una frase sencilla: "En un grupo de 28 personas, es probable que dos de ellas cumplan años el mismo día".

## 5. (Árboles generadores conectando puntos aleatorios) Escriba un programa que construya 20 parejas de puntos aleatorios en el cuadrado $[0, 1] \times [0, 1]$ con coordenadas $(X_i, Y_i)$ independientes y uniformemente distribuidas en $[0, 1]$ (ver [numpy.random.uniform](https://numpy.org/doc/stable/reference/random/generated/numpy.random.uniform.html))

### a) Escriba el código de su implementación.

Escribiremos un programa en Python que genere 20 pares de puntos aleatorios dentro del cuadrado unitario $[0, 1] \times [0, 1]$. Cada punto tendrá coordenadas $(X_i, Y_i)$ que son independientes y uniformemente distribuidas entre 0 y 1. Utilizaremos la función `numpy.random.uniform` para generar las coordenadas aleatorias.

Aquí está el código de Python para generar los puntos:

import numpy as np

def generar_puntos_aleatorios(num_puntos):
    # Generar puntos aleatorios en el cuadrado [0, 1] x [0, 1]
    return np.random.uniform(low=0.0, high=1.0, size=(num_puntos, 2))

def imprimir_puntos(puntos):
    # Imprimir los puntos generados
    for i, punto in enumerate(puntos):
        print(f"Punto {i+1}: (X_{i+1}, Y_{i+1}) = ({punto[0]}, {punto[1]})")

if __name__ == '__main__':    
    num_puntos = 20  # Número de puntos a generar
    puntos = generar_puntos_aleatorios(num_puntos)
    imprimir_puntos(puntos)

### b) Implemente una rutina que dibuje los puntos (por ejemplo mediante ```pyplot```) y úsela para producir las gráficas (los veinte puntos) de tres muestras distintas.

import numpy as np
import matplotlib.pyplot as plt


def generar_puntos_aleatorios(num_puntos):
    # Generar puntos aleatorios en el cuadrado [0, 1] x [0, 1]
    return np.random.uniform(low=0.0, high=1.0, size=(num_puntos, 2))


def dibujar_puntos(puntos, titulo):
    # Dibujar los puntos en un gráfico
    plt.figure(figsize=(5, 5))
    plt.scatter(puntos[:, 0], puntos[:, 1], c='blue', label='Puntos aleatorios')
    plt.title(titulo)
    plt.xlabel('X')
    plt.ylabel('Y')
    plt.grid(True)
    plt.xlim(0, 1)
    plt.ylim(0, 1)
    plt.legend()
    plt.show()


if __name__ == '__main__':    
    num_puntos = 20  # Número de puntos a generar

    # Generar y dibujar tres muestras distintas
    for i in range(1, 4):
        puntos = generar_puntos_aleatorios(num_puntos)
        dibujar_puntos(puntos, f'Muestra {i}')

### c) Defina un grafo con vértices $\{1, \ldots, 20\}$ y ponga aristas entre todo par de vértices con costos $c(i, j)$ dados por las distancias entre los puntos respectivos, es decir
$$ c(i, j) = \sqrt{(X_i - X_j)^2 + (Y_i - Y_j)^2}. $$
Implemente un código que calcule el minimum spanning tree (MST) de un grafo de estos.

import numpy as np
from scipy.spatial.distance import pdist, squareform
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
import matplotlib.pyplot as plt


def generar_puntos_aleatorios(num_puntos):
    return np.random.uniform(low=0.0, high=1.0, size=(num_puntos, 2))

def calcular_mst(puntos):
    distancia_matriz = squareform(pdist(puntos, 'euclidean'))
    grafo = csr_matrix(distancia_matriz)
    mst = minimum_spanning_tree(grafo)
    return mst.toarray().astype(float)

def visualizar_mst(puntos, mst):
    # Visualizar los puntos
    plt.scatter(puntos[:, 0], puntos[:, 1], c='red')

    # Dibujar las aristas del MST
    for i in range(len(puntos)):
        for j in range(len(puntos)):
            if mst[i][j] > 0:
                punto_inicio = puntos[i]
                punto_final = puntos[j]
                plt.plot([punto_inicio[0], punto_final[0]], [punto_inicio[1], punto_final[1]], 'b-')

    plt.title('Minimum Spanning Tree')
    plt.show()


if __name__ == '__main__':
    num_puntos = 20
    puntos = generar_puntos_aleatorios(num_puntos)
    mst = calcular_mst(puntos)

    print("Matriz del MST:")
    print(mst)

    visualizar_mst(puntos, mst)

### d) Dibuje los MST de las tres muestras de la primera parte.

import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial.distance import pdist, squareform
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree


def generar_puntos_aleatorios(num_puntos):
    # Generar puntos aleatorios en el cuadrado [0, 1] x [0, 1]
    return np.random.uniform(low=0.0, high=1.0, size=(num_puntos, 2))


def calcular_mst(puntos):
    # Calcular la matriz de distancia euclidiana
    distancia_matriz = squareform(pdist(puntos, 'euclidean'))
    # Crear un grafo con la representación de matriz dispersa
    grafo = csr_matrix(distancia_matriz)
    # Calcular el MST usando la matriz de distancia
    mst = minimum_spanning_tree(grafo)
    return mst.toarray().astype(float)


def dibujar_mst(puntos, mst, titulo):
    plt.figure(figsize=(6, 6))
    plt.title(titulo)
    plt.xlabel('X')
    plt.ylabel('Y')
    plt.scatter(puntos[:, 0], puntos[:, 1], c='red', label='Puntos')

    # Dibujar las aristas del MST
    for i in range(len(puntos)):
        for j in range(len(puntos)):
            if mst[i][j] != 0:
                punto_inicio = puntos[i]
                punto_final = puntos[j]
                plt.plot([punto_inicio[0], punto_final[0]], 
                [punto_inicio[1], punto_final[1]], 'b-')

    plt.grid(True)
    plt.legend()
    plt.show()


if __name__ == '__main__':
    num_puntos = 20

    # Generar y dibujar el MST para tres muestras distintas
    for i in range(1, 4):
        puntos = generar_puntos_aleatorios(num_puntos)
        mst = calcular_mst(puntos)
        dibujar_mst(puntos, mst, f'MST de la muestra {i}')

### e) Haga un histograma de la longitud $c(T)$ de estos MST para conjuntos de $m = 100, 200, 300$ muestras de 20 puntos y dibuje una recta vertical en el valor promedio de estas longitudes.

import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial.distance import pdist, squareform
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree

def generar_puntos_aleatorios(num_puntos):
    # Generar puntos aleatorios en el cuadrado [0, 1] x [0, 1]
    return np.random.uniform(low=0.0, high=1.0, size=(num_puntos, 2))

def calcular_mst(puntos):
    # Calcular la matriz de distancia euclidiana
    distancia_matriz = squareform(pdist(puntos, 'euclidean'))
    # Crear un grafo con la representación de matriz dispersa
    grafo = csr_matrix(distancia_matriz)
    # Calcular el MST usando la matriz de distancia
    mst = minimum_spanning_tree(grafo)
    return mst

def calcular_longitud_mst(mst):
    # Sumar los pesos de todas las aristas en el MST
    return mst.toarray().astype(float).sum()

def hacer_histograma(muestras, num_puntos):
    longitudes_mst = []
    # Calcular la longitud del MST para cada muestra
    for _ in range(muestras):
        puntos = generar_puntos_aleatorios(num_puntos)
        mst = calcular_mst(puntos)
        longitud = calcular_longitud_mst(mst)
        longitudes_mst.append(longitud)

    promedio_longitudes = np.mean(longitudes_mst)

    # Dibujar histograma
    plt.hist(longitudes_mst, bins=20, color='skyblue', edgecolor='black')
    plt.axvline(promedio_longitudes, color='red', linestyle='dashed', linewidth=2, label=f'Promedio: {promedio_longitudes:.4f}')
    plt.title(f'Histograma de longitudes del MST para {muestras} muestras')
    plt.xlabel('Longitud del MST')
    plt.ylabel('Frecuencia')
    plt.legend()
    plt.show()

if __name__ == '__main__':
    # Hacer histogramas para diferentes cantidades de muestras
    for muestras in [100, 200, 300]:
        hacer_histograma(muestras, 20)