Olimpiada Corea - Ronda Final 2003 Problema 1

Algunas computadoras de una sala de computadoras tienen la siguiente red. Cada computadora está conectada por tres cables a tres computadoras. Dos computadoras arbitrarias pueden intercambiar datos directa o indirectamente (a través de otras computadoras). Ahora, eliminemos $K$ computadoras para que haya dos computadoras que no puedan intercambiar datos, o quede una computadora. Sea $k$ el valor mínimo de $K$. Eliminemos $L$ cables de la red original para que haya dos computadoras que no puedan intercambiar datos. Sea $l$ el valor mínimo de $L$. Demuestra que $k=l$.

26

0

Kevin (AI)

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados