[Téc. M]

Hola,

   Tengo el siguiente problema: Dada una matriz de 4x3 y un conjunto de cuatro números; 1,2,3 y 4, encontrar todas las posibles combinaciones que se pueden lograr con estos números de forma que no se repita ninguno de estos horizontalmente ni verticalmente.

Planteo lo siguiente:

\( \begin{bmatrix} a & a+1 & \ldots & a+3 \\ a+1 &a & \ldots & a+2 \\ \vdots&&&\vdots \\a+3 &a+2 &\ldots & a\end{bmatrix} \)

Supongamos que ese es un ejemplo de una posible configuración para el problema, donde podemos suponer a=1 a+1=2...

Para cada fila, puedo variar los cuatro elementos sin repetirlos de V44=4!
Si hago todas esas variaciones en las filas horizontales, ya hice todas las variaciones en las filas verticales.

Osea, la cantidad maxima de variaciones es: V44 . V44 . V44= \( (4!)^3 \)

El problemas es que ahora se me repiten verticalmente las cifras, ¡por lo que tendría que calcular las veces que sucede eso entre las columnas y restarselas a las variaciones totales!. En algun momento se me ocurrió probar que pasaba si dividia las variaciones totales por la cantidad de permutaciones de 4 elementos y sorprendentemente me dió el resultado (corroborado con qbasic =p).

\( C=\displaystyle\frac{  V4,4 .  V4,4 .  V4,4 }{P4}=\displaystyle\frac{4! 4! 4!}{4!}=576 \)

Me parece que de bien es solo casualidad, me interesaria saber como se debe hacer correctamente!

Muchas gracias por su ayuda

Saludos

Téc M

[Gerardo Exequiel Pozzi]

Jeje te salio de la galera esa permutación

Está bien como lo pensas.

Igual, los nombres son al revés, en Argentina llamamos variaciones a las permutaciones cuando no entran en juego todos los elementos.
Entonces para el caso de 4 elementos tomados de 4 en 4, son simplemente permutaciones de 4 elementos.
En cambio, a pesar de que dé lo mismo, en el caso de permutaciones de 4, yo lo veo como variaciones de 4 elementos tomados de 3 en 3. \( \frac{4!}{(4-3)!} = 4! \)

Ahora el razonamiento posible que podría seguir, olvidándome de factoriales y formulas es:

Primera fila
Para el primer elemento tengo 4 posibilidades, para el segundo 3, ... 2, y 1.
La segunda fila:
Tengo 3 posibilidades, luego 2, luego 1 y finalmente 1
Tercera fila:
Tengo 2 posibilidades, luego 2, ...1 y 1.

En definitiva: (4*3*2*1) * (3*2*1*1) * (2*2*1*1) = 576

Salut!

[Téc. M]

Hola!

 ... Realmente no te entedi porque decis que el la sugunda tenes 3.2.1 posibilidades y en la tercera 2.1.1 posibilidades. Lo que había pensado era que tenía 4.3.2.1 posibilidades en todas y despues restar las que se repiten. Te agradeceria si me explicaras cual es el razonamiento que haces ( por como lo explicaste no debe ser jodido... el problema es que cuando encare este problema me complique demasiado  )

Muchas gracias!

Saludos

Téc M!

[Gerardo Exequiel Pozzi]

mmmm pensandolo mejor, hay algo que no me gusta en la forma que puse


Yo lo razoné así:

En la primera fila estamos de acuerdo: \( 4 \cdot 3 \cdot 2 \cdot 1 \)

Segunda fila:
Su primer elemento tengo 4 números (en mano), menos un número en esa columna de la fila de arriba que justamente no puedo poner, es decir tengo 3 posibilidades para ese lugar.
Segundo elemento de la segunda fila, tengo 3 números (en mano), menos un número en esa columna que no puedo usar de la fila de arriba, es decir 2 posibilidades.
Tercer elemento, tengo 2 en mano, menos uno de arriba o bien ninguno: 1 posibilidad, o bien 2 posibilidades (esto en un comienzo no lo consideré el "o bien").
Cuarto, tengo uno sólo, 1 posibilidad.

Tercera fila, el razonamiento es similar, pero hay que tener en cuenta ese "o bien" de arriba.

En resumen puede ser que ocurra:
\( \begin{bmatrix} 4 & 3 & 2 & 1 \\ 3 & 2 & 1 & 1 \\ 2 & 2 & 1 & 1\end{bmatrix} \)

Pero también puede darse este caso:

\( \begin{bmatrix} 4 & 3 & 2 & 1 \\ 3 & 2 & 2 & 1 \\ 2 & 1 & 1 & 1\end{bmatrix} \)

A lo que voy es: supongamos esta forma de acomodar:

1,2,3,4
3,4,x,y en x, puedo poner el 1 o 2,
a,b,c,d en a puedo poner el 2 o 4, en b puedo poner el 1, 3, para c queda una sola posibilidad

Pero si tengo así:
1,2,3,4
2,1,x,y en x, sólo puedo poner el 4
a,b,c,d en a puedo poner el 3 o 4, en b puedo también el 3 o el 4, luego para el c, también voy a tener dos posibilidades.

Digamos que también mi pensamiento intuitivo estaba "equivocado" pero sirvió, eso sí me estaba olvidando la otra solución.

Espero no confundirte.

[Gerardo Exequiel Pozzi]

Por cierto, al tener dos formas de armar la matriz, esas dos formas cada una me da 576 posibilidades, ¿o sea 576 + 576 = 1152? Donde diferimos en la solución final.

Igual quiero seguir analizándolo.

¿Tu programa en BASIC, como lo hiciste?

[Téc. M]

Hola,

   Muchas gracias por responder. El programa lo hice en Qbasic (bueno, tendría que aprender un nuevo lenguaje jeje, sera que me gustan los clásicos). Es un programa sencillo lineal que analisa todos los casos con un algoritmo de baja calidad echo con la única finalidad de darme el resultado.
 
   Entiendo tu planteo, y veo las 2 formas de armar la matriz.

\( \begin{bmatrix} 4 & 3 & 2 & 1 \\ 3 & 2 & 1 & 1 \\ 2 & 2 & 1 & 1\end{bmatrix} \)
\( \begin{bmatrix} 4 & 3 & 2 & 1 \\ 3 & 2 & 2 & 1 \\ 2 & 1 & 1 & 1\end{bmatrix} \)

  Ahora como hay 2 posibles configuraciones de matrices, sumas las posibilidades de cada una y te da 1152. Voy a encarar el problema mañana de otra forma haber si concuerda con el resultado que obtuviste. El mayor problema que me dio este problema (    ) fue que planteandolo de varias formas distintas ¡me dio diferentes cosas!

Muchas gracias

Saludos

Téc M!

[Luis Fuentes]

Hola

 Una forma de plantearlo:

 1) Para la primera columna podemos colocar cualquier permutación de los cuatro números. Supondré la trivial y luego multiplico el resultado por \( 4!. \)

\( \begin{bmatrix}{1}&{*}&{*}\\{2}&{*}&{*}\\{3}&{*}&{*}\\{4}&{*}&{*}\end{bmatrix} \)

 2) La primera fila puedo completarla con los dos elementos que yo quiera distintos de 1 y distintos entre si. Hay \( 3\cdot 2=6 \) seis formas de elegirlos. Pero elija lo que elija el número de posibilidades para los "huecos" restantes son siempre las mismas, sin más que intercambiar el papel de los números. Supondré entonces que coloco \( 2 \) y \( 3 \) y luego multiplicaré el resultado por \( 6 \).

\( \begin{bmatrix}{1}&{2}&{3}\\{2}&{*}&{*}\\{3}&{*}&{*}\\{4}&{*}&{*}\end{bmatrix} \)

 3) En lo que me queda, y esto quizá no sea muy elegante, directamente escribo todas las posiblidades (hay pocas):

\( \begin{bmatrix}{1}&{2}&{3}\\{2}&{1}&{4}\\{3}&{4}&{1}\\{4}&{3}&{2}\end{bmatrix},\quad
\begin{bmatrix}{1}&{2}&{3}\\{2}&{1}&{4}\\{3}&{4}&{2}\\{4}&{3}&{1}\end{bmatrix},\quad
\begin{bmatrix}{1}&{2}&{3}\\{2}&{3}&{4}\\{3}&{4}&{1}\\{4}&{1}&{2}\end{bmatrix},\quad
\begin{bmatrix}{1}&{2}&{3}\\{2}&{4}&{1}\\{3}&{1}&{4}\\{4}&{3}&{2}\end{bmatrix}. \)

 Por tanto en total las opciones son:

\(  4!\cdot 6\cdot 4=24^2=576 \)

 Es interesante observar que el problema equivale a contar de cuantas formas se pueden colocar los números \( 1,2,3,4 \) en un matriz cuadrada \( 4\times 4 \), sin repetirlos en fila y en columna, ya que colocadas las 3 primeras columnas la cuarta sólo tiene una opción.

 Esto último se llama el problema del Cuadrado Latino y su generalización no es sencilla:

http://es.wikipedia.org/wiki/Cuadrado_latino

Saludos.

[Téc. M]

Hola gente,

 Primero que nada gracias a los 2. El_manco, no se si tu respuesta sera elegante pero de seguro fue didactica, entendi la manera en que encaraste el problema y te lo agradesco!

Saludos   

Téc M!