Imaginemos que está coloreado como un ajedrez: hay que quitar al menos una cerilla de cada cuadrado blanco para deshacer los 8 cuadrados blancos; del mismo modo hay que quitar al menos una de cada cuadrado negro. Si quito 8 cerillas de las uniones de cuadrados blancos y negros puedo romper los 16 cuadrados individuales. Además podría romper los cuadrados de 4 y 9 cuadrados individuales, pero no puedo romper el cuadrado de 16 porque ninguna de sus cerillas está en la unión de un cuadro blanco y uno negro.
Por tanto necesito como mínimo quitar 9 cerillas, 8 entre cuadrados blancos y negros diferentes y la novena en el borde.
@XXL2: me gustaria ver tu solucion en 9, ya que creo que se puede demostrar que es imposible en menos de 10.
@Mmonchi: estoy de acuerdo que tu razonamiento implica que no se puede hacer en menos de 9. Pero no das demostracion de que de hecho se puede hacer en 9. Me parece que se puede continuar tu razonamiento para probar que no es posible en 9 tampoco:
Si lo queremos hacer en 9, gracias a tu explicacion, sabemos que debemos de elegir 8 cerillos que son «fronteras» entre un cuadrado blanco y un negro, mas un cerillo en el borde exterior. Eligir las 8 fronteras corresponde a hacer una decomposicion (o teselacion) del cuadrado en 8 dominos de tamano 2*1.
Si queremos lograrlo en 9, tenemos que intentar de formar muy pocos cuadrados de 2*2 con nuestros dominos: podemos tener uno (solo) tocando el borde exterior (luego lo eliminariamos con el 9o cerillo), no podemos formar otro (si es el caso necesitariamos otro cerillo), y no podemos formar uno que no toca el borde exterior (misma razon).
Jugando un poco con las posibilidades, es rapido convencerse de que esto es imposible. Casi todas la teselaciones que se pueden hacer con dominos 2*1 forman al menos 2 cuadrados de tamano 2*2. Si queremos formar solo uno, se forma en el centro, o sea no toca el borde.
Finalmente, en 10 si, se puede. Por ejemplo Show ▼
fila por fila, quito solo cerillos verticales: los cerillos 2,4 en la primera fila, luego los 1,3,5 en la segunda fila, luego 2,4, luego 1,3,5.
Espero no haber hecho un error en la demostracion! 😉
.
Gracias @Mmonchi! El error en mi razonamiento es cuando dije que
«Eligir las 8 fronteras corresponde a hacer una decomposicion (o teselacion) del cuadrado en 8 dominos de tamano 2*1»
Eso es falso, como lo muestra claramente tu solucion.
Yo lo consigo con Show ▼
Es imposible hacerlo con menos de 9.
Imaginemos que está coloreado como un ajedrez: hay que quitar al menos una cerilla de cada cuadrado blanco para deshacer los 8 cuadrados blancos; del mismo modo hay que quitar al menos una de cada cuadrado negro. Si quito 8 cerillas de las uniones de cuadrados blancos y negros puedo romper los 16 cuadrados individuales. Además podría romper los cuadrados de 4 y 9 cuadrados individuales, pero no puedo romper el cuadrado de 16 porque ninguna de sus cerillas está en la unión de un cuadro blanco y uno negro.
Por tanto necesito como mínimo quitar 9 cerillas, 8 entre cuadrados blancos y negros diferentes y la novena en el borde.
@XXL2: me gustaria ver tu solucion en 9, ya que creo que se puede demostrar que es imposible en menos de 10.
@Mmonchi: estoy de acuerdo que tu razonamiento implica que no se puede hacer en menos de 9. Pero no das demostracion de que de hecho se puede hacer en 9. Me parece que se puede continuar tu razonamiento para probar que no es posible en 9 tampoco:
Finalmente, en 10 si, se puede. Por ejemplo
Show ▼
Espero no haber hecho un error en la demostracion! 😉
.
Gracias @Mmonchi! El error en mi razonamiento es cuando dije que
«Eligir las 8 fronteras corresponde a hacer una decomposicion (o teselacion) del cuadrado en 8 dominos de tamano 2*1»
Eso es falso, como lo muestra claramente tu solucion.