Rectángulo con lado natural

Os dejo el problema de esta semana:

Un rectángulo $R$ se subvidide en una serie de rectangulos $R_1,\ldots, R_n$ de tal modo que cada uno de los rectángulos $R_i, \; 1\leq i \leq n$ posee al menos un lado de longitud natural. Demostrar que entonces el rectángulo original $R$ debe tener un lado con longitud natural.

El problema me lo ha enviado Domingo, que lo vio en este post del blog de J.H.S., donde no encontró respuesta. A ver si aquí se la damos.

29 comentarios

Trackback | 25 May, 2010

Bitacoras.com
Trackback | 25 May, 2010

Tweets that mention Rectángulo con lado natural | Gaussianos -- Topsy.com
OnyxIonVortex | 25 de May de 2010 | 15:21

Pues para un solo rectángulo (n=1) está claro.
Ahora hay que demostrar que si se cumple para n rectángulos también se cumple para n+1.
Siempre que añadimos un rectángulo a la serie tenemos que dividir mediante una línea a otro preexistente. Entonces el problema se reduce a demostrar que si un rectángulo se divide en dos de lado natural, este también tiene un lado natural.
Hay dos casos:

1) Que el lado natural de uno de los rectángulos sea el lado común a los dos o uno paralelo a este. Entonces, el rectángulo original tiene los lados paralelos a la línea que lo divide de longitud natural.

2) Que el lado natural de los dos rectángulos no sea el lado común ni paralelo a este. Entonces, el rectángulo grande tiene un lado natural que será la suma de los lados naturales de cada rectángulo pequeño, ya que la suma de dos naturales es también natural.
Agustín Morales | 25 de May de 2010 | 15:23

Se cumple para n=1 y para n=2 de forma trivial. A bote pronto parece que quizás se pueda probar por inducción… habrá que pensar.
Agustín Morales | 25 de May de 2010 | 15:27

¡Vaya! acabo de ver que OnyxIonVortex y yo hemos publicado a la vez y ambos con la idea de la inducción.
Osukaru | 25 de May de 2010 | 15:34

Te equivocas OnyxlonVortex, no es tan sencillo como lo planteas. Estás suponiendo que la única forma de subdividir un rectángulo en rectángulos más pequeños es añadiendo líneas sucesivamente, pero esto no es así. Por poner un contraejemplo, a ver si se aprecia:

_ _ _ _ _ _ _
| | |
|_ _ _ _ _| |
| | | |
| | | |
| |_ _ _|_ _ |
| | |
|_ _|_ _ _ _ _ |

A este cuadrado que he dibujado no le puedes quitar ninguna línea de forma que te quede subdividido en 4 rectángulos.
Osukaru | 25 de May de 2010 | 15:36

Vaya, no ha quedado el cuadrado como yo quería… con lo que me ha costado dibujarlo Espero que aún así se entienda la idea.
Pepe | 25 de May de 2010 | 15:41

No estoy de acuerdo con OnyxIonVortex, ya que existen otras particiones de un rectángulo además de las que se forman a base de dividir los existentes. Por ejemplo, tómese una cuadrícula de 3×3 y numérense los cuadrados del 1 al 9 en el sentido de lectura, de izquierda a derecha y de arriba abajo. Tómese ahora la siguiente partición en 5 rectángulos: uno que corresponda a la unión de los cuadrados 1 y 2, otro que sea la unión de 3 y 6, la unión de 4 y 7, la unión de 8 y 9 y finalmente otro que consista solo en el cuadrado 5. Tal partición no puede ser obtenida mediante divisiones sucesivas a partir de un rectángulo original. Perdonen que me haya enrollado tanto para explicar un concepto tan simple. Desde luego es solo un ejemplo que no tiene que ver con el problema, pero demuestra que es falsa la afirmación “Siempre que añadimos un rectángulo a la serie tenemos que dividir mediante una línea a otro preexistente”, lo cual hace que la inducción se complique…
Pepe | 25 de May de 2010 | 15:51

Bueno, Osukaru, parece que queremos expresar la misma idea, no sé cuál lo habrá explicado peor xD

Para intentar buscar la inducción habría que contemplar que para añadir un rectángulo puede hacerse de otras formas además de dividiendo, que implican redimensionar algunos rectángulos existentes… Lo veo complejo.

Otra idea puede ser reducción al absurdo: suponer que existe un rectángulo de lados no naturales, dividido en rectángulos que cumplen que al menos un lado es natural… y llegar a una contradicción, probablemente por la vía de sumar perímetros, o trazar líneas transversales y sumar los recorridos por cada rectángulo interior, …

Como complemento a la reducción al absurdo, tendríamos el descenso infinito: supuesto que exista un rectángulo como el explicado en el párrafo anterior, demostrar que existe otro con las mismas propiedades pero con menos rectángulos…

Son ideas. Yo estoy espeso, pero a ver si alguien..
josejuan | 25 de May de 2010 | 16:12

Otra vía es probar directamente que, si los lados no son enteros, entonces forzosamente algún rectángulo interior tiene ambos lados no enteros.

Tomando esta idea con cada lado independiente se ve que forzosamente existe (al menos) una franja (vertical) de ancho no natural y (al menos) otra franja (horizontal) de alto no natural.

La intersección de ¿todas?, ¿alguna? de los pares de franjas (tomados verticales X horizontales) nos da (al menos) un rectángulo con ambos lados no naturales.

Ummmpprrfff…..
J. H. S. | 25 de May de 2010 | 21:38

He aquí una sugerencia: integre una función en dos variables sobre el rectángulo completo de tal manera que sobre cada $R_{i}$ el resultado sea cero. Por aditividad se tendría que la integral doble sobre el rectángulo $R$ también es cero. Claramente, esto dice que la función elegida debe ser tal que la integral doble nos de una expresión en términos de los vértices del rectángulo sobre el que se integra y más aún que la expresión esa se anule si y sólo si los vértices son enteros.

P.D. Gracias por considerar mi blog una vez más, Diamond.
Rober | 25 de May de 2010 | 22:25

Creo que he encontrado una forma de solventar las particiones y reducir al absurdo suponiendo que el rectángiulo original tiene sus lados no naturales.

Tomemos el rectángulito que esté en la parte superior derecha. Supongamos que sus lados naturales (n) son los horizontales (el razonamiento es simétrico si son los verticales). Tomemos el lado vertical donde termina y lo “alargamos” hasta abajo del todo, dejando el rectángulo grande en dos “trozos”: uno tendrá el lado natural del rectangulito (n) y el otro el resto (L-n)

Este resto (L-n) deber ser no natural (de lo contrario L sería natural y llegaríamos ya al absurdo) y la altura tampoco puede serlo (porque es igual a la del original).

Los rectángulitos que sean “partidos” son de dos tipos: los que son “horizontal-naturales” que dejan en el resto un trocito “horizontal-natural” (o no: ver abajo), y los que son “vertical-naturales” que dejan un trocito “vertical-natural” (todo su lado vertical lo es).

Es decir, que tenemos un resto (L-n) que se comporta como el original: sus lados son “no naturales” y todos sus cachitos tienen un lado natural (los que ya “cabían” enteros y los trocitos)

Si la secuencia no es infinita, hay un momento en que no podamos dividir más porque nos quede un único rectangulito, llegando al absurdo de que alguno de sus lados es natural y no natural al mismo tiempo.

(*) Esta división es la problemática. Si el rectangulito que es partido por su lado natural deja dos trozos no naturales A y B entonces el trocito B que nos deja en el resto no nos sirve para seguir iterando. Hay que tomar entonces el otro resto: es decir, el que está “debajo” del primer rectangulito (sin incluirlo) y que tiene lado horizontal “n” y partirlo por la vertical del trocito A. Al restarle el ladito no natural a “n” volvemos a dejar un resto de lados no naturales para seguir iterando. Esto hay que hacerlo con el mayor de los trocitos de todos los rectangulitos divididos, para simplificar.

El problema es que la iteracción no se “resuelve” antes de pasar a la siguiente, pero creo que al no ser infinita eso no supone un problema.

No se si estará bien o si entenderá, porque al final he puesto tantos diminutivos que parezco Ned Flanders
Rober | 25 de May de 2010 | 22:42

El argumento anterior es algo más sencillo de entender si antes de nada se dividen los rectangulitos en “n” rectangulitos de lado 1 por su lado natural.

El caso es el mismo, pero con lados naturales cualesquiera siempre hay que ir mirando cómo se subdividen: al ser de lado 1 toda subdivisión posterior ya no obtiene naturales.
M | 25 de May de 2010 | 22:59

Rober, creo haber entendido tu propuesta, y me parece que tu frase “Hay que tomar entonces el otro resto: es decir, el que está “debajo” del primer rectangulito (sin incluirlo) y que tiene lado horizontal “n” y partirlo por la vertical del trocito A.” requiere algo más de precisión.

Cuando tomas “el otro resto” te queda el trozo A, que no tiene ninguno de sus lados naturales. Puede que esté algo torpe, pero no veo que ese “otro resto” vaya a tener una subdivisión como la del rectángulo original.

Por otra parte, comentar que este problema es un clásico para el que se conocen más de una decena de demostraciones a cual más elegante (entre ellas la que deja entrever J.H.S. y alguna que otra por inducción).

Por cierto, esta propiedad se generaliza a $n$ dimensiones, de modo que una caja subdividida en cajas con al menos $l$ lados naturales debe tener también al menos $l$ lados naturales.
Rober | 25 de May de 2010 | 23:28

Jo, pues explicarlo para “cajitas de n-dimensionitas” es para volverse loco

Precisemos:

Tenemos el rectángulo original (L x H) dividido en tres: el rectangulito (n x h), el primer resto (L-n x H) y el segundo resto (n x H-h).

Si hay rectangulitos de horizontal-naturales (m x J) que son partidos en dos trozos A+B=m no-naturales (A+B x J), el trozo (B x J) queda en el primer resto (e invalida ese resto) y otro (A x J) en el segundo resto.

Ahora hay que tomar ese segundo resto (n x H-h) y dividirlo en dos por la vertical “izquierda” del rectangulito partido, de tal forma que quedarán a su vez dos restos: (n-A x H-h) y (A x H-h) y tomamos el primero de ellos (n-A x H-h) para seguir iterando el cual tiene sus lados no naturales (hasta que lleguemos al absurdo, claro)

Como hemos tomado el rectangulito partido que tenga la mayor parte A dentro del segundo resto, nos aseguramos que esta última división no vuelve a cortar los rectangulitos previamente cortados por la primera con lo que evitamos dividir algo que ya tenga ambos lados no-naturales (lo que invalidaría la inducción)

Al hacer la división de (n-A x H-h | A x H-h) pueden partirse en dos, otra vez, rectangulitos (que serán originales, no partidos previamente) digamos que en C (del lado n-A) y D (del lado A)

Recordemos que n-A y A son no naturales hasta el momento. Tanto si la nueva división produce dos trocitos no-naturales como dos naturales no nos importa: siempre habrá un resto no-natural para escoger y seguir iterando.

Ojo: jugamos con dos tipos de “restos”, los que son teselados por rectangulitos con algún lado natural (cuando la prolongación no produce cortes) y los que no, en los cuales la iteración se realiza hasta encontrar uno que al prolongar no produzca cortes.

No se ve claramente, pero no siempre jugamos con el lado horizontal; podríamos pasar a lados verticales (que es simétrico) cuando tengamos un “resto” teselado y el rectangulito elegido tenga el lado natural en vertical.

Creo que con eso está todo, pero muy elegante no es, no.
Asier | 26 de May de 2010 | 04:08

La demostración que se me ocurre consiste en observar que cada $R_i$ se puede descomponer siempre en rectángulos donde algún lado mide 1. Éstos a su vez, también pueden descomponerse en rectángulos de lado más pequeño (como deseemos) manteniendo uno de los lados con el valor 1.

Siendo esto así, con estas ‘piezas atómicas’ reconstruimos $R$ por franjas, con los rectángulos de altura 1, hasta que nos quede una franja de altura menor que 1 (si no queda franja es porque ya hemos terminado y la altura sería un número entero). Ahora, con las piezas que nos quedan (siempre podemos hacerlas más pequeñas, manteniendo un lado a 1) tendríamos que ser capaces de llenar el área que queda, pero estamos obligados a colocarlas en horizontal, con lo cual $R$ tiene una anchura que es un número entero.

Con esto lo que se ve también es que si todos los $R_i$ tienen algún lado de longitud k, entonces algún lado de $R$ tiene una longitud que es múltiplo de k.

¿Os parece válido el razonamiento?
FIDELERNESTO | 26 de May de 2010 | 07:18

A ver quien me puede ayudar con este problemita, por favor: A una varilla de metal le practicamos dos cortes (una tras otro), ¿cuál es la probabilidad de que con los tres trozos obtenidos podamos formar un triángulo?
josejuan | 26 de May de 2010 | 09:35

FIDELERNESTO, tienes dos variables aleatorias independientes X e Y que son los cortes, por tanto, tienes un espacio bidimensional, un cuadrado vaya. En ese cuadrado, habrá puntos (zonas, áreas, …) que permitirán formar un triángulo y otras que no. Integra las áreas que sí lo permiten y ya lo tienes.
Agustín Morales | 26 de May de 2010 | 09:56

[OFF TOPIC]
Fidelernesto, yo diría que la probabilidad es 1. Con tres trozos siempre puedes formar un triángulo.
Pepe | 26 de May de 2010 | 10:27

FIDELERNESTO, la probabilidad es 1/4.

Dibuja un triángulo equilátero de altura la longitud de tu varilla. Cada punto en el interior y en el borde del triángulo corresponde a un estado posible de tu problema, tomando como “coordenadas” de dicho punto las distancias a cada lado del triángulo. Dentro de ese espacio de coordenadas, la zona “válida” es aquella en la que cada coordenada es menor de 1/2 de la longitud de la varilla (para que se verifique la desigualdad triangular), y dicha zona viene siendo un triángulo de área 1/4 del original.

No lo expliqué muy bien, pero espero haberte transmitido la idea.
Agustín Morales | 26 de May de 2010 | 11:16

[OFF TOPIC]
Oops tuve un lapsus en mi comentario anterior.
M | 26 de May de 2010 | 11:20

Rober | 25 de Mayo de 2010 | 23:28 : no veo la cosa muy clara cuando dices “y tomamos el primero de ellos (n-A x H-h) para seguir iterando el cual tiene sus lados no naturales”. Tal como yo lo veo $H-h$ sí que podría ser natural, lo cual invalida la inducción que propones.

Sin embargo, mi mayor duda es que cuando consideras la vertical, ¿por qué ha de tenerse que el nuevo rectángulo que consideras para la iteración sigue descomponiéndose en rectángulos con algún lado natural? Esta vertical podría dividir a la subdivisión del rectángulo original en nuevos rectángulos que no tienen porqué tener lados enteros.

Asier | 26 de Mayo de 2010 | 4:08: me parece que sí. Si la franja superior que queda tiene altura no natural (digamos $H-\lfloor H\rfloor$ ) y debe rellenarse sólo con rectángulos (posiblemente subdivididos) de anchura natural, entonces dicha franja tiene anchura natural.

FIDELERNESTO | 26 de Mayo de 2010 | 7:18: para formar un triángulo debe cumplirse la desigualdad triangular, y lo pides nos conduce a 1/4: http://mit.ocw.universia.net/6.281j/f01/pdf/f01-lec02.pdf

No obstante, esa cuestión tiene varias interpretaciones que dan lugar a diferentes valores: http://www.cut-the-knot.org/Curriculum/Probability/TriProbability.shtml#Yagloms
josejuan | 26 de May de 2010 | 12:38

Ja, ja, … pero hombre, no le hagáis la tarea a FIDELERNESTO.

;-D
M | 26 de May de 2010 | 13:25

La prueba que más me gusta es la siguiente:

pongamos el rectángulo en la posición $(0,0)$ , consideremos en el plano una cuadrícula de dimensiones $1/2\times 1/2$ , y coloreemos de negro y blanco las casillas (como en un tablero de ajedrez). Entonces, un rectángulo cualquiera con lados paralelos a los ejes (e independientemente de su posición respecto a la red) tiene al menos un lado entero si y sólo si el número de regiones negras y blancas es el mismo. Como esta propiedad se da para los subrectángulos $R_1,\ldots, R_n$ , también se da para el rectángulo de partida, por la misma aditividad que comentaba J.H.S.

La variante que indicaba J.H.S. consiste en elegir por ejemplo $f(x,y)=sin(2\pi x)sin(2\pi y)$ , que tiene periodos naturales en ambas variables, y por tanto su integral sobre un rectángulo será cero si y sólo si el rectángulo tiene al menos un lado natural. Luego, por aditividad, se deduce que el rectángulo original también tiene al menos un lado natural.
fede | 26 de May de 2010 | 14:43

M, tampoco está mal la del grafo bipartito:

Situamos el origen de coordenadas en la esquina inferior izquierda del rectángulo $R$ .

Formamos un grafo bipartito entre el conjunto de vértices $A = \mathbb{Z}\times \mathbb{Z}$ y el conjunto de vértices $B = \{ R_1, \ldots, R_n \}$ . colocando una arista entre un vértice (x,y) de A y uno $R_i$ de B si y solo si (x,y) es una esquina de $R_i$ .

Si cada $R_i$ tiene un lado entero, el grado de cada vértice de B es 0, 2 ó 4. Por tanto el número total de aristas es par.

El grado de un vértice de A de 0, 1, 2 ó 4, pero es 1 solo si el vértice (x,y) es una esquina de R.

Como hay un vértice de grado 1, (la esquina (0,0) ), y el número de aristas es par tiene que haber al menos otro vértice de grado 1, y R tiene un lado entero.
Dani | 26 de May de 2010 | 21:19

sólo conocía la que sugirió J.H.S. fantástica la del grafo, fede!
M | 26 de May de 2010 | 22:31

En los siguientes enlaces hay más de una decena de pruebas adicionales a las expuestas:

http://mathdl.maa.org/mathDL/22/?pa=content&sa=viewDocument&nodeId=2927

http://www.cut-the-knot.org/Curriculum/Algebra/IntRectGraph.shtml
J. H. S. | 26 de May de 2010 | 22:42

1. Otra opción sería considerar la función $f(x,y) = e^{2\pi i(x+y)}$ . Si integramos sobre el rectángulo de vértices $(x_{1}, y_{1}), (x_{1}, y_{2}), (x_{2}, y_{1}), (x_{2}, y_{2})$ se tiene que

$\int_{x_{1}}^{x_{2}} \int_{y_{1}}^{y_{2}} f(x,y)dxdy = (2\pi i)^{-2} (e^{2\pi i x_{2}}-e^{2 \pi i x_{1}})(e^{2\pi i y_{2}}-e^{2 \pi i y_{1}})$

de donde se sigue que la integral es cero si y sólo si al menos uno de los lados del rectángulo en cuestión es un número entero.

2. Cuentan por ahí que en alguna conferencia el célebre matemático francés Alain Connes mencionó que “no puede decirse que uno comprende a los números enteros a menos que uno entienda este problema”. ¿Qué opinan ustedes al respecto?
Sara | 10 de June de 2010 | 12:26

En este pdf:

http://ommcolima.ucol.mx/guias/TallerdeResolucionproblemas.pdf

a partir de la página 37, hay 6 demostraciones en español.