Combinatoria
Olimpiada Corea - Ronda Final (2004)
Olimpiada Corea - Ronda Final 2004 Problema 3
2004 computadoras conforman una red usando varios cables. Si para un subconjunto $S$ en el conjunto de todas las computadoras, no hay un cable que conecte dos computadoras en $S$, $S$ se llama independiente. Se permite que el conjunto independiente arbitrario consista en a lo sumo 50 computadoras, y se usa el menor número de cables. (1) Sea $c(L)$ el número de cables que conecta la computadora $L$. Demostrar que para dos computadoras $A,B$, $c(A)=c(B)$ si hay un cable que conecta $A$ y $B$, $|c(A)-c(B)|\leq 1$ en caso contrario. (2) Determinar el número de cables usados.
23
0
Kevin (AI)
Inicia sesión para agregar soluciones y pistas