sábado, 19 de mayo de 2012

Como se arma el fixture del futbol argentino.Adrian Paenza



Lo que sigue es la historia de cómo un matemático argentino resolvió un problema ligado con el fútbol y la televisión. No sé si habrá prestado atención alguna vez a un fixture de fútbol, la programación de todos los partidos que se juegan en el año. Un fixture estándar consiste en 19 fechas en las que los 20 equipos jueguen todos contra todos. Además, se supone que semana tras semana alternan su condición de local y visitante. Confeccionarlo no debería ser una tarea difícil. Sin embargo, lo invito a que lo intente para comprobar el grado de dificultad que presenta.

Este problema está resuelto (matemáticamente) hace ya mucho tiempo (con la salvedad de que los equipos tengan que repetir una única vez su condición de local o visitante ). Desde que se juega fútbol en la Argentina siempre se han podido hacer los ajustes necesarios para que, por ejemplo, Racing e Independiente no jueguen de local en la misma fecha, y lo mismo los dos equipos de Rosario, La Plata o Santa Fe.

Pero la televisión cambió todo. Cuando los partidos se jugaban todos el día domingo (sí, aunque parezca mentira, antes todos los partidos se jugaban los domingos a la misma hora, pero eso correspondía a otra generación de argentinos), todo era relativamente sencillo. Después, la televisación de partidos obligó a ciertas restricciones: había que seleccionar un partido para televisar los viernes, y tenía que ser un partido que enfrentara a un equipo de los denominados “grandes” (River, Boca, Racing, Independiente y San Lorenzo), que se jugara en la capital, con uno de los denominados “chicos” (éstos van variando de acuerdo con el campeonato, pero creo que se entiende la idea).

Después se agregó un partido para televisar los sábados, con la condición de que tenía que ser una transmisión originada en el interior del país (Córdoba, Rosario, La Plata, Santa Fe, Mendoza, Tucumán, etcétera) y debía involucrar a un equipo de los “grandes” (grupo al que se permitía añadir a Vélez). Luego se sumó un partido para televisar los lunes entre dos clubes “chicos”.

Y para complicar más las cosas, aparecieron los codificados.

Y después, “El clásico del domingo”. Además, había que dejar algún partido atractivo para que se pudiera ver por primera vez en el programa Fútbol de primera el domingo a la noche.

Si uno intenta hacerlo a mano (y créame que hubo mucha gente que se lo propuso) son tantos los ajustes que hay que hacerle a un fixture para que cumpla con todas esas restricciones, que ya se dudaba de que un fixture así existiera, o que fuera posible armarlo. ¿Qué hacer? En ese momento, enero de 1995 (hace ya casi doce años), la gente de la empresa Torneos y Competencias (dedicada a la difusión de deportes en radio, televisión y medios gráficos) me derivó el problema para ver si algún matemático (como yo sostenía) era capaz de presentar un programa de partidos a la AFA (Asociación del Fútbol Argentino) que contemplara todas las restricciones señaladas. Me reuní con Carlos Ávila, el creador de la empresa, quien es un gran intuitivo, y finalmente entendió que lo mejor que podíamos hacer era consultar con alguien que supiera. Bien, pero, ¿quién sabría?, Mirá, le dije, en la Facultad de Ciencias Exactas de la UBA hay matemáticos a quienes les podría plantear el problema.

Son ellos los candidatos naturales para resolverlo.

-Dale para adelante, me dijo.

Y le di. En realidad, le di el problema al doctor Eduardo Dubuc, profesor titular del departamento de Matemáticas desde hace años, y uno de los más prestigiosos que tiene el país. Su vida circuló por distintas ciudades de los Estados Unidos, Francia y Canadá, y hace ya algunos años reside en la Argentina.

Me formuló las preguntas lógicas para alguien que sigue el fútbol sólo como aficionado. Cerró la carpeta que contenía los datos, se sacó los anteojos que usa siempre, mi miró en silencio durante un rato y me preguntó:

-Vos estás seguro de que este problema tiene solución?, No sé, pero seguro que si la tiene, vos sos la persona para encontrarla.

Unos días más tarde, me entregó un fixture junto con algunos comentarios escritos. Recuerdo uno en particular: “El problema está resuelto de la mejor manera posible”.

Yo estaba entusiasmado, pero le dije:

-Eduardo, ¿qué significa “la mejor manera posible”? Necesitamos que sea la mejor y no la mejor posible .

-Como ya vimos el día que me trajiste el problema, es imposible que en todas las fechas haya un partido entre dos clubes chicos , ya que hay sólo seis (en ese momento eran Deportivo Español, Argentinos Juniors, Ferro, Platense, Lanús y Banfield).

En todo el campeonato, jugarán entre ellos 15 partidos. Aun, que logremos hacerlos jugar a todos en fechas diferentes, igualmente habrá cuatro semanas en las que va a faltar un partido para los días lunes.

Una obviedad. Sin embargo eso ponía en peligro todo. Si ya había una dificultad irresoluble, ¿qué quedaría para el resto? ¿Es que no habría manera de poder ordenar todo el caos que había siempre con el programa de los partidos? Sonaba a fracaso. Sin embargo, Eduardo me insistió.

-Fíjate bien en el fixture que te entrego y lee mis apuntes.

Y los leí. Digo, leí sus apuntes. Aquí van.

Tomá un fixture estándar (¿no debería decir standard ?) cualquiera.

Si intercambio dos equipos (por ejemplo, Boca juega en lugar de Ferro, y Ferro en lugar de Boca), se obtiene otro fixture (que sigue siendo estándar). Así se obtienen distintosfixtures y puede verse que hay en total 2.432.902.008.176.640.000 fixtures estandares.

Es posible que, en algunos casos, el intercambio de dos equipos permita generar un nuevo fixture equivalente al que le dio origen. Es decir, si el original cumplía con ciertas restricciones, el nuevo también lo hará. Y si el primero no cumplía algunas, el derivado tampoco lo hará. Por ejemplo, los equipos “grandes” que formaban una pareja (porque no podían jugar de local el mismo día, como era el caso de River y Boca, o Newell's y Central) podían intercambiarse entre sí y el resultado no variaría.

Lo mismo valía para los equipos “chicos”, o los que formaban “pareja” en el interior (como Colón y Unión o, en ese momento, Talleres e Instituto en Córdoba).

Una vez hechas estas observaciones, el número total de fixtures diferentes es de
1.055.947.052.160.000

que son casi 1.056 billones de fixtures . ¡Una barbaridad! Surgía inmediatamente una pregunta: ¿quién los revisaría para saber cuál o cuáles eran los que servían? Y un tema clave, muy importante: ¿cuánto tiempo tardaría en examinarlos todos? A razón de investigar 5.000 fixtures por segundo (sí, dice 5.000 fixtures por segundo, que es lo que se podía hacer en ese momento con un programa adecuado en las computadoras PC más veloces), llevaría casi 10.000 años hacerlo.

Había que intentar otra cosa. Probar a mano uno por uno no resultaría. Y Dubuc ya lo sabía. Pero se le ocurrió una idea que serviría para dar un salto cualitativo muy importante y, eventualmente, llegar a la solución.

Hay un método matemático que se conoce con el nombre de “recocido simulado”, y Dubuc decidió probar con él. Para ello, primero hay que empezar por calificar los fixtures . ¿Qué quiere decir esto? Elijan un fixture estándar cualquiera. Lo más probable es que no cumpla la mayoría de los requisitos que se necesitan.

Entonces, a Eduardo se le ocurrió que le iba a poner una multa por cada restricción que no cumpliera. Por ejemplo, si en el fixture que había elegido, en la primera fecha no había partido para los viernes, le ponía tres puntos de multa. Si le faltaba partido desde el interior, dos puntos de penalidad. Y así siguió hasta agotar la primera fecha. Pasó entonces a la segunda, y esencialmente las recorrió todas acumulando las multas que sufrían en el camino. Al finalizar el proceso, ese fixture tenía adosada una cantidad de puntos en contra, es decir, una multa. En definitiva, cuanto mayor fuera la multa de un fixture , peor era. Como se advierte, el objetivo de Eduardo era encontrar el o los fixtures que tuvieran multacero . Es decir, aquellos programas de partidos que no infringieran ninguna de las normas pedidas.

¿Existirían? ¿Tendría solución el problema? El proceso de revisar todas las alternativas estaba (y está) fuera de las posibilidades, ya que involucraría más de diez mil años, sin embargo, la diferencia ahora era que el problema estaba cuantificado . Es decir, se contaba con una función multa , y eso es lo que posibilita un tratamiento matemático para minimizar esa función.

Aquí es donde interviene el recocido simulado. Una aclaración muy importante: seguro que quienes concibieron, usan o usaron el recocido simulado no tuvieron in mente resolver un problema de estas características. Pero ahí también reside la capacidad de un matemático para saber que hay una herramienta que, en principio, no parece haber sido construida para esta ocasión en particular y, sin embargo, con una adaptación no sólo se transformó enútil, sino que permitió encontrar la solución.

A grandes rasgos, el sistema funciona así. Imagine que todos los fixtures posibles (los más de 1.000 billones) están escritos, cada uno en una hoja de papel, y metidos dentro de una pieza.

Uno entra a la pieza repleta de fixtures con un pinche en la mano, como si se tratara de recoger las hojas en una plaza. Más aún: en cada hoja que hay dentro de la pieza, no sólo hay un fixture escrito, sino que además está agregada la multa que le corresponde , que, como vimos, depende del grado de incumplimiento de las restricciones pedidas.

Entonces, uno procede así. Ni bien entra, pincha un fixture cualquiera y se fija en la multa que tiene asignada. Por supuesto, si uno tuviera la suerte de que ni bien empieza encuentra un fixture con multa cero, detiene el proceso inmediatamente, sale rápido de la pieza y se va a comprar un billete de lotería, a jugar al casino y apostar todo lo que tenga.

Cuando uno pincha el fixture y se fija en la multa que tiene asignada, decide caminar en alguna dirección. Cualquier dirección.

Pincha alguno de los vecinos ( fixtures ), y si la multa aumentó, entonces, no avanza en esa dirección. Si en cambio, al pinchar un vecino, la multa disminuye, entonces se encamina por ese lugar, seleccionando los que va encontrando en ese trayecto en la medida que siempre vaya disminuyendo la multa.

Si en algún momento llega a un lugar donde, independientemente del camino que elija, la multa aumenta siempre, entonces habrá llegado a un mínimo local , o a una especie de cráter.

Imagínese caminando por un camino montañoso, en el que la multa indicara la altura a la que se encuentra. De pronto, llegará a un lugar donde no importa para qué lado elija avanzar, para todas partes se sube, pero se está todavía lejos del nivel del mar. ¿Qué hacer? Hay que permitirse trepar para luego poder llegar más abajo por otro camino. Ésa es clave en el proceso.


El método del recocido simulado indica los movimientos que hacen subir (es decir, cambian el fixture por otro con una multa mayor) para salir de los mínimos locales, los cráteres, y eventualmente volver a descender, esta vez más abajo. Termina conduciendo a un lugar al nivel del mar, es decir, con multa cero.

No es posible que incluya aquí las precisiones sobre el método del recocido simulado en sí mismo, pero, en todo caso, vale la pena decir que involucra movimientos al azar, la teoría de probabilidades y se inspira en un análisis probabilístico de lo que sucede cuando se enfría lentamente el vidrio en la fabricación de botellas (de ahí el nombre recocido ), y es simulado, porque se usa una simulación por medio de una computadora.

En nuestro caso, eligiendo al azar dónde empezar (es decir, al entrar en la pieza se elige unfixture estándar cualquiera para comenzar), después de revisar entre 500.000 y un millón de fixtures en alrededor de 20 minutos en una PC 384 de aquella época, el programa que diseñó Eduardo encontraba un fixture que resolvía el problema. Aunque, como ya se sabía de antemano, la multa no podía ser cero (porque sabíamos que cualquier fixture tenía por lo menos cuatro fechas sin un partido entre dos equipos chicos).

Lo que el programa encontró fue un fixture con la mínima multa posible, es decir, con 15 fechas con un partido entre dos equipos chicos, que, además, satisfacía todos los otros requerimientos.

Lo curioso en este caso es que el programa que construyó Dubuc encontraba siempre el mismo fixture (salvo las equivalencias mencionadas al principio), independientemente de con cuál comenzaba el recorrido al entrar en la pieza.

Esto le permitió conjeturar que el que había encontrado era el único. O sea, había un solo fixture que resolvía el problema, y el método lo encontraba. La Asociación de Fútbol Argentino (AFA) implementó su uso a partir del campeonato Apertura de 1995 (que fue el torneo en el que Maradona produjo su retorno a Boca después de jugar en Europa). La utilización de matemática de alta complejidad permitió resolver un problema que hasta ese momento tenía enloquecidos a todos. Y a mano, hubiera llevado ¡diez mil años!






8 comentarios:

  1. Esto lo posteo rocho, sin dudas (?).
    Es broma, muy interesante post, todavia me acuerdo de algo de matematica y lo entendi. Me pregunto, si hubiera un torneo largo habria este problema? Igual muy buena la resolucion.

    ResponderEliminar
  2. Lo postee yo.Los libros de Paenza son un flash.Si,es exactamente lo mismo C.F.El fixture se hace para toda la temporada.

    ResponderEliminar
  3. No lei un carajo!!! jaja muy largo. PEPO

    ResponderEliminar
  4. alguien tiene un logaritmo o algo para hacer un fixture en lenguaje de programacioN?

    alejandroere_777@hotmail.com

    ResponderEliminar
  5. No tengo ni la mas puta idea de lo que estas hablando, Alejandro.

    ResponderEliminar
  6. Te esta preguntando que si tienes personalmente la solucion matematica al problema. Supongo que se lo podrias pedir a AFA. O si pides un logaritmo generico para hacer fixtures, supongo que es mas facil de investigar por tu cuenta.

    ResponderEliminar