Alice y Bob está jugando un juego en un tablero de ajedrez de $n \times n$.
Alice pone monedas en cada plaza; ella puede optar por poner uno de ellos dirige o cola para arriba. A continuación, Bob puede realizar cualquier número de movimientos, donde un movimiento es convertir todas las monedas en una sola fila o columna; su meta es que todas las cabezas de monedas para arriba.
¿Podría Bob siempre consigue hacerlo?
No, no siempre es posible.
Nunca hay cualquier punto de una fila o columna del tirón más de una vez, y no importa el orden de los movimientos.
Así, hay sólo $2^n$ estrategias de tirón, y $2^n$ columna flip estrategias, rendimiento en $(2^n)(2^n) = 2^{2n}$ estrategias posibles.
Pero hay $2^{n^2}$ posiciones posibles, por lo tanto, cuando $n^2 > 2n$ (p. ej., $n \ge 3$), no todas las posiciones se puede llegar desde el la posición de las cabezas de todos. Equivalente, cuando $n^2 > 2n$, no todas las posiciones pueden llegar a la posición de las cabezas de todos.
Otra solución con el uso de matrices:
Denotar por $ A \in \mathbb R ^{n \times n}$ la matriz que representa a la junta directiva, en la que los jefes está representado por $-1$ y colas por $1$. Darle la vuelta a la $i$-ésima columna/fila es el mismo que multiplicar el $i$-ésima columna/fila en la matriz por $-1$. Tal movimiento no cambia el rango de la matriz, ya que es el mismo que multiplicar $A$ con una matriz diagonal $\operatorname{diag}(1, \dots, -1, \dots, 1)$ desde la derecha/izquierda.
La configuración con todos los jefes de seguridad tiene rango $1$. Por lo tanto la única configuraciones que posiblemente pueden ser alcanzadas son aquellos con rango de $1$. Obviamente hay configuraciones con rango de $\geq 2$.
Considerar cualquier plaza de $2\times 2$ en el tablero de ajedrez. Es fácil ver que el número de cabezas en esta plaza es impar, entonces quedará raro después de cualquier Bob. Por lo tanto si $n\geq 2$ y Alice pone exactamente un cabezas de moneda, entonces Bob no podrá levantar todas las cabezas.
Una más elaborada contar el argumento.
Más en general, vamos a echar un $d$-dimensiones checkboard de tamaño $n_1\times\cdots\times n_d$ con la regla de que podemos lanzar monedas en cualquier hyperplane paralelo a una coordenada hyperplane. Inicialmente todas las monedas son de heads up. La natural pregunta es:
Pregunta 1. ¿Cuáles son las posibilidades de que el número de heads-up de monedas después de realizar algunos movimientos?
Pregunta 2. Cuántas configuraciones son posibles?
Tenga en cuenta que, por la inversión de todas las hyperplanes en una cierta dirección, vamos a invertir todo el cuboides, por lo que es equivalente a preguntar ¿cuántas colas que podemos tener.
Las operaciones de recorrido y son involuciones, por lo que podemos suponer no hyperplane se invierte dos veces, y una configuración resultante es entonces determinado por la invertida hyperplanes. (Pero puede ser obtenida en $2^{d-1}$ formas distintas; ver abajo). Decir $a_1,\ldots,a_d$ hyperplanes son invertidos a lo largo de cada una de las direcciones.
El número de heads-up de monedas es entonces $$\sum_{\substack{S\subset\{1,\ldots,d\}\\|S|\text{ even}}}\prod_{k\in S}a_k\prod_{k\notin S}(n_k-a_k)\tag1$$ (el número de monedas volteado 0 veces, dos veces, cuatro veces, etc...)
Esto es igual a 1 $$\frac12\left(N+\prod(n_k-2a_k)\right)\tag2$$
donde $N=n_1\cdots n_d$.
Llegamos a la conclusión de que:
$H$ jefes pueden ser obtenidos iff $|2H-N|$ puede ser escrito como $b_1\cdots b_d$ con cada una de las $b_k\in\{0,\ldots,n_k\}$ de la misma paridad como $n_k$
En particular: 2
Si $n_1=\ldots=n_d=n$ es incluso, a continuación,$2^{d-1}\mid H$.
Para responder a la segunda pregunta, tenga en cuenta que estamos considerando una acción de $(\mathbb Z/2)^{n_1+\cdots+n_d}$ en las monedas, y de la órbita de cada configuración es $2^{n_1+\cdots+n_d}$ dividido por el estabilizador de (por ejemplo) el inicial.
El orden del estabilizador es la suma de los $\prod\binom{n_k}{a_k}$ sobre las soluciones a $$N=\prod(n_k-2a_k),\qquad a_k\in[0,n_k]$$
Teniendo en cuenta el valor absoluto se entera de que un número de $a_k$'s es igual a $n_k$ y un número impar es igual a $0$. Los coeficientes binomiales son todos los $1$, y llegamos $2^{d-1}$ para el fin del estabilizador:
Hay $2^{n_1+\cdots+n_d-d+1}$ configuraciones posibles, de $2^{n_1\cdots n_d}$ en total. 3
Una rápida inducción muestra que $n_1\cdots n_d-(n_1+\cdots+n_d-d+1)\geq0$ con igualdad de iff todos, pero en más de una $n_k=1$. Así, excepto para el $1\times\cdots\times1\times n$ cuboides, hay siempre unreacheable configuraciones.
1Prueba 1: Cada plazo $\prod_{k\notin T}n_k\prod_{k\in T}a_k$ aparece en $(1)$ con un coeficiente de $(-1)^{|T\setminus S|}$ por cada $S\subset T$ $|S|$ incluso. Por esto, esto da $2^{d-|T|-1}$$T\neq\varnothing$, con lo que obtenemos la expansión de $(2)$ (véase también la segunda prueba).
Prueba 2: $$\sum_{\substack{S\subset\{1,\ldots,d\}\\|S|\text{ even}}}\prod_{k\in S}a_k\prod_{k\notin S}(n_k-a_k)=\sum_{\substack{S\subset\{1,\ldots,d\}\\|S|+d\text{ even}}}\prod_{k\notin S}a_k\prod_{k\in S}(n_k-a_k)$$
y
$$\begin{align*}\sum_{\substack{S\subset\{1,\ldots,d\}\\|S|+d\text{ even}}}\prod_{k\notin S}a_k\prod_{k\in S}(n_k-2a_k+a_k) &=\sum_{\substack{S\subset\{1,\ldots,d\}\\|S|+d\text{ even}}}\sum_{T\subset S}\prod_{k\notin S}a_k\prod_{k\in T}(n_k-2a_k)\prod_{k\in S\setminus T}a_k\\ &=\sum_{T\subset\{1,\ldots,d\}}\prod_{k\in T}(n_k-2a_k)\prod_{k\notin T}a_k\cdot\#\{S: T\subset S\subset\{1,\ldots,d\}, |S|+d\text{ even}\}\\ &=\prod(n_k-2a_k)+\sum_{\substack{T\subset\{1,\ldots,d\}\\|T|<d}}\prod_{k\in T}(n_k-2a_k)\prod_{k\notin T}a_k\cdot 2^{d-|T|-1}\\ &=\frac12\prod(n_k-2a_k)+N/2\end{align*}$$
2 creo directa combinatoria pruebas de $2^k\mid H$ todos los $k<d$ son posibles, pero se vuelven menos elegante para $k>1$.
3 de Nuevo, estoy seguro de que un efecto directo de la combinatoria prueba (tengo uno para $d=3$).
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
