Prueba de Selección de Equipos de Grecia 2025 Problema 4

4 En una conferencia internacional participan $n$ científicos $(n > 100)$ , donde se cumplen las siguientes condiciones: todo científico conoce al menos a otros 4 participantes, y todo conocimiento es mutuo. En ningún grupo de 4 científicos se conocen todos entre sí. Cualesquiera dos científicos que participan en la conferencia están conectados mediante una cadena de conocidos. El número mínimo de conocidos necesario para conectar a dos científicos mediante una cadena de participantes conocidos en la conferencia se llama la distancia entre los dos científicos. Si $d$ es la distancia máxima entre cualesquiera dos participantes de la conferencia, demuestre que $$d \leq \left\lceil \frac{4}{7}n \right\rceil + 3 .$$

0

0

Kevin

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados