¿Rompecabezas de Microsoft?

¡El algoritmo matricial se puede implementar de forma sencilla utilizando matrices de ordenadores! ! !

La solución perfecta a 12 bolas que pesan 3 veces para encontrar bolas malas

Detalles del antiguo rompecabezas:

Hay 12 bolas con las mismas características, solo que uno de ellos Si el peso es anormal, use una balanza sin pesas para pesarla tres veces y encontrar la bola con peso anormal.

Los métodos más comunes en Internet son los métodos lógicos, y también existen algunos de los llamados árboles estratégicos dibujados en gráficos y programas de algoritmos basados ​​en ellos. Aquí tengo 13 respuestas diferentes. proponer una nueva Solución matemática completa:

1. En primer lugar, se propone el modelo matemático de pesaje:

Considerando un pesaje como una expresión algebraica lineal, el mismo problema se puede describir como una solución de ecuación matricial simple Pregunta. ¿Cómo expresar un pesaje como una fórmula algebraica?

1), simplifique la descripción del peso (estado) de la pelota: el peso de la pelota normal se establece en 0, y la bola anormal es más pesada que la bola normal es 1 o la liviana es -1. Cuando se desconoce el peso de la bola anormal, se representa por Izquierda y derecha (método de colocación) ----- Colocar una bola. de un cierto número a la izquierda se establece en 1, el de la derecha se establece en -1 y, si no se coloca, se establece en 0. Utilice el vector de fila i para representar el estado izquierdo y derecho de todas las bolas pesadas en un determinado tiempo

3), describa los resultados del pesaje:

Se puede determinar una fórmula de pesaje a partir de 1) y 2)

∑ Peso de cada bola * método = Resultados del pesaje de la balanza.--------(1) Fórmula

Si usamos los vectores jey i para representar el estado del peso de la pelota y la ubicación izquierda y derecha de la pelota respectivamente (j es un vector de fila, i es un vector de columna), para la fórmula (1), se puede reescribir como

j*i=a (la constante a es el resultado de un solo pesaje) -- ----------- (2) Fórmula

Por ejemplo, hay ***6 bolitas pequeñas, del 1 al 6, entre las cuales la 4 es la más pesada. Tome el No. 3 y el No. 5 y colóquelos a la izquierda, y el No. 1 y el No. 4 a la derecha para pesar, la fórmula es:

(-1)*0 0*0. 1*0 (-1)*1 1*0 0*0=-1,

Desde -1 El significado de se puede conocer porque indica que el lado izquierdo del resultado es más claro

También puede obtener 0 para indicar equilibrio y 1 para indicar que el lado izquierdo es más pesado

4), la ecuación se usa para describir el proceso de pesaje. También hay una condición importante. que hay que sumar: significa que el número de 1 colocado a la izquierda y el -1 colocado a la derecha son iguales, es decir,

∑La ubicación de cada bola = 0---- ------- ---------------Ecuación (3)

Esto resuelve el problema de expresión matemática de pesaje

For. 12 bolas pequeñas, 3 Los pesajes están representados por vectores de fila de 12 dimensiones j1, j2 y j3 respectivamente. j1j2j3 constituye una matriz de pesaje de 3 × 12 J para una determinada situación posible i, la columna tridimensional correspondiente compuesta por los tres; pesando resultados Vector b, obtenemos

J*i=b

Modelado matemático del problema de las dos bolas

El equivalente del problema:

Supongamos que J es una matriz de 3×12 tal que la suma de los elementos de cada fila es 0. i es un vector de columna de 12 dimensiones, uno de los elementos de i es 1 o -1 y los demás elementos son todos 0, es decir, i es cualquier columna de la matriz de bloques de 12 × 24 M = (E, -E ). La matriz C de 3 × 27 está compuesta por 27 vectores columna tridimensionales diferentes, y sus elementos solo pueden ser 1, 0, -1.

Se puede ver por el significado del problema que b=. J* i debe ser un vector columna de C.

Para cualquier i, b determinado por J*i=b son diferentes entre sí

Es decir,

J*M=J*(E,-E)=(B). , -B)=X ----- (Supongamos que X es una matriz de 3×24)

Porque se puede ver que las tres columnas eliminadas de C son (0, 0, 0) y 1 pares de vectores de columna mutuamente pares Aquí, (1, 1, 1) y (-1, -1, -1) se eliminan

De la fórmula anterior, obtenemos J*E=B. y deducir J=B, X=(J,-J). Por lo tanto, (0, 0, 0), (1, 1, 1), (-1, -1, -1) se eliminan de los 27 vectores columna tridimensionales y luego se dividen en dos grupos de pares mutuos (correspondientes a la inversión)

[ 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]

[ 0, 1, 1, 1, 0 , 0, 0, 1, 1,-1,-1,-1]

[ 1, 0, 1,-1, 0, 1,-1, 0,-1; , 0, 1, -1].

[ 0, 0, 0, 0, -1, -1, -1, -1, -1, -1, -1, -1];

[ 0, -1, -1, -1, 0, 0, 0, -1, -1, 1, 1, 1]; , -1 , 1, 0, -1, 1, 0, 1, 0, -1, 1

Ahora, intercambiando las 2 columnas hacia arriba y hacia abajo, se obtiene la suma de los elementos de cada fila. es 0! ! Puede obtener J. Mi método es intercambiar hacia arriba y hacia abajo a intervalos de derecha a izquierda, y luego intercambiar las filas 2 y 3 hacia arriba y hacia abajo, de modo que la suma de todas las filas sea 0. Obtener

Matriz de pesaje J=

[0, 0, 0, 0, 1, -1, 1, -1, 1, -1, 1, -1] <; /p>

[0, 1,-1,-1, 0, 0, 0,-1, 1, 1,-1, 1]

[1, 0,- 1]; , 1, 0, -1, -1, 0, -1, 0, 1, 1

El método correspondiente para colocar ambos lados de tres pesas:

5 en. la izquierda, 7, 9, 11: 6, 8, 10, 12 a la derecha

2, 9, 10, 12 a la izquierda: 3, 4, 8, 11 a la derecha; /p>

1 a la izquierda, 4, 11, 12: 3, 6, 7, 9 a la derecha.

********** ********** ************ **********

Bola No. 1, y pesada - plana, plana, izquierda Bola No. 1, y ligera - plana, plana, derecha

Bola No. 2, pesada - plana, izquierda, La bola No. 2 es liviana: plana, derecha, plana

La bola No. 3 es pesada: plana, derecha, derecha La bola No. 3 es liviana: plana, izquierda, izquierda

Bola No. 4, pesada - plana, derecha, izquierda. Bola No. 4, plana, izquierda, derecha.

Bola No. 5, pesada - izquierda, plana, bola No. 5. , ligero - plano, izquierdo, derecho Derecha, plano, plano

Bola nº 6, y pesado - derecha, plano, derecha bola nº 6, y ligero - izquierda, plano, izquierda

Bola N° 7 y pesada - Bola N° 7, izquierda, plana, derecha y ligera - derecha, plana, izquierda

Bola N° 8, pesada - derecha, derecha, plana Bola No. 8, y ligera - izquierda, izquierda, plana

Bola No. 9, pesada - izquierda, izquierda, derecha No. 9, ligera - derecha, derecha, izquierda

Bola No. 10, pesada - derecha, izquierda, plana No. 10 Bola No. 11, ligera-izquierda, derecha, plana

Bola No. 11, pesada-izquierda, derecha, izquierda No. 11 bolas, ligera-derecha, izquierda, plana

Bola No. 12 y pesada - derecha, izquierda, izquierda Bola No. 12 y ligera - izquierda, derecha, derecha

3·Extensión de la pregunta

1. El problema de pesar 13 bolas 3 veces:

Los tres vectores eliminados de la solución anterior son (0, 0, 0) (1, 1, 1) (-1, -1, -1) Para poder determinar las 13 bolas se debe sumar un par de vectores duales If (1, 1, 1) (-1, -1, -1). ) se agrega, luego

[ 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

[ 0, 1, 1, 1, 0, 0, 0, 1, 1, -1, -1, -1, 1]

[ 1, 0, 1, -1, 0, 1, - 1, 0, -1, 0, 1, -1, 1

[ 0, 0, 0, 0, -1, -1, -1, -1, -1, -1]. , -1, -1, -1];

[ 0, -1, -1, -1, 0, 0, 0, -1, -1, 1, 1, 1, -1 ];

[-1, 0, -1, 1, 0 , -1, 1, 0, 1, 0, -1, 1, -1]. Los números distintos de 0 en la primera fila son números impares y no importa cómo los ajuste, no puede hacer que la suma de las filas sea 0. Por lo tanto, la fila agregada solo puede ser un vector de columna dual (0, 0, 0). El resultado es que cuando una bola diferente es la decimotercera bola, se puede juzgar pero no se puede verificar la gravedad. También se puede ver que el problema de pesar 13 bolas 3 veces y el problema de pesar 12 bolas 3 veces son sólo ligeramente diferentes. Por ejemplo, el problema de 12 bolas divide las bolas en 3 grupos de 4 pesajes, mientras que el de 13 bolas. El problema de la pelota divide las pelotas en 4 grupos (4, 4, 4, 1), la decimotercera pelota está en un grupo separado.

Se pesan 2, (3^N-3)/2 bolas N veces para conocer las diferentes bolas y determinar la solución general:

El primer paso es dar 3 bolas Una matriz de pesaje J2 pesó dos veces

[0, 1,-1]

[-1, 0, 1]. Kn=(3^N-3)/2 pesaje esférico N veces sea la matriz Jn de N filas × Kn columnas, y ponga (3^N/3-3)/2 pesaje esférico N- La matriz de pesaje de primer orden Jlt; n-1gt; abreviado como J. Entonces sean los vectores columna N-dimensionales Xn, Yn, Zn (0, 1, 1,..., 1), (1, 0, 0,..., 0), (1, -1, -1, ..., -1).

Paso 1 del tercer paso, agregue 1 fila cada una a la matriz J de N-1 filas. formando una nueva matriz J'.

Paso 2 del tercer paso, sobre la matriz J de N-1 filas, agrega el vector fila t=(1, 1,..., 1, -1). , -1, ..., -1), se convierte en una nueva matriz J". La dimensión (longitud) de t es la misma que el número de columnas de J. Los primeros elementos de t son todos 1, y los últimos elementos son - 1; cuando la longitud de t es un número par, el número 1 es igual al número -1; cuando la longitud de t es un número impar, el número 1 es uno menos que el número -1; >

Paso 3 de 3, encima de la matriz-J de N-1 filas, agregue el vector de fila t=(1, 1,...,1,-1,-1,...,- 1) para formar una nueva matriz J"'.

El cuarto paso, cuando el número de columnas de J, es decir, la longitud de t, es un número impar, use una matriz de bloques para representar la matriz Jn = (J', J", J"', Xn, Yn, Zn Cuando el número de columnas de J, es decir, la longitud de t, es un número par, utilice una matriz de bloques para representar la matriz); Jn = (J', J", J"', Xn, -Yn, Zn);

Este método puede encontrar rápidamente un J3 como

[0, 0, 0, 1, -1, -1, 1, -1, -1, 0, 1, 1]

[0, 1,-1, 0, 1,-1, 0,-1, 1, 1, 0,-1];

[-1, 0, 1, -1, 0, 1, 1, 0, -1, 1, 0, -1]. >

También puedes continuar sustituyendo para encontrar las matrices de pesaje de J4 y J5.

3. Promoción principal de la Categoría 2:

Categoría 1, hay (3^n-3)/2 bolas, una de las cuales es una bola diferente, pesada n veces con una balanza, encuentra la pelota y determina si es más liviana o más pesada.

Tipo 2, hay n bolas, mezcladas con m bolas de otro tamaño, pero no se sabe si las diferentes bolas son más pesadas o más ligeras que las bolas estándar. Pésalas k veces para separarlas y determinar. el peso? Obviamente, la promoción anterior divide las bolas en dos tipos y luego se generaliza al método de encontrar la escala cuando las bolas se dividen en n tipos.

Para el primer tipo de promoción, la solución general de ladder push se ha proporcionado anteriormente. En cuanto al segundo tipo de promoción, solo tenemos una comprensión preliminar de algunas situaciones simples cuando m = 2, como encontrar 2 bolas diferentes idénticas con 5 escalas de bolas 3 veces y encontrar 2 bolas diferentes con 9 escalas de bolas 4 veces. Las mismas esferas alienígenas se han resuelto mediante el método de lógica de inferencia, pero el método matricial aún no tiene idea. El problema de encontrar 2 esferas alienígenas idénticas 5 veces usando 16 esferas se ha vuelto muy engorroso con los métodos lógicos ordinarios. una solución. Espero que algunos expertos puedan continuar usando métodos matriciales para encontrar la respuesta. Es mejor obtener la fórmula recursiva cuando m = 2.

J4=

[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1 , 1, 1, 1 , 1,-1,-1,-1,-1,-1,-1,1, 1, 1, 1, 1, 1,-1,-1,-1,-1 , -1, -1 , 0, -1, 1];

[ 0, 0, 0, 1, -1, -1, 1, -1, -1, 0, 1, 1 , 0, 0, 0 , 1, -1, -1, 1, -1, -1, 0, 1, 1, 0, 0, 0, -1, 1, 1, -1, 1, 1, 0, -1, -1 , 1, 0, -1];

[ 0, 1, -1, 0, 1, -1, 0, -1, 1, 1, 0, -1 , 0,1,- 1, 0, 1,-1, 0,-1, 1, 1, 0,-1,0,-1, 1, 0,-1, 1, 0, 1,-1, -1, 0, 1 , 1, 0, -1];

[-1, 0, 1, -1, 0, 1, 1, 0, -1, 1, 0, -1, -1, 0, 1, -1, 0, 1, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0, -1, -1, 0, 1, -1, 0, 1 , 1, 0, -1].