Un $n\times(n+3)$ rejilla rectangular ( $n>10$ ) se corta en algunos cuadrados, con todos los cortes a lo largo de las líneas de la cuadrícula. ¿Cuál es el menor número posible de cuadrados con longitud de lado impar?
[Fuente: Problema de competencia en Rusia]
Agradecimiento a Steve Kas por sus dibujos
Parece que siempre se puede hacer con 2 o 4 cuadrados (Impares)
Creo que necesitas 4 cuadrados "impar" si n o n+3 es divisible por 4, de lo contrario son 2.
En primer lugar, puede rellenar los rectángulos pares con cuadrados pares solamente.
Si n o n+3 no es divisible por 4, 2 cuadrados de tamaño similar de impar dejarán un rectángulo par por par, por lo que sólo necesitarás 2 cuadrados de lado de impar
si n o n+3 es divisible por 4 te quedas con un rectángulo de 2 por impar y otro par por par.
y necesitas dos cuadrados adicionales de lado impar para convertir el rectángulo de 2 por impar en un rectángulo par por par, así que un total de 4 cuadrados de lado impar
Gracias a Steve por los dibujos
Denota por $f(n)$ el número mínimo de cuadrados de tamaño impar en una descomposición de un $n\times (n+3)$ cuadrado. Entonces (como adivinó @Willemien en su respuesta) tenemos $f(n)=g(n)$ donde $g(n)=4$ cuando $n$ es de la forma $4q$ ou $4q+1$ y $g(n)=2$ cuando $n$ es de la forma $4q+2$ ou $4q+3$ .
En primer lugar, si $r$ es el número de cuadrados de tamaño impar en cualquier descomposición de un $n\times (n+3)$ cuadrado, contando los cuadrados de la unidad y trabajando en módulo $4$ vemos que $n(n+3)\equiv r \ ({\textsf{mod}} \ 4)$ . También, $r$ no puede ser cero porque uno de $n$ ou $n+3$ es impar. De ello se desprende que $r\geq g(n)$ para cualquier descomposición, y por tanto $f(n)\geq g(n)$ .
La desigualdad inversa $f(n)\leq g(n)$ ya se ha demostrado en respuesta de @Willemien. A continuación se muestra una imagen que resume su argumento (con rectángulos de tamaño par en verde y cuadrados de tamaño impar en rojo ):
Si he entendido bien el problema pide el divisor común mayor de impar de $n$ y $n+3$ . Pero la paridad de $n$ y $n+3$ es diferente, porque si $n$ es par y se suma 3 entonces $n+3$ es impar, y viceversa.
Entonces el problema se reduce a buscar el GCD de $n$ y $n+3$ . Si GCD divide $n$ entonces
$$(GCD\mid n)\land (GCD\mid n+3)\implies GCD\mid 3\implies GCD(n,n+3)\in\{1,3\}$$
Entonces tenemos que el menor número de cuadrados (LNS) será
Causa $n>10$ compararemos el mínimo n divisible por 3 ( $n=12$ ) y el mínimo absoluto $n=11$ :
Así que el número mínimo de cuadrados para un rectángulo $n\times(n+3)$ donde $n>10$ son $20$ y ocurre cuando $n=12$ .
Tal vez la interpretación de la pregunta no era correcta porque veo la etiqueta "combinatoria". A la luz de esta información el problema puede pedir por la forma de cortar el rectángulo en piezas que son cuadrados con longitud impar.
Si, por mi interpretación anterior, sabemos que $GCD(n,n+3)\in\{1,3\}$ entonces sabemos que
Es obvio que la solución óptima está relacionada con algún n divisible por 3:
Análisis:
si $2\mid n$ entonces no se puede cortar un cuadrado $n\times n$ porque $n$ es uniforme, por lo que tendrá un montón de pequeños cuadrados de $1\times 1$ para cubrir una línea de, al menos, longitud $n$ es decir, tendrá al menos $n+1$ cuadrados.
si $2\not\mid n$ y $3\not\mid n$ entonces $GCD(n,n+3)=1$ como he demostrado arriba, entonces puedes cortar un gran cuadrado $n\times n$ porque n es impar, y después de cortar el resto que es un rectángulo $n\times4$ donde, recuerda, $3\not\mid n$ por lo que tendrá algún resto de cuadraditos de $1\times1$ , tal vez 3 o 6 dependiendo de $n \pmod 3$ además de toda una línea de $n+1$ . Así que tendrá un mínimo de $n+8$ cuadrados.
si $3\mid n$ y $2\not\mid n$ entonces puedes cortar un gran cuadrado $n\times n$ porque n es impar, además de algunos $3\times 3$ cuadrados porque n y $n+3$ son divisibles por 3. Se tendrá aquí la solución óptima porque no hay cuadrados de $1\times 1$ . El número mínimo de casillas será $4$ cuando $n=9$ pero $n>10$ por lo que el mínimo será $6$ cuadrados.
Así que la solución del problema será el mínimo n que son Impares y divisibles por 3. Si $n>10$ este número es 15.
Para $n=15$ tendremos una gran plaza de $15\times 15$ y 5 cuadrados de $3\times 3$ , siendo un total de 6 casillas. Cualquier otro n no se puede cortar en menos número de cuadrados con lado de longitud impar.
P.D.: existen soluciones con menor o igual número de cuadrados pero para $n<10$ .
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.
