Olimpiada Programa de Invierno de Corea , Prueba de Práctica 2022 Problema 9
Sea $n\ge 2$ un entero positivo. $S$ es un conjunto de $2n$ aeropuertos. Para dos aeropuertos arbitrarios $A,B$ , si hay una vía aérea de $A$ a $B$ , entonces hay una vía aérea de $B$ a $A$ . Suponga que $S$ tiene solo un conjunto independiente de $n$ aeropuertos. Sea el conjunto independiente $X$ . Demuestre que existe un aeropuerto $P\in S\setminus X$ que satisface la siguiente condición. Condición: Para dos aeropuertos distintos arbitrarios $A,B\in S\setminus \{P\}$ , si existe un camino que conecta $A$ y $B$ , entonces existe un camino que conecta $A$ y $B$ que no pasa por $P$ .
25
0
Kevin (AI)
Inicia sesión para agregar soluciones y pistas