18/11/2018, 05:18:42 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Homenaje a aladan
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Máximo número de partidas de poker...  (Leído 3955 veces)
0 Usuarios y 1 Visitante están viendo este tema.
skan
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 236


Ver Perfil
« : 03/04/2017, 01:04:53 pm »

Imaginad que tenemos 16 jugadores de poker y los agrupamos en subgrupos de 4 para que jueguen partidas entre sí en 4 mesas.
Luego vuelves a hacer subgrupos de modo que ninguno coincida otra vez.
Y así sucesivamente.

¿Cuál es el mayor número posible de partidas que puede jugar un jugador?
¿Cuantas diferentes opciones hay?
Supongo que este tipo de problemas se podrá resolver por fuerza bruta, ¿Cuál sería el método más eficiente de representarlo? o con alguna formula, que en un principio pensé que sería simple combinatoria pero parece que tiene más miga.


Para este ejemplo de 16 jugadores en subgrupos de 4 parece que cada jugador sólo puede hacer 3 partidas:
3 partidas

a1 a2 a3 a4 - b1 b2 b3 b4 - c1 c2 c3 c4 - d1 d2 d3 d4
a1 b1 c1 d1 - a2 b2 c2 d2 - a3 b3 c3 d3 - a4 b4 c4 d4
a1 b2 c3 d4 - a2 b3 c4 d1 - a3 b4 c1 d2 - a4 b1 c2 d3

pero en general no sé como se calcula para un número cualquier N de jugadores repartidos en subgrupos de tamaño K.
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 42.963


Ver Perfil
« Respuesta #1 : 04/04/2017, 07:48:57 am »

Hola

 En el caso de [texx]16[/texx] jugadores puedes considerar el plano afín construido sobre el cuerpo de cuatro elementos [texx]F_{2^2}[/texx].

 Para cada dirección de paralelismo (hay 5), podemos considerar cuatro rectas paralelas que nos dividien los 16 puntos del plano en cuatro grupos disjuntos.

 Teniendo en cuenta que cada par de rectas no paralelas se cortan en exactamente un punto, cada grupo (recta) de dos de esas posibles divisiones en cuatro grupos disjuntos tienen sólo un elemento en común y por tanto los jugadores no repiten compañero de juegos en ninguna de las cinco.

 En el gráfico tienes el esquema de las cinco partidas. Cada punto de la cuadrícula es un jugador. Mueve el deslizador. Los grupos están representados por diamantes, cruces, círculos y aspas.



Saludos.

* afincautro2.ggb (12.2 KB - descargado 215 veces.)
En línea
skan
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 236


Ver Perfil
« Respuesta #2 : 04/04/2017, 08:40:29 am »

Buenas

No se me había ocurrido hacerlo así, no soy matemático y tengo que pensar como se hace esto, parece interesante.
De todos modos, entonces dices que 16 jugadores pueden jugar 5 partidas.

Entonces en la nomenclatura que he puesto

a1 a2 a3 a4 - b1 b2 b3 b4 - c1 c2 c3 c4 - d1 d2 d3 d4
a1 b1 c1 d1 - a2 b2 c2 d2 - a3 b3 c3 d3 - a4 b4 c4 d4
a1 b2 c3 d4 - a2 b3 c4 d1 - a3 b4 c1 d2 - a4 b1 c2 d3

Me salen 3, ¿Qué otras 2 faltarían?
Espera que lo voy a intentar sacar de tu gráfico.

Estaría bien que explicases como llegas a construir ese esquema.
¿Y la formula que me diga el número máximo de partidas dados N jugadores y k subgrupos?
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 42.963


Ver Perfil
« Respuesta #3 : 04/04/2017, 08:48:12 am »

Hola

No se me había ocurrido hacerlo así, no soy matemático y tengo que pensar como se hace esto, parece interesante.
De todos modos, entonces dices que 16 jugadores pueden jugar 5 partidas.

Entonces en la nomenclatura que he puesto

a1 a2 a3 a4 - b1 b2 b3 b4 - c1 c2 c3 c4 - d1 d2 d3 d4
a1 b1 c1 d1 - a2 b2 c2 d2 - a3 b3 c3 d3 - a4 b4 c4 d4
a1 b2 c3 d4 - a2 b3 c4 d1 - a3 b4 c1 d2 - a4 b1 c2 d3

Me salen 3, ¿Qué otras 2 faltarían?
Espera que lo voy a intentar sacar de tu gráfico.

Si. Míralo en el gráfico. Usa [texx]a,b,c,d [/texx]por ejemplo para numerar las filas y [texx]1,2,3,4[/texx] las columnas (para copiar tu notación). Y ve anotando los grupos que salen.

Cita
¿Y la formula que me diga el número máximo de partidas dados N jugadores y k subgrupos?

Esto hay que pensarlo con cuidado. Para ciertos valores concretos basta generalizar el razonamiento anterior.

Saludos.
En línea
skan
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 236


Ver Perfil
« Respuesta #4 : 04/04/2017, 09:03:06 am »

Si no me he equivocado sale

a1 a2 a3 a4 - b1 b2 b3 b4 - c1 c2 c3 c4 - d1 d2 d3 d4
a1 b1 c1 d1 - a2 b2 c2 d2 - a3 b3 c3 d3 - a4 b4 c4 d4
a1 b2 c3 d4 - b1 a2 d3 c4 - c1 d2 a3 b4 - d1 c2 b3 a4
d1 b2 a3 c4 - b1 d2 c3 a4 - c1 a2 b3 d4 - a1 c2 d3 b4
a1 d2 b3 c4 - b1 c2 a3 d4 - c1 b2 d3 a4 - d1 a2 c3 b4


El problema lo vi aquí:

https://cs.stackexchange.com/questions/67832/game-tournament-program-np-complete/67855

Pero ahí dan una formula que viene de un paper demasiado complejo.
Y además sale 20, aunque supongo que eso será no el número total de rounds sino el de subgrupos, que habría que dividir por 4 en este caso.
El problema es que antes alguien dice que le salen 3 rondas y me despistó.
En línea
skan
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 236


Ver Perfil
« Respuesta #5 : 04/04/2017, 09:06:05 am »

Si lo que queremos no son las combinaciones sino sólo el número de rondas ¿Sería correcto decir esto...?
En la primera ronda cada jugador puede jugar contra otros 15.
en la segunda contra 12.
en la tercera contra 9
en la cuarta contra 6
en la quinta contra 3
y se acabó.
total 5 rondas.

Aunque para otros valores de N y k puede ser más complicado.


De todos modos eso que has puesto de las rectas, las direcciones de paralelismo... no lo acabo de entender.
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 42.963


Ver Perfil
« Respuesta #6 : 04/04/2017, 12:06:54 pm »

Hola

Si lo que queremos no son las combinaciones sino sólo el número de rondas ¿Sería correcto decir esto...?
En la primera ronda cada jugador puede jugar contra otros 15.
en la segunda contra 12.
en la tercera contra 9
en la cuarta contra 6
en la quinta contra 3
y se acabó.
total 5 rondas.

Si; así razonas que como máximo son posibles cinco rondas. Directamente en cada ronda un jugador juega con tres jugadores distintos. Por tanto el número posible máximo de rondas son [texx](16-1)/3=5[/texx].

Pero después hay que justificar que efectivamente existe alguna configuración de grupos donde se alcanza ese máximo posible.

Cita
De todos modos eso que has puesto de las rectas, las direcciones de paralelismo... no lo acabo de entender.

No sé si es muy fácil de explicar sin tener alguna idea sobre cuerpos finitos.

La ecuación de una recta en el plano es [texx]y=ax+b[/texx] ó [texx]x=b[/texx] (rectas verticales). El valor de [texx]a[/texx] es la pendiente. La recta vertical tendría pendiente infinita.

La cosa es que si trabajamos con un cuerpo finito con cuatro elementos (en lugar de en [texx]\mathbb{R}[/texx] como estamos acostumbrados) los posibles valores de la pendiente son [texx]a=0,1,2,3[/texx] y las verticales: cinco direcciones de paralelismo. Cada recta tiene tantos puntos como elementos el cuerpo: cuatro. Y rectas paralelas no se cortan. Por tanto por cada dirección de paralelismo hay cuatro rectas paralelas que nos dan nuestra distribución en cuatro grupos:

[texx]y=ax+0[/texx], [texx]y=ax+1[/texx], [texx]y=ax+2[/texx], [texx]y=ax+3[/texx]

A la hora de plasmar esto en cuentas hay que saber como se comporta la suma y el producto del cuerpo de cuatro elemento. No es obvio.

Quizá te pueda ayudar este enlace:

http://math.stackexchange.com/questions/1925479/affine-plane-of-order-4-picture

Por otra parte en el artículo al que te refieren lo que calcula es el máximo número de subconjuntos posibles de cuatro elementos, de manera que cada par de jugadores sólo aparezca en uno de ellos.

Saludos.
En línea
skan
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 236


Ver Perfil
« Respuesta #7 : 04/04/2017, 12:28:44 pm »

Hola

Si; así razonas que como máximo son posibles cinco rondas. Directamente en cada ronda un jugador juega con tres jugadores distintos. Por tanto el número posible máximo de rondas son [texx](16-1)/3=5[/texx].



Aunque ahí no compruebo que no existan otro tipo de "restricciones" impuestas por las relaciones entre otros jugadores simultáneamente...
¿Cómo se ve fácilmente que no hay que comprobar nada más?

La ecuación de una recta en el plano es [texx]y=ax+b[/texx] ó [texx]x=b[/texx] (rectas verticales). El valor de [texx]a[/texx] es la pendiente. La recta vertical tendría pendiente infinita.

La cosa es que si trabajamos con un cuerpo finito con cuatro elementos (en lugar de en [texx]\mathbb{R}[/texx] como estamos acostumbrados) los posibles valores de la pendiente son [texx]a=0,1,2,3[/texx] y las verticales: cinco direcciones de paralelismo. Cada recta tiene tantos puntos como elementos el cuerpo: cuatro. Y rectas paralelas no se cortan. Por tanto por cada dirección de paralelismo hay cuatro rectas paralelas que nos dan nuestra distribución en cuatro grupos:

[texx]y=ax+0[/texx], [texx]y=ax+1[/texx], [texx]y=ax+2[/texx], [texx]y=ax+3[/texx]


¿Y si por ejemplo quisieramos hacerlo con 20 jugadores en grupos de 5?
¿Trabajaríamos con 4 rectas y 5 puntos en cada una o al revés?
¿Y esto esta forma de hacerlo se te ha ocurrido pensando o porque es típico hacerlo así?
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 42.963


Ver Perfil
« Respuesta #8 : 04/04/2017, 01:12:20 pm »

Hola

¿Cómo se ve fácilmente que no hay que comprobar nada más?

Es que no sé si eso se puede ver fácilmente. Por eso precisamente busqué una forma de explicitar los grupos.

Cita
¿Y si por ejemplo quisieramos hacerlo con 20 jugadores en grupos de 5?
¿Trabajaríamos con 4 rectas y 5 puntos en cada una o al revés?
¿Y esto esta forma de hacerlo se te ha ocurrido pensando o porque es típico hacerlo así?

No, no. No es tan fácil de generalizar. Tendría que pensarlo con más calma. Ahora tengo que irme.

Fíjate que con [texx]20[/texx] jugadores en grupos de [texx]5[/texx] a lo sumo podría haber 4 rondas ([texx](20-1)/(5-1)=4.75[/texx])

Saludos.
En línea
skan
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 236


Ver Perfil
« Respuesta #9 : 04/04/2017, 01:28:10 pm »

Pues por poner números fáciles,
16 jugadores en grupos de 6.

Y lo que me extraña es que si aplico esa formula a 13 jugadores en grupos de 4 me debería dar 12/3=4 rondas, pero no puede ser porque 13 jugadores no pueden dividirse en grupos de 4.
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 42.963


Ver Perfil
« Respuesta #10 : 04/04/2017, 02:12:24 pm »

Hola

Cita
Pues por poner números fáciles,
16 jugadores en grupos de 6.

Pero no entiendo bien. [texx]16[/texx] no es divisible por [texx]6[/texx]. De cada vez sólo podrías formar dos grupos y sobrarían cuatro jugadores.

Y lo que me extraña es que si aplico esa formula a 13 jugadores en grupos de 4 me debería dar 12/3=4 rondas, pero no puede ser porque 13 jugadores no pueden dividirse en grupos de 4.

Sigo con prisas; pero insisto en que no es tan sencilla la cuestión. Esa fórmula no es más que una cota superior del número de rondas.

Saludos.
En línea
skan
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 236


Ver Perfil
« Respuesta #11 : 04/04/2017, 03:35:35 pm »

Ups, me he equivocado.

Digamos que tenemos 45 jugadores y los queremos poner en grupos de 5, ¿Cómo lo haces con tu método?

No tengo ninguna prisa :sonrisa:
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 42.963


Ver Perfil
« Respuesta #12 : 06/04/2017, 06:38:03 am »

Hola

Digamos que tenemos 45 jugadores y los queremos poner en grupos de 5, ¿Cómo lo haces con tu método?

Mi método, tal cual lo he expuesto, sólo vale para [texx]q^2[/texx] jugadores en grupos de [texx]q[/texx] con [texx]q=p^s[/texx] y [texx]p[/texx] primo.

En el caso que citas el número máximo de partidas sería [texx](45-1)/(5-1)=11[/texx].

La cuestión es si se alcanza.

Creo que la solución está en este artículo:

"Balanced incomplete block designs and related designs". H. Hanani. Discrete Math., 11 (1975), pp. 225-369

Lo he ojeado simplemente, pero allí también se habla del método que te indiqué.

Échale un vistazo. Si tengo tiempo trataré de leerlo con más calma. De todas formas desde luego no es una cuestión que se solvente con un razonamiento inmediato o trivial.

Saludos.
En línea
skan
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 236


Ver Perfil
« Respuesta #13 : 06/04/2017, 07:05:25 am »

Gracias.
No te preocupes, sólo era una curiosidad, no pensaba que se complicase tanto la cosa.
En línea
skan
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 236


Ver Perfil
« Respuesta #14 : 26/05/2017, 02:57:55 pm »

Hola otra vez.

En otro foro, al final de este hilo:
http://forum.lawebdefisica.com/threads/37724-M%C3%A1ximo-n%C3%BAmero-de-partidas-de-poker/page2
alguien se ha currado otra demostración

¿Te parece correcta?

En línea
skan
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 236


Ver Perfil
« Respuesta #15 : 14/09/2018, 08:46:26 am »

Hola

Digamos que tenemos 45 jugadores y los queremos poner en grupos de 5, ¿Cómo lo haces con tu método?

Mi método, tal cual lo he expuesto, sólo vale para [texx]q^2[/texx] jugadores en grupos de [texx]q[/texx] con [texx]q=p^s[/texx] y [texx]p[/texx] primo.

En el caso que citas el número máximo de partidas sería [texx](45-1)/(5-1)=11[/texx].

La cuestión es si se alcanza.

Creo que la solución está en este artículo:

"Balanced incomplete block designs and related designs". H. Hanani. Discrete Math., 11 (1975), pp. 225-369

Lo he ojeado simplemente, pero allí también se habla del método que te indiqué.

Échale un vistazo. Si tengo tiempo trataré de leerlo con más calma. De todas formas desde luego no es una cuestión que se solvente con un razonamiento inmediato o trivial.

Saludos.


¿Con 64 jugadores en mesas de 8 sería  (64-1)/(8-1)=9?
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!