Sorteo de la Liga de Campeones

El sorteo de octavos de final de la Liga de Campeones de la UEFA funciona de la siguiente manera. Acceden los 16 equipos clasificados de la primera ronda, de entre los cuales 8 acceden como primeros de grupo, y se enfrentan a los 8 equipos que acceden como segundos de grupo. Además hay ciertos condicionantes que impiden que dos equipos se enfrenten entre ellos:

  • Dos equipos no se enfrentarán si ya se enfrentaron en la primera fase.
  • Dos equipos del mismo país no se pueden enfrentar entre ellos.
  • Dos equipos no se pueden enfrentar si la UEFA considera que existen problemas políticos entre sus respectivos países.

Desde un punto de vista matemático, el problema se puede expresa como encontrar un emparejamiento en un grafo bipartito. El problema de encontrar dicho emparejamiento es un problema ampliamente estudiado, y para el que se conocen soluciones algorítmicas eficientes.

Ahora, la pregunta que se hacen todos los medios de comunicación es, ¿cuál es la probabilidad de que a mi equipo le toque este otro equipo tan bueno, o este otro tan asequible a priori? El primer razonamiento que se nos pasa por la cabeza es el siguiente: si a mi equipo le pueden tocar 5 rivales, entonces la probabilidad de que le toque cada uno de ellos es la misma: 20%.

Sin embargo, un análisis rápido nos lleva a la conclusión de que dicho razonamiento tiene que ser erróneo. Si fuera cierto surgiría una contradicción: mi equipo, el Balompié FC, tiene 5 posibles rivales, y uno de ellos es el AD Futbolistas, que por determinadas circunstancias sólo tiene 4 posibles rivales. Entonces, ¿cuál es la probabilidad de que en octavos nos enfrentemos el Balompié FC contra el AD Futbolistas? Pues desde nuestro punto de vista es un 20%, pero desde el suyo es un 25%, lo cual es una contradicción.

La manera justa de hacer el sorteo y calcular las probabilidades es la siguiente: Hay un número determinado de sorteos posibles, en los que todos los condicionantes se cumplen. De los 40.320 posibles emparejamientos entre primeros y segundos, 9.147 de ellos son correctos. Cada uno de esos sorteos correctos debería tener la misma probabilidad de salir, y por tanto la probabilidad de que se enfrentaran el Real Madrid y el PSV Eindhoven debería ser el número de sorteos correctos en los que salen emparejados (1.175), dividido entre el número total de sorteos, es decir, un 12.85%. Ten en cuenta que el Real Madrid tiene 7 posibles rivales, y dado que 100/7=14.29%, eso quiere decir que hay rivales que son más probables para el Real Madrid que el PSV Eindhoven. Si el sorteo fuera justo, las probabilidades de que dos equipos se enfrentaran entre sí vendrían dadas por el cuadro que se muestra a continuación:

 50051 64332 50124 52919 50080 50037 52914 52826
52747 0% 12.85% 12.85% 15.95% 12.85% 13.73% 16.53% 15.25%
50062 12.85% 0% 12.85% 15.95% 12.85% 13.73% 16.53% 15.25%
50147 12.85% 12.85% 0% 15.95% 12.85% 13.73% 16.53% 15.25%
50139 13.27% 13.27% 13.27% 0% 13.27% 14.09% 16.99% 15.83%
50137 12.85% 12.85% 12.85% 15.95% 0% 13.73% 16.53% 15.25%
52280 19.21% 19.21% 19.21% 0% 19.21% 0% 0% 23.17%
52723 15.83% 15.83% 15.83% 19.79% 15.83% 16.89% 0% 0%
4608 13.15% 13.15% 13.15% 16.41% 13.15% 14.09% 16.89% 0%

Calcular dichas probabilidades es sencillo: basta con hacer un programa que simule los 40.320 emparejamientos, a continuación que decida cuáles de ellos son correctos, y por cada pareja de equipos que calcule también en cuántos sorteos correctos se enfrentan. Desde un punto de vista algorítmico, se dice que la complejidad del algoritmo es de O(n·n!), donde n es el número de equipos en cada bombo. Para n=8, esto tarda unas 3 centésimas en ejecutarse en un ordenador moderno.

Sin embargo, este método tiene un problema que no está relacionado con las matemáticas ni con la justicia: el sorteo tiene mucha audiencia y da dinero. Eso significa que no sólo tiene que ser justo, sino atractivo para el espectador. Para realizar un sorteo como el que he descrito sólo se me ocurren dos formas:

  • Introducir en un bombo gigante 9.147 bolas, cada una de ellas con un sorteo correcto, y elegir una de ellas al azar, que indicaría el emparejamiento completo.
  • Hacer el sorteo sin condicionantes, y si se produce una situación no permitida (como que dos equipos del mismo país se enfrenten) se para todo el sorteo y se vuelve a empezar. El número medio de veces que habría que realizarlo es de entre 4 y 5.

Es evidente que ninguno de los dos sorteos son atractivos para el espectador. El primero de ellos tendría el inconveniente adicional de que sería difícil de auditar, ya que habría que comprobar que cada sorteo aparece una única vez, y que aparecen todos. Descartado pues este sistema, la UEFA opta por un método que da un resultado parecido, y que es mucho más atractivo para el espectador. El sorteo consiste en lo siguiente:

  • Hay un bombo en el que están situados todos los segundos de grupo. También hay un bombo por cada primero de grupo con varias bolas. Todas las bolas cada bombo de primeros de grupo contienen el mismo nombre.
  • Sucesivamente, se elige una bola del bombo de los segundos. A continuación, un programa de ordenador decide con qué primeros se le pueden emparejar, de forma que sea posible completar el sorteo de forma correcta. Es decir, aunque un primero pueda enfrentarse a un segundo, si el ordenador decide que, de emparejarse, no se podría acabar el sorteo porque los equipos restantes son incompatibles, entonces dicho primero queda descartado.
  • A continuación se mezclan en otro bombo todos los primeros que el programa de ordenador ha decidido como válidos, y se selecciona al azar uno de ellos, que queda emparejado con el segundo que se eligió anteriormente.

A priori no parece que haya ningún motivo por el que las probabilidades de dicho método sean las mismas que la del método denominado justo. La pregunta que nos hacemos es, entonces, ¿cuál es la diferencia entre un método y otro? Para calcularlo es necesario programar un algoritmo más complejo, que tenga en cuenta no sólo el resultado final del sorteo, sino también todos los escenarios en el que dicho resultado puede darse. Además es necesario hacer la comprobación de si emparejando dos equipos no se produce una situación en la que no se puede acabar el sorteo de forma correcta. Dicha comprobación la he hecho mediante un algoritmo que resuelve un problema conocido, denominado emparejamiento máximo. Esto aumenta la complejidad, por lo que desde un punto de vista informático diríamos que la complejidad es de O((n·n!)²), lo que significa que en tiempo de ejecución pasamos de 3 centésimas a cerca de media hora. La tabla resultante es la siguiente:

 50051 64332 50124 52919 50080 50037 52914 52826
52747 0% 12.86% 12.86% 15.96% 12.86% 13.66% 16.46% 15.33%
50062 12.86% 0% 12.86% 15.96% 12.86% 13.66% 16.46% 15.33%
50147 12.86% 12.86% 0% 15.96% 12.86% 13.66% 16.46% 15.33%
50139 13.21% 13.21% 13.21% 0% 13.21% 14.29% 17.14% 15.74%
50137 12.86% 12.86% 12.86% 15.96% 0% 13.66% 16.46% 15.33%
52280 19.27% 19.27% 19.27% 0% 19.27% 0% 0% 22.92%
52723 15.78% 15.78% 15.78% 19.81% 15.78% 17.08% 0% 0%
4608 13.16% 13.16% 13.16% 16.34% 13.16% 13.98% 17.02% 0%

Dicha tabla, que se puede encontrar en otras fuentes, muestra que en realidad la diferencia con el sorteo justo es muy baja, y en la mayoría de casos, si ponemos poca precisión en los porcentajes ni siquiera se notaría la diferencia. Sin embargo, una de las consecuencias de que el sorteo se realice finalmente así es que no todos los emparejamientos son igual de probables. He hecho un programa que calcula cuáles son los sorteos más probables y menos probables. Como hay 9.147 emparejamientos posibles, la probabilidad media será de 1/9.147. El resultado es que tampoco varía demasiado. El emparejamiento menos probable tiene una probabilidad de 1/10.888 aproximadamente. Dicho emparejamiento es:

PSG – Barcelona
PSV – Atlético
Benfica – Wolfsburgo
Juventus – Chelsea
Roma – Real Madrid
Arsenal – Zenit
Dinamo – Manchester
Gent – Bayern

Por otro lado, el emparejamiento más probable tiene una probabilidad de 1/8.570 aproximadamente, y es:

PSG – Barcelona
PSV – Zenit
Benfica – Wolfsburgo
Juventus – Bayern
Roma – Atlético
Arsenal – Real Madrid
Dinamo – Manchester
Gent – Chelsea