Se tiene una hoja cuadrada de [math]9 \times 9 cuadriculada en cuadritos de [math]1 \times 1. Se corta la hoja con el objetivo de dividirla en cuadritos de [math]1 \times 1.
Cada corte debe ser recto y seguir una línea de la cuadrícula.
Después de efectuar cada corte, está permitido reacomodar convenientemente los pedazos en una pila de modo que en el corte siguiente se divida a varios pedazos simultáneamente (en cada pedazo el corte debe ser recto y seguir la línea de la cuadrícula). Está prohibido plegar el papel.
¿Cuál es la menor cantidad de cortes que hacen falta para lograr el objetivo?
(Para el número hallado, indicar cuales son los cortes y explicar por qué es imposible lograr el objetivo con menos cortes.)
Guía de [math]\LaTeX: sirve para escribir ecuaciones como [math]\frac{11}{8}+ x \lfloor \pi \rfloor = 1
Notemos que el primer corte divide al tablero en [math]2^1 partes, si estas se superponen en el siguiente corte, en [math]2^2 y así sucesivamente.
Consideremos un subtablero de [math]8\times8. Como [math]2^6=64, se puede dividir mediante [math]6 cortes, si siempre se superponen las partes cortadas. Nótese que hay [math]3 cortes verticales y [math]3 horizontales. Además, en todo momento se superponen partes iguales, por lo tanto no sobra espacio y cualquier tablero más grande tendrá que dividirse con más cortes.
Un tablero de [math]9\times9 tiene una fila y una columna más. Por lo visto anteriormente, se necesitará un corte vertical más y uno horizontal más: en total, [math]8 cortes. El ejemplo con [math]8 es fácil de encontrar.
La demostración de que para dividir un cuadrado de [math]8\times 8 necesitás [math]6 cortes está bien.
Lo que no está bien es decir que se necesitan dos cortes más para el de [math]9\times 9. Creo que con este argumento podés probar que se necesitan al menos [math]7 cortes (porque [math]2^6<81). No me queda claro que se pueda decir así nomás que hacen falta [math]8 cortes (por ahí en algún momento rotás uno de los pedazos y se puede hacer con un corte menos).
No pensé el problema, así que tampoco estoy seguro de si la respuesta es [math]7 o es [math]8.
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)
Vamos a decir que un rectángulo de [math]a\times b es más difícil que un rectángulo de [math]c\times d si se pueden ubicar de modo que el primero contenga al segundo. En otras palabras, si [math](a\geq c \text{ y } b\geq d) \text{ o } (a\geq d \text{ y } b\geq c).
La idea clave es que si un rectángulo [math]R se puede dividir con [math]n cortes y [math]R es más difícil que [math]R', entonces [math]R' también se puede dividir con [math]n cortes. Vamos a usar esto varias veces.
Supongamos que el rectángulo de [math]9\times 9 se puede dividir con [math]7 cortes. Vamos a llegar a un absurdo.
Al hacer el primer corte, alguno de los dos pedazos que quedan es más difícil que un rectángulo de [math]9\times 5. Entonces el rectángulo de [math]9\times 5 se puede dividir con los [math]6 cortes restantes.
Ahora quedan [math]6 cortes para dividir el rectángulo de [math]9\times 5. En el primer corte queda un pedazo más difícil que un rectángulo de [math]9\times 3 o un pedazo más difícil que un rectángulo de [math]5\times 5. Por lo tanto alguno de los dos se puede dividir con los [math]5 cortes restantes [lo que vamos a hacer es mostrar que no se puede hacer esto en ninguno de los dos casos].
Seguimos haciendo el mismo argumento en cada caso:
Si el rectángulo de [math]9\times 3 se puede dividir con [math]5 cortes, en alguno de estos dos casos tiene que alcanzar con [math]4 cortes: para [math]9\times 2 o para [math]5\times 3.
Si el rectángulo de [math]5\times 5 se puede dividir con [math]5 cortes, entonces el rectángulo de [math]5\times 3 se puede dividir con [math]4 cortes.
Luego si vemos que ni el rectángulo de [math]9\times 2 ni el de [math]5\times 3 se pueden dividir con [math]4 cortes estamos.
El caso de [math]9\times 2 lo podemos descartar directamente, con [math]4 cortes se pueden lograr a lo sumo [math]2^4=16<18=9\times 2 pedazos.
En el caso [math]5\times 3 seguimos haciendo lo mismo: alguno de estos se tiene que poder dividir con [math]3 cortes: el de [math]3\times 3 o el de [math]5\times 2.
Pero [math]2^3=8<3\times 3 y [math]2^3=8<5\times 2 así que en ninguno de los dos casos se puede.
Primer corte:Cortar el cuadrado de 9 x 9 en un rectángulo de 9 x 3 y otro de 9 x 6.
Segundo corte:Ponerlos en una pila y cortar el de 9 x 6 en uno de de 6 x 6 y otro de 3 x 6, cortar el de 9 x 3 en uno de 6 x 3 y otro de 3 x 3.
Tercer corte:Poner en una pila los de 6 x 3 y el de 6 x 6 y cortar los de 6 x 3 en rectángulos de 3 x 3 y al de 6 x 6 en uno de 3 x 6.
Cuarto corte:Ponerlos en una pila y cortar los de 3 x 3 en uno de 2 x 3 y otro de 1 x 3 y al de 3 x 6 en uno de 3 x 2 y otro de 3 x 4.
Quinto corte:Ponerlos en una pila y cortar los de 3 x 2 en uno de 2 x 2 y otro de 2 x 1, cortar los de 3 x 1 en uno de 2 x 1 y otro de 1 x 1, cortar al de 3 x 4 en dos de 3 x 2
Sexto corte:Ponerlos en una pila y cortar los de de 2 x 2 en dos de 2 x 1, cortar los de 2 x 1 en dos de 1 x 1, cortar los de 3 x 2 en uno de 2 x 1 y otro de 2 x 2.
Séptimo corte:Ponerlos en una pila y cortar los de 2 x 1 en dos de 1 x 1 y los de 2 x 2 en dos de 2 x 1.
Octavo corte:Ponerlos en una pila y cortar los de 2 x 1 en dos de 1 x 1.
Y de esta manera se cumple que el mínimo de cortes necesarios para dividir el cuadrado de 9 x 9 en 81 cuadrados de 1 x 1 es 8.
