[germanzorba]

Una forma de hallar con total seguridad el mínimo es con los algoritmos FBI (Fuerza Bruta e Ignorancia). Es decir, probar toooooodas las combinaciones posibles para 7 partidos, a ver si alguna sirve. Si ninguna sirve, entonces probamos tooooooooodas las de 8 partidos y así, hasta que alguna sirva o el sol se convierta en supernova y ya no nos interese resolver el problema.

Hace mucho que no programo, pero si vas a hacerlo, recomiendo probar primero con 6 partidos (aún sabiendo que no habrá solución) para poder estimar el tiempo que tardará el algoritmo para 7 (hasta 13^8 veces más, según como lo programes)

Este fin de semana tengo que corregir exámenes, pero si nadie lo hace antes posiblemente yo intente hacer algo el próximo.

Saludos

[Luis Fuentes]

Hola

 Algoritmo que da la solución.

 Sea  N el número de partidos que pueden jugarse. Si queremos ser explícitos:

 \( N=\displaystyle\frac{1}{2}\displaystyle\binom{13}{8} \)

 Estos N partidos pueden ordenarse de N! formas. Definimos:

 a(k)=número de partidos necesarios en la ordenación k para que TODOS hallan jugado CON y CONTRA TODOS

 Entonces el valor buscado es:

\(  x=min\{a(k),k=1,..,n\} \)

 Todo esto es programable y calculable con un ordenador.... con suficiente memoria porque manejamos un número FINITO de datos.

 El problema es que en este caso el algortimo sería lentísimo (de hecho es el más burdo: comprobar todas las posibilidades).

 Pero con esto quiero hacer ver que SI EXISTE UN ALGORTIMO QUE DA LA SOLUCION.

Y en 13 partidos está muy fácil.

¿Muy fácil? Pues tu dirás... organiza los trece partidos de manera que TODOS hallan jugado con y contra TODOS. Con eso Ulises será feliz.

Saludos.

P.D. Donde dices ínfimo debiera ser cota inferior, pero eso sólo son nombres, es lo de menos.

P.D.D. Acabo de ver el mensaje de german.. mi algoritmo es el FBI 

P.D.D.D. Alguien leyó donde comenté que no es posible en 7 partidos?

[Jabato]

¡Toma claro!, así "calculo" yo también cual es el mínimo. Aunque debería de haber algún matiz diferencial entre lo que solemos llamar "cálculo" y esa operación matemática que nos propones manco.

Evidentemente el número de combinaciones es finito, pero no el número de algoritmos posibles, ese sí que es infinito. El problema pide que busquemos un algoritmo que haga que ... etc.

[Luis Fuentes]

Hola

 En cuanto a mi afirmación:

 "El problema de calcular el mínimo número de partidos necesarios para que todos jueguen con y contra todos tiene solución" (indpendientemente de que encontremos o no un algoritmo).

 Sigo en ella. Mi algortimo FBI por supuesto no pretende solucionar el problema sino reforzar esa afirmación (ya no se como reforzarla más).

 Pero no insisto más porque es cansino. Sigo convencido de que en relidad estamos de acuerdo, pero nos referimos a cosas disintos.

 El caso es que programé tu algoritmo, Jabato. No me riñas si metí la pata porque dio su trabajo. Lo hice en matlab, y me resultó que da la solución en..... 16 partidos!!!!!

 Aquí van:

     1     3     4     5
     2     6     7     8

     9    11    12    13
    10     1     2     3

     4     6     7     8
     5     9    10    11

    12     1     2     3
    13     4     5     6

     7     9    10    11
     8    12    13     1

     2     4     5     9
     3     6     7     8

    10    12    13     4
    11     1     2     3

     5     7     8    12
     6     9    10    11

    13     2     3     7
     1     6     8     9

     4    10    11    12
     5    13     1     2

     3     9    10    11
     4    13     7     8

     5    12     3     4
     6     1     2    13

     5     7     8    10
     6    12    11     3

     9     2     4     5
     1     7    10    11

     6    12    13     4
     8     9     2     3

     1    12     6     7
     5    11    13     8

 La comprobación de que juegan todos con y contra todos la hace el programa. Pero como es fácil haber metido la pata no estaría de más comprobarlo a mano.

 Si es cierto, al menos ya tenemos una cota superior e inferior para ese mínimo:

 8<=x<=16.

Saludos.

P.D. Corregido antes puse 14 pero me equivoqué.

P.D.D. Probablemente tenga que depurar el algoritmo pero lo que hay es un punto de partida.


 

[Jabato]

Porque voy a reñirte hombre, no creo que deba, ni que pueda, ni tan siquiera que tenga derecho a hacer tal cosa, al contrario, como ya hice notar en algún mensaje anterior, tan solo darte las gracias hombre. La idea que supongo da fundamento a estos foros es buscar debatir y aportar ideas, para tratar de poner un poco más de luz en el mundo oscuro que nos rodea. No se trata de averiguar quien sabe más, sino de averiguar quien aprende más.

Saludos Jabato.

[Luis Fuentes]

Hola

 Modifiqué el algoritmo bajando el "peso" en las puntuaciones del número de partidos jugados.

 Ahora, consigue el objetivo en sólo 13 partidos:

  1  3  4  5  vs   2  6  7  8
 9 11 12 13  vs  10  1  2  3
 4  6  7  8  vs   5  9 10 11
12  1  2  3  vs  13  4  5  6
 7  9 10 11  vs   8 12 13  1
 2  4  5  9  vs   3  6  7  8
10 12 13  4  vs  11  1  2  3
 5  7  8 12  vs   6  9 10 11
13  2  3  7  vs   1  6  9  4
 5 10 11 12  vs   8  9 13  1
 2  4  5  6  vs   3  8  9 10
 7  1 12 13  vs  11  4  8  2
 3  6 11 12  vs   5  7 13  1

Cada jugador juega 8 partidos excepto el 1 (juega 9) y el 10 (juega 7).

Esta es un buena solución para Ulises.

Saludos.
 

[Jabato]

La verdad es que me sigue pareciendo alto el número de partidos para este algoritmo, aunque de momento va muy bien la cosa, ¿has probado otras relaciones en los pesos? Podías intentar hacer un gráfico dando valores a dicha relación:

\( r=pcon/ppar \)

Yo creo que el algoritmo debería ser capaz de encontrar alguna combinación con 10 partidos ó menos, aunque claro está, es solo una opinión sin fundamento alguno.

Saludos, Jabato.

[ulises2010]

Y en 13 partidos está muy fácil.

¿Muy fácil? Pues tu dirás... organiza los trece partidos de manera que TODOS hallan jugado con y contra TODOS. Con eso Ulises será feliz.

Os aseguro que soy feliz sólo viendo la deriva de la discusión e intentando seguir (me pierdo en muchos conceptos) vuestros razonamientos

Lo hice en matlab, y me resultó que da la solución en..... 16 partidos!!!!!

Desde luego por mi parte serían asumibles 16 partidos, aunque creo que no todos los jugadores disputan el mismo número de partidos

Cada jugador juega 8 partidos excepto el 1 (juega 9) y el 10 (juega 7).

Esta es un buena solución para Ulises.

Para mi puede ser una buena solución, aunque no sé  lo que dírá el jugador número 10 (supongo que al 1 no le importará poder ganar más puntos)... ;-)

Insisto en daros las gracias a todos por vuestro interés, y aunque soy consciente de que mis necesidades no son lo primordial, sino que ya habeís entrado a debatir sobre otros conceptos, lo cierto es que si mi intención es organizar una competición un requisito esencial sería que todos los jugadores disputaran el mismo número de partidos....

Bueno, espero no liaros más, y de verdad que me sentiría abrumado por vuestro interés, sino fuera porque leyendos me doy cuenta de que vosotros también estaís pasandolo bien.

Gracias de nuevo

Ulises

[Luis Fuentes]

Hola

Insisto en daros las gracias a todos por vuestro interés, y aunque soy consciente de que mis necesidades no son lo primordial, sino que ya habeís entrado a debatir sobre otros conceptos, lo cierto es que si mi intención es organizar una competición un requisito esencial sería que todos los jugadores disputaran el mismo número de partidos....

Si quieres que todos jueguen el mismo número de partidos, la única posibilidad es que el número total de partidos sea siempre múltiplo de 13 (13,26,39,...; cada jugador jugaría 8,16,24... partidos respectivamente).

Por otro lado aunque no lo he probado rigurasamente es IMPOSIBLE en 13 partidos que todos hallan jugado el mismo número de partidos y al mismo tiempo CON y CONTRA todos.

Así que para llevar a cabo tu campeonato sin que se te dispare el número de encuentros, tienes que renunciar a algo:

 - Si quieres que todos juegen el mismo número, deberás renunciar a que todos juegen con y contra los demás. Una solución sería la primera que propuse.

 - Si quieres que todos juegen CON y CONTRA los demás, deberás de renunciar a que todos juguen el mismo número de partidos. En ese caso la última solucíon que puse podría valerte.

Saludos.

[ulises2010]

Si no hay más remedio que renunciar a algo supongo que optaría por acercarse lo más posible a que todos jugasen con o contra todos aunque no se lograse.

Supongo que entonces tu primera solución sería la ideal ¿no?...

Creo que todos jugaban con todos aunque a todos les faltaba jugar contra dos ¿no es así?