Ya llega el final del verano (lo sé porque ya se ven los anuncios esos de "La Vuelta al Cole"), pero el chiringuito aún sigue aquí.
En esta ocasión el dueño del chiringuito me buscó para poder resolverle un pequeño problema que se le había planteado. Resulta que, como todos los años, había organizado la Liguilla de Dominó, en la que los participantes, por parejas, juegan una liguilla (ida y vuelta) durante todo el verano.
El problema surgió cuando una pareja tuvo que retirarse antes de tiempo y claro, ahora no sabe cuándo fue. El dueño me comentó que lo que sí sabe es que al final se jugaron un total de 50 partidas y que el número de parejas iniciales fue... le dije que parara, que no necesitaba ya más datos y que podría responderle a cualquier duda.
El dueño, finalmente, me preguntó que si la pareja llegó a jugar la Ida completa o si se retiró antes de finalizarla.
¿Sabríais vosotros responderle al dueño? Y por ciwerto, ¿cuántas parejas comenzaron el torneo?
Pues yo sí que pude responder y, gracias a esta respuesta, mis cañas y sardinillas de la semana final del verano están garantizadas.
Tito Eliatron Dixit
Si no me equivoco, la estructura de la liguilla se corresponde con un grafo completo, en el que cada nodo representa una pareja y cada arista identifica un par de encuentros (ida y vuelta).
ResponderEliminarDado que el número de aristas de un grafo tal es n*(n-1)/2, el número total de encuentros que debería realizarse -dadas n parejas- se corresponde con el doble de este valor: 2 de haber 2 parejas inscritas, 6 con 3, 12 con 4... 42 con 7 y 56 con 8.
Dicho esto, y sabiendo que todas las parejas menos -a lo sumo- una jugaron todas sus partidas, cabe considerar dos posibilidades:
a) que el número de partidas jugadas se corresponda con uno de los valores de la secuencia anterior, en cuyo caso el número de parejas se correspondería con el número asociado de nodos, y ninguna pareja se habría retirado.
b) que el número de partidas jugadas quede entre dos valores de la secuencia, en cuyo caso el número de parejas sería el correspondiente al conjunto de nodos asociado al siguiente valor de la secuencia, con una pareja que se retiró.
Así pues, estando en el caso b, se concluye que hubo en total 8 parejas inscritas, de las cuales una se retiró tras 8 encuentros (las 7 restantes jugaron los 42 encuentros previstos entre sí).
Respondiendo a la segunda pregunta, si los encuentros de la ida se realizaron consecutivamente, podemos afirmar que la pareja "desertora" la jugó al completo más un encuentro adicional.
P.D. Si no ya una señora sardinilla... ¿me he ganado al menos una aceituna o un mejillón? ;)
Pivalak, en tu razonamiento te faltaría comprobar que no pueden ser más de 8 parejas (que lo mismo lo has hecho pero no explicado, el punto b ese).
ResponderEliminarPara sacar que el número de partidas fue n(n-1) no hace falta recurrir a grafos, es combinatoria (variacones de n elementos tomados de 2 en 2). De hecho la fórmula que ha usado Pivalak también es combinatoria (combinaciones de n elementos tomados de 2 en 2).
Vamos, que lo de usar grafos es lo que se llama matar moscas a cañonazos!!
Hola Carlos.
ResponderEliminarCreía que quedaba claro, pero ya que lo reclamas, ahí va: en el caso b, dadas n parejas de las cuales una se retira, siempre quedaría el subgrafo completo de aquellas que jugaron todos sus encuentros. Por tanto, dado que n*(n-1) > 50 para n >= 8, este valor acota superiormente el espacio de soluciones del problema.
Y sí, usar grafos quizá haya sido excesivo... ¡pero resultan tan intuitivos (y las moscas son tan molestas)! :)
Mi forma de verlo es muy de "andar por casa":
ResponderEliminar8 parejas jugarían: 56 partidas (8x7)
7 parejas jugarían: 42 partidas (7x6)
56>50<42
De aquí se infiere necesariamente que iniciaron la partida 8 parejas, y que se dejaron de jugar exactamente 8 partidas (56-50).
Como cada pareja debe jugar un total de 14 partidas ((8-1)x2), está claro que la pareja que se retiró jugó la ida (7) y una partida de la vuelta.(7+1)