En cierto pais hay $n$ ciudades, algunas de las cuales estan conectadas
por aerolineas que van de ida y vuelta. Hay $m$ aerolineas diferentes en total.
Para $i=1, 2, \dots, n$, sea $d_i$ el numero de aerolineas que salen de la ciudad $i$. Si
$1 \leq d_i \leq 2010$ para cada $i=1, 2, \dots, 2010$, muestra que
$$\sum_{i=1}^n d_i^2 \leq 4022m - 2010n.$$
Encuentra todos los $n$ para los cuales la igualdad se alcanza.
martes, 17 de agosto de 2010
Suscribirse a:
Comentarios de la entrada (Atom)
9 comentarios:
Si consideramos la gráfica donde los vértices representan ciudades, cada arista sería una línea aérea?
Lo puedes ver asi, solo que si hay una arista de un vertice a otro entonces hay dos aristas pues los vuelos son de ida y vuelta
No entiendo bien el problema, segun yo aerolinea es como Volaris, puede ir de Toluca a Cancún o de Puebla a Tijuana y sigue siendo la misma aerolinea. Osea en graficas sería como que si tienes m aerolineas, significa que tienes aristas de m colores no???
Pero entonces si esta es la definición entonces el problema no es cierto, por que si te tomas n=2010 y m=1 y pones a las ciudades en un polígono regular de tal forma que los vértices adyacentes se comuniquen por la aerolinea, entonces obtienes que el lado derecho de la ecuación es negativo y el izquierdo positivo.
O te refieres a que el numero de aerolineas es igual al número de parejas de ciudades conectadas??
Mi duda es la misma que la de Georges, una aerolínea puede conectar muchas ciudades?
No entiendo bien la pregunta de Georges, mas tarde la contesto. Acerca de la pregunta de Irving, una misma aerolinea puede conectar muchas ciudades
Pues si una a aerolinea puede conectar varias ciudades entonces no es cierto el problema como dice Georges, basta tomar n=3 m=1 y d_i=1, y ya el lado derecho se hace negativo y el izquierdo siempre es positivo; supongo que entonces por aerolinea mas bien se refiere a vuelo, entonces mi solucion es:
Tenemos que la suma de los grados de los vertices de un grafo es dos veces el numero de aristas entonces
2m= Suma (d_i)
entonces P. D. es equivalente a
Suma (d_i ^2)-suma(d_i) $\le$ 2010 * (suma (d_i)-n)
equivalente a
Suma (d_i*(d_i-1))<= 2010 * (suma (d_i-1)) = suma (2010*(d_i-1))
pero cada d_i es menor o igual a 2010, entonces cada termino de la suma de la derecha es mayor o igual a su termino respectivo en la izquierda, entonces el lado derecho es efectivamente mas grande, con igualdad si y solo si d_i=2010 para toda i, pero para que d_i sea 2010, n-1 debe ser mayor o igual a 2010, entonces n debe ser mayor o igual a 2011, aunque se necesita tambien que d_i=2010 para toda i.
Según yo cada arista de la gráfica es una aerolínea para que funcione. Tenemos $2m=\sum_{i=1}^n d_{i}$. Como $d_{i}\le 2010$ entonces
\[\sum_{i=1}^n d_{i}(d_{i}-1)\le 2010 \sum_{i=1}^n (d_{i}-1)\]
\[\Leftrightarrow \sum_{i=1}^n d_{i}^2-\sum_{i=1}^n d_{i}\le 2010\sum_{i=1}^n d_{i}-2010n\]
\[\Leftrightarrow \sum_{i=1}^n d_{i}^2\le 2011\sum_{i=1}^n d_{i}-2010n\]
\[\Leftrightarrow \sum_{i=1}^n d_{i}^2\le 4022m-2010n\]
Y se tiene que la igualdad se da cuando $d_{i}=2010$ para toda $i$.
Bueno como ya dijimos no se puede que una aerolinea conecte muchas ciudades, entonces vamos a interpretar que el número de "aerolineas" es igual al número de parejas de ciudades que estan conectadas.
Y tampoco se puede que si solo $1 \leq d_i $ para $i= 1,2, \dots, 2010$ por que si no entonces podemos tomar un $n$ muy grande y entonces como las ciudades con número mayor a $2010$ no tienen que tener ningun camino, entonces el lado derecho va a ser negativo y el lado izquierdo positivo. Por lo tanto vamos a suponer que $1 \leq d_i \leq 2010$ para toda $i$
Entonces si nos fijamos en una gráfica con las ciudades como vértices y las aerolíneas como aristas, entonces sabemos que la suma de los grados de los vértices es dos veces las aristas. Por lo tanto la desigualdad original nos queda como demostrar $\sum_{i=1}^n d_i^2 \leq 2011 \sum_{i=1}^n d_{i} - 2010 n$ y eso es equivalente a demostrar $\sum_{i=1}^n (d_i)(d_i - 1) \leq 2010 \sum_{i=1}^n d_i - 2010n = \sum_{i=1}^n 2010(d_i - 1)$ y claramente esta desigualdad si es cierta por que para cada $i$ $d_i \leq 2010$ y la igualdad se da cuando $d_i = 2010$ para toda $i$
Publicar un comentario