Recubriendo con “garfios”

Hoy martes os dejo el problema de esta semana. Ahí va:

Determina todos los rectángulos m \times n que pueden ser recubiertos por “garfios”, formados por 6 cuadrados de lado 1, como el de la figura:

Que se os dé bien.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

19 Comentarios

  1. Dado que puedo unir 2 garfios y formar un rectángulo de 3×4, también puedo formar 3×8, 3×12,… y series similares de 6×4, 6×8, …, 9x….

    Luego son infinitos.

    ¿Hay mas que los indicados?

    Publica una respuesta
  2. Como dice Juanjo, agrupando dos garfios, podemos formar un rectángulo de 4*3. Entonces esta claro que si un lado es múltiplo de 4 y otro múltiplo de 3, se puede. Pero no solo.

    Si uno de los lados es múltiplo de mcm(3, 4) = 12, y el otro es cualquier número distinto de 1, 2 y 5, tambien. No estoy seguro de si hay otras posibilidades.

    Publica una respuesta
  3. Creo que no puede haber más que los 3i x 4j … y los 4i x 3j, claro.

    Primero, veamos que toda pieza “garfio” debe acabar unida a otra pieza garfio, formando piezas básicas de 2 garfios. Cada pieza de 2 garfios tiene 12 unidades cuadradas de área.

    El garfio comienza en un “punto” (cuadradito unidad) que llamaré muñeca y acaba en otro que llamaré punta del pincho. Y los “puntos” giran alrededor de un “punto” interior. Si hay un primer garfio deberá haber otro garfio que contenga el “punto” interior. Y ese punto interior deberá ser o bien muñeca o bien punta. Cualquier otro “punto” del garfio formaría un solapamiento con el primer garfio. Ya que el punto interior sólo tiene una dirección de escape, hacia abajo, estando las otras 3 direcciones (izquierda, derecha, arriba) y los puntos muñeca y punta son los únicos que conectan con el garfio en una sola dirección.

    En el caso de que el interior sea punta sólo uno de los 4 giros evita el solapamiento, el de 180 grados. (0º produce solapamiento por arriba, 90º en sentido agujas del reloj produce solapamiento por la derecha, 270º produce solapamiento por la izquierda). Y las imágenes especulares tampoco sirven. Ese que es el único que sirve forma el ladrillo 3×4 que en sí mismo es un rectángulo y puede dar lugar a rectángulos 3i*4j

    En el caso de que el interior sea muñeca sólo hay un giro válido, nuevamente el de 180º y se forma una figura contenida en un cuadrado 4×4 también de área 12 unidades.

    Por tanto, los hipotéticos rectángulos sólo se pueden formar con las dos figuras de dos garfios citadas y su área debe ser múltiplo de 12.

    Faltaría demostrar que no puede formarse ningún rectángulo usando alguna vez la segunda figura… o, al menos, que ambas dimensiones deben ser o bien múltiplo de 3 o bien múltiplo de 4, descartando cosas como 36×17 cuya área es múltiplo de 12 unidades cuadradas pero una de las dimensiones no es múltiplo ni de 3 ni de 4.

    Para ser múltiplo de 12 las posibilidades son:

    * 3i x 4j (ó 4i x 3j): Ya hemos visto que sí se puede.

    * 12i x j (ó i x 12j): No hemos demostrado que se pueda ni que no se pueda… excepto si j es menor que 3 (en el caso 12i x j… en el otro sería el caso i menor que 3) que no se puede. Ignacio parece haber demostrado que el caso j=5 tampoco es posible.

    * 6i x 2j (ó 2i x 6j): No hemos demostrado que se pueda ni que no, salvo el caso j=1 que no se puede.

    Los casos donde el producto de dimensiones no sea múltiplo de 12 son seguro imposibles.

    Publica una respuesta
  4. Dos garfios se pueden unir de dos formas, formando un rectángulo de 3×4 o formando una figura en la que hay dos rectángulos de 3×2 unidos por el lado largo y con uno desplazado un recuadro.

    Empleando esta segunda figura, además del rectángulo 3×4, he conseguido rectángulos de 14×24 y 16×15. Aunque ambos se pueden lograr solo con rectángulos 3×4, no puedo descartar que sea posible conseguir alguno que se descomponga en dichos rectángulos.

    En la imagen se ve mejor.

    https://www.dropbox.com/s/pjgri9rbluu0iel/Rectangulos.png

    Publica una respuesta
  5. Acido, no puedes descartar 36×17. Puedes formar 36×8 y 36×9, y unirlos.

    Publica una respuesta
  6. Acido:

    Yo lo que dije es que si uno de los lados es múltiplo de 12, y el otro es cualquier número distinto de 1, 2 y 5, se puede. Simplemente porque cualquiera de estos números se puede escribir como suma de múltiplos positivos (o nulos) de 3 y 4.

    No descarto con este argumento que sea posible un rectángulo de 5*12, pero parece complicado.

    Publica una respuesta
  7. Tienes razón, Mmonchi, no me había dado cuenta de eso.

    Y muy bueno el ejemplo que pones que incluye figuras de lo que yo llamé “interior=punta” y tú llamaste “dos 3×2 desplazados”

    Entonces, cualquiera de las dimensiones puede ser cualquier número excepto el 5 ¿no?.
    Y que el producto de ambas sea múltiplo de 12.

    Por ejemplo, 10. 10 = 2*3+4. Si la otra es múltiplo de 6 ya tenemos un múltiplo de 12 en el producto… 12 ó 12i seguro que es posible, falta por ver si también es posible con 6 ó con 18 o, en general, con (2i-1)*6

    De los 3 casos de múltiplos de 12 tenemos asegurado el primero (3ix4j) y el segundo (12ixj) que sería posible siempre que j no sea 5… falta el tercero (6ix2j) con i impar, del cual todavía no sabemos nada seguro.

    Publica una respuesta
  8. Cierto Ignacio,

    pero el caso j=5 parece fácil demostrar que no es posible. Estamos hablando de una anchura de 5 en el rectángulo. En esa anchura de 5 es claro que debe haber una de las dos piezas de 12 cuadros… y esas piezas tienen anchura 3 o bien 4 (ninguna de esas piezas de 12 tiene anchura 1, ni anchura 2, ni anchura 5… En caso de colocar una de anchura 3 queda una anchura de 2 (o dos de 1) que es imposible cubrir sin salirse del rectángulo. En caso de una anchura de 4 tampoco (queda una anchura de 1 que no puedes cubrir).

    Publica una respuesta
  9. Perdón, quise decir:

    De los 3 casos de múltiplos de 12 tenemos asegurado el primero (3ix4j) y el segundo (12ixj) que sería posible siempre que j no sea 5 ni 2 ni 1 e imposible si es 1, 2 ó 5… falta el tercero (6ix2j) con i impar, del cual todavía no sabemos nada seguro (excepto que j no puede ser 1).

    Publica una respuesta
  10. Acido,

    Si j es par, los de 6i*2j son realmente 3i’*4j’, y ya sabemos que se puede. La duda esta en los de la forma 6i*2j, con i*j impar. Deben ser claramente i mayor que 1 y j mayor que 3.

    Publica una respuesta
  11. No pueden formarse rectángulos de la forma 6i*2j, con i y j impares, a base de rectángulos de 3*4. La razón es sencilla. Llamemos V al número de rectángulos de 4*3, colocados verticalmente, y H al número de ellos de 3*4, colocados horizontalmente.

    Pintamos las filas completas del rectángulo grande alternativamente blanco y negro, en igual número pues hay 2j. Cada rectangulo vertical ocupa seis casillas de cada color. Pero cada rtectángulo horizontal ocupa 8 casillas de un color y 4 de otro. Como hay el mismo número de casillas de cada color, debe haber tantos rectángulos horizontales ocupando 4 casillas blancas y ocho negras, como 4 negras y 8 blancas, por lo que H es par.

    Si ahora pintamos de igual manera las columnas en lugar de las filas, llegamos a la conclusión de que V debe ser también par, con lo que tenemos un número par de rectángulos 3*4, y no pueden ser simúltaneamente iy j impares.

    Queda por ver si cualquier rectángulo que se pueda recubrir con “garfios” se tiene que recubrir necesariamente con rectángulos 3*4. Creo que sí, pero hay que verlo. Posiblemente con un razonamiento parecido a este, pero ahora no puedo seguir.

    Publica una respuesta
  12. De acuerdo en lo primero que dices: j impar, al igual que i, es decir, ambos impares.

    Pero la última parte en principio tengo dudas ¿j mayor que 3?
    j = 1 sería 2j=2 lo cual es imposible,
    j=2 sería 4 y no es difícil ver que tampoco vale.
    Pero, ¿seguro que no puede ser j igual a 3? Por ejemplo, 30×6
    Bueno, una anchura de 6 obligaría a poner 2 bloques de 3×4… y dado que el otro número no es múltiplo de 4 parece claro que no…

    También me parece lógico descartar i=1, por la misma razón, obligaría a poner dos bloques de 3×4 y si j es impar parece imposible que cuadre.

    Así que estoy de acuerdo.

    Publica una respuesta
  13. Ignacio,

    Mmonchi puso 2 ejemplos de rectángulos recubiertos con garfios que tienen partes que no son 3×4… sino de la otra figura posible que demostré que era la única alternativa al 3×4.

    Lo que quedaría por ver es si los de tipo 6i * 2j (i, j impares) no pueden tener ningún bloque del segundo tipo. Ya hemos visto que sólo con bloques 3×4 no es pueden formar esos rectángulos, pero con alguna figura del otro tipo mezclada con bloques 3×4 todavía no sabemos si es imposible.

    Publica una respuesta
  14. Bueno, sigo por aquí …

    Acido, a eso me refería. Es decir, queda por ver si cualquier rectángulo que se pueda recubrir con “garfios” apareados de cualquier forma, tambien se tiene que poder recubrir necesariamente con rectángulos 3*4, como los dos ejemplos que puso Mmonchi.

    Los garfios tienen que ir necesariamente apareados de una de dos formas, o un rectángulo 3*4 o en un octogono no convexo.

    Con las filas y columnas pintadas alternativamente de blanco y de negro, cada octógono ocupa 6 casillas blancas y 6 negras, por lo que el número de rectángulos verticales debe ser igual que el número de rectángulos horizontales, como cuando solo se utilizan rectángulos. Por tanto el número de rectángulos es par, aun cuando tambien se utilicen octógonos.

    Queda por ver que el número de octógonos también debe ser par. He hecho cuatro o cinco esquemas de pintado de casillas, pero de momento no llego a ninguna cnclusión …

    Publica una respuesta
  15. Las 2 soluciones de Mmonchi (muy ingeniosas, por cierto) se pueden generalizar pegando 4 “piezas blancas” como en el original para el caso 1 y 4 conjuntos de doble garfio para el segundo.

    Aumentamos la longitud en 12 en ambos casos

    Publica una respuesta
  16. Supóngase que el rectangulo 3*4 (base 3, altura 4) esbel menor rectángulo de menor area que puede ser cubierto por los garfios. Si ponemos uno seguido del otro, su altura es constante (4) y su base sera de la forma 3n donde n es el numero de rectangulos.
    Análogo si su base es constante (3) y su altura es de 4n.
    La última forma es que se agregue en ambos lados, dando 3n*4n.
    Por lo tanto los rectángulos son
    3n*4
    3*4n
    3n*4n

    Publica una respuesta
  17. Es evidente que cualquier rectángulo de la forma 3n*4m se puede construir. Y como se permiten rotaciones, también todos los de la forma 4n*3m, así que a estos los llamaré simétricos.

    Por otra parte he encontrado rectángulos adicionales que no encajan en la forma anterior: con 3 rectángulos 3*4 construimos un 3*12. Bajo el lado largo de este colocamos 4 rectángulos 4*3, que dan uno mayor 4*12. El resultado de unir 3*12 y 4*12 es un 7*12 que no corresponde ni a los 4*3 ni a los simétricos. La generalización sería (4n+3m)*12p, ya que podemos replicar independientemente el rectángulo 3*12 y el 4*12. Si no me he equivocado, los resultados obtenidos por Mmonchi se pueden expresar de esta forma. O en su caso de la simétrica, que lógicamente también es posible.

    He estado buscando más combinaciones distintas pero no las he encontrado.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com Valora en Bitacoras.com: Hoy martes os dejo el problema de esta semana. Ahí va: Determina todos los…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *