Razonamiento matemático pregunta

Question

Me estaba dando un vistazo a mi país de la matemática de los juegos olímpicos, y me encontré con este problema

Si quiero el color de una $4\times 4$ cuadrícula con cuadros blancos y negros, de cuántas maneras puedo pintar de tal manera que cada fila y cada columna tiene 2 plazas de cada color?

Después de pensar un rato, decidí código de un programa que me dio ideas sobre el problema inverso de ingeniería de la respuesta.Ningún éxito.Aparentemente, la respuesta es $90$, pero ¿cómo la matemática de la forma de hacer esto?

Answer 1

Otro método es reconocer que, hasta permutaciones de filas y de columnas, sólo hay dos no equivalentes plazas:

$$ \begin{array}{|cccc|} \hline 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ \hline \end{array} \quad\quad\quad\text{y}\quad\quad\quad \begin{array}{|cccc|} \hline 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ \hline \end{array} $$ Estos son los biadjacency matrices de los vértices de color bipartita de gráficos:

$\quad\quad\quad\text{and}\quad\quad\quad$

respectivamente. Por lo que el número de tales matrices es igual al número de vértices de color, etiquetado) gráficos isomorfo a uno de los dos grafos bipartitos de arriba.

Por la Órbita Estabilizador Teorema, podemos calcular los tamaños de estas clases de isomorfismo mediante el cálculo de los tamaños de los automorphism de los grupos (que se puede hacer a mano). Por lo tanto, estos han isomorfismo clases de tamaño:

$$\frac{4!^2}{2^5} \quad\quad\quad\text{and}\quad\quad\quad \frac{4!^2}{8}$$ respectively. These sum to $90$.

Answer 2

Este problema pide la enumeración de un tipo especial de frecuencia de la plaza. La frecuencia de plazas, son una generalización de los cuadrados latinos, que son considerados como difícil de contar. Para contar los cuadrados latinos, el mejor método es Sade del Algoritmo, que podemos usar aquí también. Las principales observaciones son:

Lema: Cualquiera de los dos la frecuencia de los rectángulos que tienen el conjunto múltiple de los símbolos en cada columna puede ser completado en el mismo número de maneras.

Lema: la Frecuencia de los rectángulos formados por permuting las filas y columnas de otra frecuencia rectángulo puede ser completado en el mismo número de maneras.

Los dos anteriores Lemmata proporcionar una relación de equivalencia sobre la frecuencia de rectángulos, que podemos aprovechar para encontrar la respuesta.

En virtud de esta equivalencia, hay $\binom{4}{2}=6$ formas de la creación de la primera fila, todos los cuales son equivalentes a:

Esto puede ser extendido en $\binom{4}{2}=6$ formas, $3$ de los cuales son no equivalentes. Después de esto, podemos continuar con el uso de Sade del Algoritmo, pero es rápido sólo para contar las terminaciones:

• La equivalencia del tamaño de la clase 1:

  

  1 de finalización.

• La equivalencia del tamaño de la clase 4:

  

  2 terminaciones.

• La equivalencia del tamaño de la clase 1:

  

  6 terminaciones.

Así, en total se han $$6 \times (1 \times 1+4 \times 2+1 \times 6)=90$$ plazas.

Answer 3

Esta explicación es un poco más prolijo, pero esperemos que le ayudará con el tipo de intuición que usted necesita para resolver problemas similares.

Así que hay ${{4}\choose{2}} = 6$ maneras de elegir los 2 cuadrados negros en la primera fila. Una vez hemos elegido las dos plazas sabemos que hay dos columnas, en la que debemos escoger exactamente uno más cuadrado negro. Por ejemplo, si elegimos las columnas 2 y 3 de la fila uno, entonces debemos elegir 1 más negro en la columna 2 (en la fila 2, 3, o 4), y 1 para la columna 3. Hay ${{3}\choose{1}} = 3$ maneras de hacer esto para cada columna, por lo $3^2 = 9$ maneras en total para ambas columnas.

Ahora, supongamos que elegimos ambas opciones en la misma fila, entonces habría dos filas vacías de las que sólo tenemos una opción posible para los 4 restantes negros. Por ejemplo, el uso de la notación (fila,columna), nos dicen que el primer elegido (1,2) y (1,4) y, a continuación, (3,2) y (3,4), entonces tenemos (2,1), (2,3), (4,1), y (4,4) a la izquierda como posibles opciones para los 4 restantes negros, dando a ${{4}\choose{4}} = 1$ como se indica. Si nuestras decisiones no están en la misma fila, entonces hay 2 opciones posibles para el 4 negros que quedan como podemos elegir la columna que poner la primera restante negro fuera de los 2 restantes columnas. Por ejemplo, si lo primero que recogen (1,2) y (1,4) y, a continuación, (2,2) y (3,4), ahora es fácil ver que sólo hay 2 conjuntos de posiciones restantes que cumplan los requisitos, es decir,{(2,1),(3,3),(4,1),(4,3)} y (2,3),(3,1),(4,1),(4,3)}.

Hay 6 maneras para el segundo 2 negros para ser dispuestos en 2 columnas, tal que, el no caer en la misma fila. Y como cada uno de estos tiene una manera adicional de la organización de los 4 restantes negros, tenemos un total de $9 + 6 = 15$ formas de elegir el resto de los 6 a los negros una vez que se elige el primer 2. Así, en total se han $6 \times 15 = 90$ formas de organizar los negros.

Answer 4

No he mirado el problema general. Para esto $4\times 4$ problema, no podemos, sin pérdida de generalidad supongamos que los dos cuadrados negros en la fila superior son las dos primeras plazas de la izquierda. Cualquier respuesta que obtenemos entonces puede ser multiplicado por $\binom{4}{2}=6$.

También podemos suponer que la plaza inmediatamente debajo de la parte superior izquierda de la plaza es de color negro. Cualquier respuesta que obtenemos entonces puede ser multiplicado por $\binom{4}{2}(3)$ para obtener el conteo completo.

Ahora no es difícil hacer una lista a mano todas las configuraciones con estas especificaciones cuadrados negros. Uno puede incluso tomar ventaja adicional de simetrías para acortar el conteo, pero en este caso no es necesario.

Comentario: es de suponer que el equipo no puede ser llevado a la sala de examen. Pero nosotros no lo necesitamos. De todos modos, al menos para mí, la depuración del programa tomaría mucho más tiempo que para solucionar el problema.

Answer 5

Etiqueta las columnas $\{1,2,3,4\}$. Deje $S_i$ el conjunto de las etiquetas de las columnas pintadas de negro en la fila $i$. Entonces tenemos dos casos:

• Algunos $S_i=S_j$ $i\neq j$
• No la hay.

El recuento de estos dos casos es esencialmente el problema.

El primer caso es fácil.

El segundo caso se trata de permutaciones de un conjunto de columnas, $x_1,x_2,x_3,x_4$$x_1<x_2$. Entonces tenemos la primera fila es $\{x_1,x_2\}$ y las otras filas son algunos de permutación de $\{x_2,x_3\},\, \{x_3,x_4\},\,$$\{x_4,x_1\}$.