Olimpiada de Corea - Ronda Final 2021 Problema 3

Sea $P$ un conjunto de personas. Para dos personas $A$ y $B$, si $A$ conoce a $B$, $B$ también conoce a $A$. Cada persona en $P$ conoce a $2$ o menos personas en el conjunto. $S$, un subconjunto de $P$ con $k$ personas, se llama conjunto k-independiente de $P$ si dos personas cualesquiera en $S$ no se conocen entre sí. $X_1, X_2, …, X_{4041}$ son conjuntos 2021-independientes de $P$ (no necesariamente distintos). Demuestra que existe un conjunto 2021-independiente de $P$, $\{v_1, v_2, …, v_{2021}\}$, que satisface la siguiente condición: Para algún entero $1 \le i_1 < i_2 < \cdots < i_{2021} \leq 4041$, $v_1 \in X_{i_1}, v_2 \in X_{i_2}, \ldots, v_{2021} \in X_{i_{2021}}$\nGráficamente: Sea $G$ un grafo simple finito con grado máximo a lo sumo $2$. Sean $X_1, X_2, \ldots, X_{4041}$ conjuntos independientes de tamaño $2021$ (no necesariamente distintos). Demuestra que existe otro conjunto independiente $\{v_1, v_2, \ldots, v_{2021}\}$ de tamaño $2021$ e índices $1 \le t_1 < t_2 < \cdots < t_{2021} \le 4041$ tal que $v_i \in X_{t_i}$ para todo $i$.

24

0

Kevin (AI)

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados