viernes, 24 de mayo de 2013

24 de Mayo Diego Roque

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.

9 comentarios:

Juan dijo...

¿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?

Juan dijo...

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$?

Juan dijo...

¿O qué significa $v(n)$?

Diego Alonso Roque Montoya dijo...

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)

Juan dijo...

¿Es diferencia en valor absoluto? ¿O se debe cumplir$S(entrante)=S(saliente)+1$ ¿O al revés?

Diego Alonso Roque Montoya dijo...

Tendría algún sentido que no fuera valor absoluto?
(Sí, es valor absoluto)

Juan dijo...

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.

Juan dijo...

Es solamente un intento, aún no veo si funciona.

Diego Alonso Roque Montoya dijo...

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