Diseña un sitio como este con WordPress.com
Comenzar

Un problema de combinatoria

Imagina que tienes un tablero de 2×2 y unas fichas cuadradas con ciertos diseños con los que hacer diferentes configuraciones sobre el tablero:

Aquí puedes ver algunas de las configuraciones:

La pregunta es ¿cuántas configuraciones podemos hacer?

Lógicamente todo dependerá de las fichas/piezas de las que dispongamos y de los huecos del tablero que tengamos que rellenar. Supongamos que tenemos cuatro piezas del tipo 1, cuatro piezas del tipo 2 y dos piezas del tipo 3:

Dado que tenemos que escoger cuatro piezas de entre las diez que disponemos nuestro primer objetivo será ver cuántas posibilidades tenemos. Escribiremos (x_1,x_2,x_3) cuando tomemos x_1 piezas del tipo 1, x_2 piezas del tipo 2 y x_3 piezas del tipo 3. Además, sabemos que x_1+x_2+x_3=4 siendo x_i números enteros mayores o iguales que cero para todo i=1,2,3. En principio, obviaremos el hecho de que x_3 debe ser menor o igual que 2 (o no puede ser mayor o igual que 3). En este sentido, podríamos encontrar 15 posibles soluciones (aunque no todas nos valen):

Esta cantidad de combinaciones coincide con las soluciones de la ecuación diofántica mencionada anteriormente y, tal y como se puede ver en la página 44 de este PDF, se puede calcular como las combinaciones con repetición de 3 elementos tomados de 4 en 4:

Obviamente no todas estas combinaciones nos valen. Piensa, por ejemplo, en el caso (0,0,4). ¿Cómo vamos a escoger cuatro fichas del tipo 3 si solo disponemos de 2? Además de esta, las elecciones (1,0,3) y (0,1,3) tampoco nos valen.

En particular, desecharemos aquellas elecciones en las que x_3 sea mayor o igual que 3, es decir, debemos desechar tres de ellas.

La pregunta es: ¿cómo podemos saber cuántas elecciones debemos desechar? Escrito de otra forma, debemos desechar aquellas elecciones en las que x_1+x_2+x_3=4 con x_1,x_2 mayores o iguales que 0 y x_3 mayor o igual que 3. Para ello, podemos realizar el cambio de variable x’_3=x_3-3 en la ecuación x_1+x_2+x_3=4 y llegaríamos a la ecuación x_1+x_2+x’_3=1 siendo ahora x_1,x_2 y x’_3 mayores o iguales que cero. Aplicando el mismo razonamiento anterior, el número de soluciones de esta ecuación sale tres:

Esto quiere decir que tenemos 15-3 = 12 posibles elecciones en cuanto a las fichas:

Evidentemente no solo hay 15 posibles configuraciones de las fichas en el tablero. Ocurre, de hecho, que para cada una de las elecciones anteriores aparecen muchas configuraciones diferentes dependiente de las posiciones y orientaciones de las fichas escogidas. Por ejemplo, si tomamos cuatro fichas del primer tipo, es decir, (4,0,0), entonces saldrían 16 posibles configuraciones.

Y esto mismo ocurre para cada una de las elecciones. La pregunta ahora es: ¿cuántas configuraciones distintas aparecen en cada elección de las fichas (x_1,x_2,x_3)? Si las fichas solo pudieran ponerse en una orientación determinada, el número de posibles configuraciones sería este:

Por ejemplo, si tomamos cuatro fichas del segundo tipo y solo permitimos que se coloquen de una forma tendríamos obviamente una única configuración posible.

Sin embargo, ocurre que las fichas de tipo 1 admiten cuatro orientaciones distintas; las de tipo 2, admiten dos; y, las de tipo 3, solo una orientación.

Una vez escogidas las fichas y las posiciones, si tenemos en cuenta estas orientaciones, el número de configuraciones del tablero vendría dado por:

Por ejemplo, si volvemos a tomar cuatro fichas del tipo 2 y permitimos colocar la ficha en las dos orientaciones posibles, nos saldrían 16 configuraciones.

Es decir, con la primera elección de fichas tendríamos 16 diseños diferentes en el tablero. Para calcular el número total de configuraciones deberíamos sumar el resultado obtenido con la fórmula anterior para cada una de las posibles configuraciones.

En nuestro caso, se obtienen 1377 posibles configuraciones-diseños del tablero.

Evidentemente cuantas más fichas tengamos o más grande sea el tablero, el número de posibles diseños se dispara. Te muestro solo un ejemplo…

Imagina ahora que tu tablero es 4×4 y dispones de diferentes cantidades de ocho tipos de fichas cada uno de los cuales admite cierta cantidad de orientaciones diferentes. En particular:

Bajo estas condiciones, hay 231429 posibles elecciones de dieciséis fichas y, tendiendo en cuenta las diferentes posiciones y orientaciones, se obtienen un total de 12 103 255 169 241 096 000 000 configuraciones posibles (más o menos porque se ha calculado con ordenador y la representación en coma flotante pierde algunos decimales).

Estaremos de acuerdo que esto es una auténtica burrada. Solo por hacernos una idea, un año tiene 31 536 000 segundos. Si una persona vive 80 años, habrá vivido un total de 2 522 880 000 segundos. Y, si fuera capaz de configurar el tablero de una forma diferente en cada segundo, tardaría más de 4 797 396 000 000 vidas para poder visualizar todas las configuraciones posibles. Ahí lo dejo.

El código que he utilizado en Python se puede descargar desde aquí.

El planteamiento de este problema surgió de una duda de Kaufman (spanglish urban street artist, como él mismo se define en su web) y la resolución ha llegado de la mano de la colaboración con mi estimada amiga y compañera Mariola Molina, del departamento de Matemáticas de la Universidad de Alicante.

Anuncio publicitario

2 comentarios sobre “Un problema de combinatoria

Agrega el tuyo

  1. Hace unas semanas una amiga quiso volver a encender un móvil antiguo que tenía. No recordaba el patrón de bloqueo que puso. A partir de ahí comenzamos a preguntarnos cuántas combinaciones posibles se pueden hacer con los 9 puntos. Supongo que podría resolverse con un planteamiento similar. Nosotras miramos en internet y había millones de posibilidades. Hasta videos en los que se mostraban todas las formas posibles. Esto que muestras me ha recordado a aquello.

    Me gusta

    1. Hola, Natalia:

      Desde luego es un problema similar cuya solución se encuadra dentro de la «combinatoria». Además, como bien dices, intuyo que deben haber millones de posibles combinaciones.

      Un abrazo,
      Julio

      Me gusta

Deja una respuesta

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Salir /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Salir /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Salir /  Cambiar )

Conectando a %s

Blog de WordPress.com.

Subir ↑

La de Maldita Melena

Blog personal de Natalia Robles Mures

El sitio tranquilo

No sé vender mi producto

Messiánico de Alfredo N. Avila

Disfruta y comparte mis letras. Contenido diario... Sígueme para más inspiraciones literarias.

Qué vamos a hacer hoy

Matemáticas + Actividades en familia por Córdoba y en casa

Literatura de Japón

Tu portal de lectura asiática y mucho más.

Bits&Science

Ciencia natural y formal... con humor.

John Aranda

Blog de literatura, música, poesía y filosofía.

Letras & Poesía: Literatura Independiente

Plataforma que promueve el trabajo de escritores independientes

A %d blogueros les gusta esto: