[Programación] Re: [Programación] Generar cartones de Bingo

[Rafael Bidegain]

On Wed, 16 Mar 2005 00:20:49 -0300, Pablito <pablo_foros@yahoo.com.ar> wrote:
> Gente:
> Me quede pensando el problema. Me parece muy interesante. Porque es
> fácil de entender, parece simple de resolver, pero no lo es. Me hace
> acordar al problema del circuito hamiltoniano. Esta bueno intentar
> resolver el problema por cuenta propia, pero si nuestra solución es
> aparentemente ineficiente, no nos con vence o tal vez no la tenemos, es
> mejor pedir ayuda. Las personas apropiadas para resolver este problema
> son los matemáticos. No traté de ofender a nadie con lo que dije en el
> mail anterior.
> 
> Rafael:
> Al problema lo intenté pensar de varias maneras buscando una solucion,
> pero sin tener exito, les paso a comentar un enfoque, a ver si a alguien
> se le prende la lamparita.
> 
> Supongan que tienen generados todos los cartones. Es más supongan que
> tienen un grafo, en donde los vértices son los cartones, y dos vertices
> se unen si no tienen ninguna cifra en común.
> Por lo tanto tengo un grafo de C(20 5)=15504 vertices donde cada uno se
> une con C(15 5)=3003 vertices.
> Cada solución posible del problema se puede ver como un "coloreo" de
> grupo de 4 vertices que se unen todos con todos entre ellos (un completo
> de 4). (¿se entiende?)
> 
> Para entenderlo mejor se pueden construir un super-mini-bingo. Supongan
> que los cartones tienen solo 2 números y los numeros van del 1 al 6.
> (entonces C(6 2)=15 vertices). Y los cartones se agrupan de a 3. (Cada
> vertice tiene C(4 2)=6 aristas).
> 
> En este caso hay que pintar con colores diferentes triangulos (un
> completo de 3).
> 
> Creo que el mini-modelo es bueno ya que se cumple lo siguiente:
> 
> agrupacion de cartones*cantidad de numeros por carton= cantidad de
> numeros posibles.
> 
> en el Bingo:
> 
> 4*5=20.
> 
> en el mini-modelo:
> 
> 2*3=6.
> 
> Por ahi alguien conoce algún algoritmo para hacer este coloreo.
> 
> Qué les parece si proponemos una manera (así sea fuerza bruta) y la
> tratamos de mejorar. Tal vez lleguemos a alguna euristica simpática.
> 
> Saludos.
> Pablito.
> 
Pablito gracias por dedicarle tiempo al problema
creo que hay un error en tu analisis pero me gusta la idea de trabajar
con un mini bingo para probar el algoritmos

si tomas un carton culquiera solo tenes 1001 cartones posibles para
combinarlo (no 3003)
y despues de combinar esos 2 cartones solo te quedan 126 posibilidades
para el tercer carton.
una vez seleccionados tres cartones solo hay 1 posibilidad para completar los 4

-- 
/* Rafael Bidegain
Linux Registered User # 204304
CaFeLUG Grupo de Usuarios de Software Libre de Capital Federal
http://www.cafelug.org.ar */