Hay $2^n$ jugadores en un torneo de ajedrez por eliminación. Todos tienen la misma habilidad. Esto significa que para dos emparejamientos cualesquiera la probabilidad de que uno de ellos gane es $\frac{1}{2}$ .
La mesa se asigna uniformemente al azar. Tú y tu amigo estáis compitiendo. ¿Cuál es la probabilidad de que os encontréis?
Método uno
Dibujar una tabla de eliminación en el sentido de un árbol binario rooteado. Sin pérdida de generalidad ponte en la hoja inferior izquierda. Podemos condicionar la probabilidad de que tú y tu amigo os encontréis a la ubicación inicial del amigo.
Observe que tenemos $2^n-1 $ posiciones en las que podrían estar. Una de las posiciones es adyacente a la suya, en cuyo caso la probabilidad de que se encuentren es $1$ . Dos de estas posiciones están a sólo un juego de distancia en cuyo caso ambos deben ganar sus juegos para cumplir, con probabilidad $\frac{1}{4}$ . Cuatro de estas posiciones están a dos juegos de distancia en cuyo caso se encuentran si ambos ganan dos juegos. $\frac{1}{2^4}$ . Y así sucesivamente.
Formalmente: Probabilidad de encuentro = $\sum\limits_{i = 0}^n \frac{2^i}{2^n-1} \cdot (\frac{1}{2^i})^2$ = $\frac{1}{2^n-1}\sum\limits_{i = 0}^n \frac{1}{2^i} = \frac{1}{{2^n}-1} \cdot \frac{\frac{1}{2^{n+1}} -1}{1-\frac{1}{2}} = \frac{1}{2^{n-1}}$
Este método es la tuerca y el tornillo. Un poco de juego con las series geométricas, pero bastante intuitivo.
Método dos
Este método parece mucho más bonito. I pensamiento era legítimo y obtiene la misma respuesta, pero encontré un gran agujero en él explicado al final.
Que las posiciones de los concursantes sean $C_1 , C_2, C_3 , ... , C_{2^n} $ . Sea $M_{i,j}$ denotan el caso de que el concursante $i$ se encuentra con el concursante $j$ Por simetría total la probabilidad de $M_{i,j}$ es el mismo para todos los $i \not= j \in [1,2^n] $ .
Tenemos un total de $2^n - 1$ juegos en el torneo ya que cada juego elimina a un solo jugador.
Tenemos un total de $2^n$ elija $2$ = $\frac{2^n \cdot (2^n - 1)}{2} = 2^{2n-1} -2^{n-1}$ acoplamientos de $M_{i,j}$ .
( $\star$ ) Los partidos jugados son como escoger $2^n -1$ bolas de una bolsa con $2^{2n-1} -2^{n-1}$ bolas en él. Así que la probabilidad de que tú y tu amigo os encontréis es $\frac{2^n -1}{2^{2n-1} -2^{n-1}} = \frac{1}{2^{n-1}}$ .
Qué bien, tenemos la misma respuesta que antes pero mucho más limpia. ¡Sin embargo este método es erróneo!
Paso $(\star)$ es una violación. No podemos, por ejemplo, recoger las bolas $M_{1,2} , M_{1,3} , M_{1,4} , ..., M_{1,2^n}$ como concursante $1$ ¡no puede jugar todo el mundo!
¿Puede alguien ayudarme a hacer funcionar el segundo método? Estoy seguro de que no está muy lejos. ¿O es sólo una coincidencia que funcione?
