En un país hay $64$ ciudades, algunos pares de ciudades están conectadas mediante caminos, pero no se sabe cuáles son estos pares. La operación permitida es elegir un par de ciudades y preguntar si están conectadas o no (la respuesta siempre será verdadera). El objetivo es averiguar si es posible viajar de cualquier ciudad a cualquier otra mediante una secuencia de caminos.
Demostrar que es imposible cumplir el objetivo con menos de $2016$ operaciones permitidas.
Primero veamos que podemos plantear el problema como un grafo, donde los nodos son las ciudades, las aristas son los caminos y el objetivo es ver si el grafo es conexo. Luego veamos que la cantidad de "posibles aristas" es $\binom{64}{2} = 2016$. Por lo tanto, intentaremos demostrar que es necesario preguntar por todas las posibles aristas para saber si es conexo o no.
Supongamos que ya hicimos $2015$ operaciones, que con esa información tenemos $2$ componentes y que la arista que nos queda por preguntar tiene un nodo en cada componente, con esto, no sabremos si la arista que nos queda por preguntar unirá las $2$ componentes o no, por lo que no sabremos si será conexo con $2015$ operaciones. Por lo tanto no podremos cumplir nuestro objetivo con menos de $2016$ operaciones ■
P.D: Probablemente nadie vea esto ya que es el problema del día, si lo viste dale like
Última edición por Edu Carranza el Dom 01 Oct, 2023 12:18 am, editado 1 vez en total.
Primero veamos que podemos plantear el problema como un grafo, donde los nodos son las ciudades, las aristas son los caminos y el objetivo es ver si el grafo es conexo. Luego veamos que la cantidad de "posibles aristas" es $\binom{64}{2} = 2016$. Por lo tanto, intentaremos demostrar que es necesario preguntar por todas las posibles aristas para saber si es conexo o no.
Supongamos que ya hicimos $2015$ operaciones, que con esa información tenemos $2$ componentes y que la arista que nos queda por preguntar tiene un nodo en cada componente, con esto, no sabremos si la arista que nos queda por preguntar unirá las $2$ componentes o no, por lo que no sabremos si será conexo con $2015$ operaciones. Por lo tanto no podremos cumplir nuestro objetivo con menos de $2016$ operaciones ■
P.D: Probablemente nadie vea esto ya que es el problema del día, si lo viste dale like
Primero veamos que podemos plantear el problema como un grafo, donde los nodos son las ciudades, las aristas son los caminos y el objetivo es ver si el grafo es conexo. Luego veamos que la cantidad de "posibles aristas" es $\binom{64}{2} = 2016$. Por lo tanto, intentaremos demostrar que es necesario preguntar por todas las posibles aristas para saber si es conexo o no.
Supongamos que ya hicimos $2015$ operaciones, que con esa información tenemos $2$ componentes y que la arista que nos queda por preguntar tiene un nodo en cada componente, con esto, no sabremos si la arista que nos queda por preguntar unirá las $2$ componentes o no, por lo que no sabremos si será conexo con $2015$ operaciones. Por lo tanto no podremos cumplir nuestro objetivo con menos de $2016$ operaciones ■
P.D: Probablemente nadie vea esto ya que es el problema del día, si lo viste dale like
No estaría entendiendo por qué con $2015$ operaciones nos quedan al menos dos componentes conexas. Por ejemplo, si el grafo es completo puede pasar que yo pregunte por la arista $\{1,2\}$, después por la $\{2,3\}$, después por la $\{3,4\}$, y así hasta la $\{63,64\}$ y gano en $63$ pasos porque encontré un camino que pasa por todos los vértices del grafo.
Primero veamos que podemos plantear el problema como un grafo, donde los nodos son las ciudades, las aristas son los caminos y el objetivo es ver si el grafo es conexo. Luego veamos que la cantidad de "posibles aristas" es $\binom{64}{2} = 2016$. Por lo tanto, intentaremos demostrar que es necesario preguntar por todas las posibles aristas para saber si es conexo o no.
Supongamos que ya hicimos $2015$ operaciones, que con esa información tenemos $2$ componentes y que la arista que nos queda por preguntar tiene un nodo en cada componente, con esto, no sabremos si la arista que nos queda por preguntar unirá las $2$ componentes o no, por lo que no sabremos si será conexo con $2015$ operaciones. Por lo tanto no podremos cumplir nuestro objetivo con menos de $2016$ operaciones ■
P.D: Probablemente nadie vea esto ya que es el problema del día, si lo viste dale like
No estaría entendiendo por qué con $2015$ operaciones nos quedan al menos dos componentes conexas. Por ejemplo, si el grafo es completo puede pasar que yo pregunte por la arista $\{1,2\}$, después por la $\{2,3\}$, después por la $\{3,4\}$, y así hasta la $\{63,64\}$ y gano en $63$ pasos porque encontré un camino que pasa por todos los vértices del grafo.
Me faltó aclarar que si todavía no cumplimos nuestro objetivo con $2015$ preguntas si o si tendremos dos componentes conexas:
Debemos notar que si es imposible cumplir nuestro objetivo con menos de $2016$ preguntas, entonces siempre existirá un grafo que se puede ir modificando sin contradecir la información que tenemos para que sea imposible cumplir nuestro objetivo, por lo que se podrá cumplir la condición que asumí. Más en detalle:
Para que sea imposible saber si es conexo, no debemos descubrir que es disconexo antes de las $2016$ preguntas ya que sino cumpliríamos nuestro objetivo con menos de $2016$ preguntas y queremos demostrar lo contrario. Por lo tanto siempre va a existir una arista que una dos componentes antes de las $2016$ preguntas.
Cada vez que unimos dos componentes $c$ y $d$, sea $n$ el tamaño $c$ y $m$ el tamaño $d$, el máximo "costo" (cantidad de preguntas) para unirlas es la cantidad de posibles aristas que tienen un nodo en $c$ y otro en $d$: $n × m$, ya que nos podrían decir que ninguna existe hasta que preguntemos por la última.
Ahora, intentemos demostrar por inducción que el costo para tener una componente de tamaño $n$ es $\binom{n}{2}$. Vemos como caso base que para $n = 1$ se cumple ya que $\binom{1}{2} = 0$. Ahora si unimos dos componentes de tamaño $n$ y $m$ tenemos que demostrar que la propiedad se sigue cumpliendo, es decir que el costo de la componente final es igual a el costo de $n$ $+$ el costo de $m$ $+$ el costo de unirlas: $\binom{n+m}{2} = \binom{n}{2} + \binom{m}{2} + n × m$. Haciendo las cuentas nos queda que $\binom{n+m}{2} = \frac{(n+m)×(n+m-1)}{2} = \frac{n²-n+m²-m+2nm}{2} = \frac{n(n-1)+m(m-1)+2nm}{2} = \frac{n(n-1)}{2}+\frac{m(m-1)}{2}+nm = \binom{n}{2} + \binom{m}{2} + n × m$. Otra forma de verlo es que si tenés una componente es porque ya preguntaste por todas sus posibles aristas, y cuando unís dos componentes $c$ y $d$ ya preguntaste por todas las posibles aristas de $c$ y de $d$ y ahora estás preguntando por todas las posibles aristas que tienen un nodo en cada componente, por lo que habremos preguntado por todas las posibles aristas en la componente resultante. Por lo que si tenemos una componente de tamaño $64$ es porque preguntamos por todas las $\binom{64}{2} = 2016$ posibles aristas, pero si ya hicimos $2015$ preguntas es porque estamos uniendo dos componentes, que por el momento no encontramos una arista que las conecte (ya que sino hubiéramos cumplido nuestro objetivo), y nos queda preguntar por la última arista que tiene un nodo en cada componente.
Voy a probarlo por contraejemplo. Imaginemos que las 64 ciudades estan conectadas en una linea. Es decir, la primera con la segunda, la segunda con la tercera, asi hasta la 63 con la 64. Hay 63 caminos en total.
Voy a probar que en este caso se necesitan 2016 movimientos para saber con seguridad que se puede viajar de cualquier ciudad a cualqiuer otra.
La informacion que necesitamos para conocer esto es exactamente conocer la existencia de los 63 caminos. Si solo supiesemos de 62 caminos, entonces habria dos subconjuntos de ciudades que no sabriamos si estan conectados. o no. Si sabemos que dos ciudades no estan conectadas, entonces esa informacion obviamente no nos sirve porque la respuesta correcta es que estan todas conectadas.
Para cada una de las ciudades, hay 63 caminos posibles a otra ciudad. Hay 64 ciudades. Entonces hay $\frac{64 \cdot 63}{2} = 2016$ caminos posibles. (divido por 2 porque cada camino conecta dos ciudades, entonces si no estaria contando cada camino dos veces).
No sabemos nada de la distribucion de los caminos. Podrian existir 2016 caminos, o podria no existir ninguno, y podrian salir 2016 caminos de una sola ciudad. Entonces, una vez que hacemos un movimiento, no conseguimos nada de informacion que nos sirva para decidir que movimientos vamos a hacer despues. Hasta donde sabemos, los caminos podrian estar distribuidos de cualquier manera. Lo unico que podriamos averiguar en un movimiento es que las 64 ciudades o estan conectadas o no estan conectadas, en este caso averiguariamos que no tenemos que hacer mas movimientos.
Imaginemos que vamos haciendo movimientos. Obviamente, la mejor estrategia va a implicar nunca hacer el mismo movimiento dos veces. El primer movimiento va a ser al azar. Imaginemos que tuvimos mala suerte, y que las dos ciudades que elegimos no estaban conectadas. El segundo tambien es al azar porque ya probamos que el primero no nos brindo nada de informacion util para decidir los movimientos. Imaginemos que tampoco estan conectadas las ciudades. Imaginemos que tenemos mala suerte hasta el movimiento 2016 - 63 + 1, en el cual si o si tiene que salir que hay dos ciudades conectadas porque hay 63 caminos. En los otros 62 movimientos tambien pasa esto. Al final hicimos 2016 movimientos usando la estrategia optima con la informacion que teniamos, y averiguamos que las ciudades estan conectadas en una linea, pero con menos de 2016 no sabiamos si estaban conectadas o no.
Entonces con menos de 2016 movimientos existen configuraciones de caminos con las que no se puede saber con seguridad.
