Menor número de No negativo en una matriz

Question

Hay una pregunta que me he encontrado que dijo a llenar un $N \times N$ matriz de tal manera que cada entrada en la matriz es el menor número de no negativo que no aparece encima de la entrada o a su izquierda. Que es para $N = 6$ la matriz se parece a esto:

$$\begin{array}{} 0&1&2&3&4&5\\ 1&0&3&2&5&4\\ 2&3&0&1&6&7\\ 3&2&1&0&7&6\\ 4&5&6&7&0&1\\ 5&4&7&6&1&0 \end{array}$$

Me pidió que encontrar una función tal que dado fila y columna I se puede calcular el valor en ese punto yo.e

$$f(\text{row}, \text{column}) = \text{Matrix}[\text{row}][\text{column}]$$

Yo estaba mirando Nimbers y encontrar la matriz en exactamente similar a esto. Hubo también da una fórmula para calcular calcular la Matriz[fila][columna] que fue fila XOR columna (XOR es bit a bit exor).

Sin embargo, yo era capaz de obtener la respuesta que yo todavía soy incapaz de cómo llegar a la solución, es decir, la prueba de que cada entrada en la matriz es el menor número de no negativo que no aparece por encima de la entrada o a su izquierda es igual a la fila XOR columna.

Answer 1

Denotar por $a(m,n)$ la entrada en la fila $m$ columna $n$ de la matriz. Por definición

$$a(m,n)=\operatorname{mex}\big(\{a(k,n):k<m\}\cup\{a(m,k):k<n\}\big)\;,\tag{1}$$

donde $\operatorname{mex}(A)$ es el menor entero no negativo, no en $A$. El problema es demostrar que cuando todas las cifras están expresadas en binario, $a(m,n)=m\oplus n$, el bit a bit exclusivo O de $m$$n$. Lo haremos por inducción en $m+n$. Es cierto cuando $m+n=0$: $a(0,0)=0=0\oplus 0$. Supongamos ahora vamos a $m,n\in\mathbb{N}$, y supongamos que es cierto para todos los $m',n'\in\mathbb{N}$$m'+n'<m+n$; vamos a demostrar que es cierto para $m$$n$.

Deje $s=m\oplus n$. Para mostrar que $s=a(m,n)$ como se define por $(1)$, tengo que demostrar dos cosas:

1. si $0\le t<s$, $t\in\{a(k,n):k<m\}\cup\{a(m,k):k<n\}$; y
2. $s\notin\{a(k,n):k<m\}\cup\{a(m,k):k<n\}$.

Mostrar (1), supongamos que $0\le t<s$, vamos a $d=t\oplus s$, y deje $k$ el número de bits de $d$, por lo que el $2^{k-1}\le d<2^k$. Es decir, $d$ $1$ $k$- ésima posición contando desde la derecha. Desde $t<s$, esto implica que $t$ $0$ $k$- ésima posición, y $s$ $1$ no. Desde $s=m\oplus n$, exactamente uno de $m$ $n$ debe tener un $1$ $k$- ésima posición; sin pérdida de generalidad supongamos que $m$ $1$ $k$- ésima posición. A continuación, $d\oplus m$ $0$ $k$- ésima posición y es idéntica a la de $m$ en posiciones a la izquierda de la $k$-ésima posición, por lo $d\oplus m<m$. Deje $k=d\oplus m$; a continuación,$$k\oplus n=d\oplus m\oplus n=d\oplus s=t\oplus s\oplus s=t\;.$$ Moreover, $ k<m$, so $k+n<m+n$, and therefore $t=k\oplus n=a(k,n)$ por la hipótesis de inducción. Esto completa la prueba de (1).

Mostrar (2), se puede suponer que, por el contrario, que el $s\in\{a(k,n):k<m\}\cup\{a(m,k):k<n\}$. Sin pérdida de generalidad podemos suponer que la $s\in\{a(k,n):k<m\}$. Deje $k<n$ ser tal que $s=a(k,n)$. Claramente $k+n<m+n$, de modo que por la hipótesis de inducción tenemos $$k\oplus n=a(k,n)=s=m\oplus n\;,$$ and therefore $$k=k\oplus n\oplus n=m\oplus n\oplus n=m\;,$$ contradicting the choice of $k$. Thus, (2) also holds, and $m\oplus n=a(m,n)$.

Answer 2

Es la función XOR, y se puede demostrar por inducción sobre la longitud de bits. Para $0\leq x,y<2^n$ con el binario expansiones $$ x=\sum_{i=0}^{n-1} x_i 2^i, \quad y=\sum_{i=0}^{n-1} y_i 2^i \quad \text{para} \quad x_i, y_i \in \{0,1\}, \quad \text{y} \quad x,y \in I_n=\{0,1,\dots,2^n-1\}, $$ podemos empezar por asumir de forma inductiva que $$ f(x,y) = XOR(x,y) \equiv \sum_{i=0}^{n-1} x_i y_i 2^i $$ y observar (y también como parte de nuestra hipótesis inductiva) que cada fila y columna (donde uno de $x$ o $y$ es fijo, pero el otro varía libremente sobre $I_n$) contiene precisamente los valores de $I_n$ (una vez cada uno).

Ahora, para el paso inductivo, dejamos $x_n,y_n\in\{0,1\}$ ser arbitraria, y nótese en primer lugar que el bloque de base $(x_i,y_i)=(0,0)$ es nuestra hipótesis inductiva. Siguiente, tenga en cuenta que para $(x_i,y_i)=(0,1)$$(x_i,y_i)=(1,0)$, todos los valores en $I_n$ ya están tomadas y así la minimality regla de asignar valores a $f$ comenzando con $2^n$ en lugar de $0$, el llenado de estos bloques con los valores $I_{n+1} \setminus I_n = \{2^n,2^n+1,\dots,2^{n+1}-1\}$. Además, estos los valores serán asignados dentro de cada bloque en el mismo orden en que fueron en el bloque de base. Por último, el bloque de $(x_i,y_i)=(1,1)$ va a coincidir con el bloque de base, desde que sus predecesores (los dos no base, inductivo bloques ya se considera) utiliza los valores de$I_{n+1} \setminus I_n$, pero dejó a los de $I_n$ vacantes. Por lo tanto, la minimality criterio es aditivo: $$ f(2^i x_i + x, 2^i y_i + y) = 2^i XOR(x_i,y_i) + f(x,y) = 2^i x_i y_i + f(x,y) $$ lo que demuestra el paso inductivo.

La idea clave que hace de esta prueba es que los bloques de $(x,y)$ para $0 \leq x,y < N$ "completa" (que contiene cada valor de $0$ $N-1$en cada fila y columna) iff $N=2^n$ es una potencia de dos.

Answer 3

Me gusta mucho esta pregunta. Yo lo vi en un sitio web o menos un año atrás, cerró la página para que no me vea la respuesta, y luego nunca lo encontró de nuevo. Lo resuelto por demostrar por inducción que $$ f(4i+r, 4j+s) = f(r,s)+4f(i,j)$$ --- esta relación es evidente si se dibuja suficiente de la matriz. Déjame saber si a usted le gustan los detalles. Una vez que tienen esta relación, se puede aplicar varias veces para obtener

$$f(\sum a_i 4^i, \sum b_i 4^i) = \sum h(a_i,b_i) 4^i$$

donde $h$ es la función determinada por el primer 4x4 de bloque de la matriz. Esto explica por qué es posible pensar de f como un "bit a bit" de la operación.

Answer 4

Todas estas pruebas se basan en la observación de que esta pregunta está relacionada con el operador XOR bit a bit (después de un par de ejemplos, esto es muy fácil de ver). Sin embargo, todavía no puedo ver la interfaz de conexión entre el problema original y el Nimbers. ¿Alguien tiene una información clara sobre esto?

Answer 5

Digamos que usted ha seleccionado una fila (es decir $A$ representado el uso de n-bits). Ahora, para todos los $2^n$ columnas (es decir $B$) que usted elija, usted recibirá diferentes cadenas de bits, de ahí los diferentes números.

Para un particular $A$, $A\oplus B$ es diferente para los distintos valores de $B$. Es por eso que usted recibe diferentes números y dentro del rango de n-bits. El mismo no es cierto para Y o U operadores.

A  B  A xor B    A and B   A or B
0  0     0          0         0
0  1     1          0         1
1  0     1          0         1
1  1     0          1         1

Aquí os aviso de que si se toman a nivel de bit Y, luego de una fila en particular que usted puede obtener los mismos valores para las diferentes columnas. Por ejemplo, para $5^{th}$ fila ie $(101)_2$ tendrá un valor de 5 $(101)_2$ $5^{th}(101)_2$ $7^{th}(111)_2$ columna.

Así, [5][5] = A[5][7] = 5 que no es necesario. Este problema viene porque de 0 en el bitstring.

Del mismo modo O, esta repetición vendrá porque de 1 en el bitstring.

[5][5] = A[5][4] = A[5][1] = A[5][0] = 5

Así, ahora se puede ver por qué la operación XOR bit a bit se utiliza.

Pero no, con el menor valor posible. En la matriz, se puede ver que el 4 y 5 son las que faltan en $3^{rd}$ $4^{th}$ filas; y el 2 y 3$5^{th}$ $6^{th}$ filas. Esto es porque usted tiene 6 filas y columnas para las que se necesitan 3 bits que puede acomodar a 8 valores.

\begin{array}{} 0&1&2&3&4&5\\ 5&0&1&2&3&4\\ 4&5&0&1&2&3\\ 3&4&5&0&1&2\\ 2&3&4&5&0&1\\1&2&3&4&5&0 \end{array}

Para obtener los valores mínimos, usted puede solo cambian los valores, mientras que entrar en la siguiente fila.