Ahi les va uno, creo yo, pesado. Me dicen si ya lo vieron
Sea $c_n$ una secuencia definida asi $c_0 = c_1= 1$, $c_{2n+1} = c_n$, y $c_{2n} = c_n + c_{n-2^{v (n)}}$ para $n\geq 1$ Demuestra que
\[\sum_{i=0}^{2^n-1} c_i = \frac{1}{n+2} {2n+2 \choose n+1}.\]
Otro para que se entretengan, pero ahora de combi.
En cierto país, Unidireccionlandia, hay varias ciudades y entre algunas de ellas hay carreteras. Estas carreteras tienen capacidad de uno o dos. De cada ciudad salen carreteras cuya suma de flujo es impar. El ministro de transporte, para abaratar costos, decide hacer que todas las carreteras sean de una sola dirección. Prueba que se puede hacer de tal manera que en todas las ciudades, la diferencia entre la suma de las capacidades de flujo entrante y la suma de las capacidades de saliente sea uno.
Sea $c_n$ una secuencia definida asi $c_0 = c_1= 1$, $c_{2n+1} = c_n$, y $c_{2n} = c_n + c_{n-2^{v (n)}}$ para $n\geq 1$ Demuestra que
\[\sum_{i=0}^{2^n-1} c_i = \frac{1}{n+2} {2n+2 \choose n+1}.\]
Otro para que se entretengan, pero ahora de combi.
En cierto país, Unidireccionlandia, hay varias ciudades y entre algunas de ellas hay carreteras. Estas carreteras tienen capacidad de uno o dos. De cada ciudad salen carreteras cuya suma de flujo es impar. El ministro de transporte, para abaratar costos, decide hacer que todas las carreteras sean de una sola dirección. Prueba que se puede hacer de tal manera que en todas las ciudades, la diferencia entre la suma de las capacidades de flujo entrante y la suma de las capacidades de saliente sea uno.
9 comentarios:
¿Qué significa capacidad?
¿Qué significa "suma de flujo"?
¿Qué es la "capacidad de flujo entrante" y "capacidad de flujo saliente"?
¿Puede haber una carretera de una ciudad a esa misma ciudad?
¿Puede haber dos carreteras entre el mismo par de ciudad?
También, en la definición de $c_{2n}$, es $c_n + c_{n-2^{v_2(n)}}$. Es decir, ¿la diferencia entre $n$ y la máxima potencia de 2 que divide a $n$?
¿O qué significa $v(n)$?
Suma de flujo es suma de las capacidades. El resto de las peguntas merece un "Lease más detenidamente el problema".
Y sí, eso es v_2(n)
¿Es diferencia en valor absoluto? ¿O se debe cumplir$S(entrante)=S(saliente)+1$ ¿O al revés?
Tendría algún sentido que no fuera valor absoluto?
(Sí, es valor absoluto)
Para el segundo, primero considera la gráfica que resulta de quitarle las aristas de capacidad 2 a la original. Hay un número par de vértices y cada vértice tiene grado non. Ahora, Demuestra que se puede direccionar. Luego, agrega una arista de capacidad 2. Direcciónala de alguna manera, y si eso causa que algún vértice se vuelva "malo", re-direcciona una arista de ese vértice. Repite el proceso y demustra que acabará en algún momento. Luego, agrega otra arista de capacidad 2, y otra, y así, hasta tener la gráfica original direccionada correctamente.
Es solamente un intento, aún no veo si funciona.
Como es un hint, lo escribiré en un pastebin y para el que quiera meterse pues que lo vea.
http://pastebin.com/LMLqz5rN
Publicar un comentario