Hay cuadrícula bidimensional con coordenadas enteras. Podemos hacer algunos movimientos por monedas. Si la moneda está en el punto$(x,y)$ y el punto$(x+1,y)$ y$(x,y+1)$ están libres de monedas, podemos retirar moneda de$(x,y)$ y poner dos monedas en$(x,y+1)$ y $(x+1,y)$. Al principio sólo tenemos una moneda en el origen. La pregunta es "¿Podemos liberar monedas cuadradas con coordenadas de la esquina inferior izquierda$(0,0)$ y esquina superior derecha$(2,2)$?"
Respuestas
¿Demasiados anuncios?
Asigne el punto$(x,y)$ the weight$2^{-(x+y)}$. Entonces el peso de$(x,y)$ es igual al peso de$(x+1,y)$ más el peso de$(x,y+1)$, por lo que el peso total de los puntos ocupados nunca cambia. Al principio, con una sola moneda en el origen, el peso total es sólo$1$. Los puntos fuera de ese cuadrado tienen un peso$15/16$, que es menor que$1$, por lo que es imposible.
rmmh
Puntos
4361
Este es un lindo problema.
La visión aquí es buscar un invariante que es preservada por los movimientos permitidos. En este caso, la forma correcta de enfoque es pensar en la moneda original en el origen como tener una masa de 1. La regla para la sustitución de la moneda con los otros dos puede ser pensado como una ruptura de la moneda en la mitad, para ser reemplazado por dos monedas de la mitad de la masa. Ya estamos empezando con una moneda de la misa en el origen, nuestras reglas nos dicen que una moneda en una determinada plaza tendrá un cierto prescrito en masa, independientemente de la secuencia de movimientos que tienes allí. En particular, una plaza que es de $n$ pasos de distancia desde el origen con el apoyo de una masa de $2^{-n}$.
La manera de proceder ahora debe ser clara - determinar la (finito) de la masa de toda la cuadrícula. Entonces, podemos comprobar y ver si una región se puede borrar mediante el cálculo de la masa del complemento - si esta es menor que la masa original de uno, una región no puede ser desactivada.
