Muestra que para cada $n = 2^k$ , es posible colocar los numeros $1, 2, . . . , n^2$ en un tablero de $n \times n$ de tal manera que la media aritm etica de cualesquiera de dos de los numeros colocados no esta en el mınimo rect angulo determinado por los dos numeros. Esto es, la media aritm etica de los numeros $a_{ij}$ y $a_{kl}$
no es una entrada de la forma $a_{rs}$ donde
$$min(i, k) \leq r \leq max(i, k), min(j, l) \leq s \leq max(j, l)$$
jueves, 10 de febrero de 2011
Suscribirse a:
Comentarios de la entrada (Atom)
10 comentarios:
Notemos primeramente que para $n=2^{1}$ funciona, ya que se puede acomodar como: el cuadro superior izquierdo es 1, el cuadro superior derecho es 3, el cuadro inferior izquierdo es 2 y el cuadro inferior derecho es 4. Ahora avanzaremos por inducción. Supongamos que hay construcción para $2^{k}$, pd que existe construcción para $2^{k+1}$. Hagamos la construcción de la siguiente manera: A la construcción de $2^{k}$ le añadimos una columna después de cada una de sus columnas, al igual que una fila a cada una de sus filas. Ahora, si $r\leq2^{k}$, entonces el cuadro a la derecha de r le asignamos $2^{k}+r$, al de abajo $2\times2^{k}+r$, y al de abajo a la derecha que comparte una esquina con r, le asignamos $3\times2^{k}+r$, dando así una asignación a todos los números desde 1 hasta $(2^{k+1})^{2}$.
Hagamos una subdivición en cuatro cuadros de $2^{k}$. Llamamos al subcuadro que contiene al 1 como C1, respectivamente se nombra C2, C3 y C4. Vemos que el subcuadro superior izquierdo es C1, el subcuadro superior derecho es C3, el subcuadro inferior izquierdo es C2 y el subcuadro inferior derecho es C4. Notamos que C1 y C3 contiene sólo números impares, y C2 y C4 contienen sólo numeros pares. Entonces, la media aritmética entre cualquier par de números de C1 con C2; C1 con C4; C3 con C2; y C3 con C4 es de la forma $\frac{2s+1}{2}$, es decir, no es entero, por lo cual no se encuentra en el rectángulo formado por dichos números. Ahora, si se elige un número $a\epsilon C1\; y\; b\epsilon C3$, entonces $a\equiv1(mod4)$ y $b\equiv3(mod4)$, entonces $\frac{a+b}{2}\equiv0,2(mod.4)$, por lo cual, sería par, y como C1 está junto a C3 entonces el rectángulo determinado por a y b se encuentra dentro de C1 y C3, por lo cual es impar, contradicción. Si se eligen números $a\epsilon C2\; y\; b\epsilon C4$, tenemos que $a\equiv2(mod4)$ y $b\equiv0(mod4)$, entonces $\frac{a+b}{2}\equiv\pm1(mod4)$, pero el rectángulo determinado por a y b sólo se encuentra en C2 y C4, entonces sólo hay pares, contradicción.
Por lo anterior logramos ver que si $\exists a,b$ que cumplan las condiciones del problema, entonces a y b se encuentran en el mismo Ci. Supongamos que existen a y b que cumplan, entonces $\frac{a+b}{2}$ se encuentra en el rectángulo determinado por a y b. Si $\frac{a+b}{2}=k\Leftrightarrow\frac{(a+4-i)+(b+4-i)}{2}=k+4-i\Leftrightarrow\frac{(a+4-i)+(b+4-i)}{8}=\frac{k+4-i}{4}$, en lo cual, ambos son enteros. Ahora, notamos que si a todos los cuadros de Ci le sumamos 4-i y lo dividimos entre 4, entonces nos quedará el cuadro cuando n es $2^{k}$, y como ya habíamos supuesto por hipótesis de inducción que en esa construcción no se podía formar, entonces ningún Ci cuenta con un par de números que cumplan, entonces hemos acabado.
Primero veamos que podemos ir separando en columnas por congruencias módulo $2^{k}$, agrupando en una columna los de una misma congruencia. Luego en los últimos $2^{k-1}$ espacios ponemos los múltiplos de dos, y para fines de poder ir simplificar el proceso que haremos, con los pares haremos lo mismo que con los impares sólo que para los múltiplos de $2$ los dividiremos entre dos y luego repetiremos el proceso y nuevamente de los que sigan siendo pares los mandamos hacia la derecha hacemos lo mismo y así hasta llegar al final, después, regresaremos a los números a sus valores originales.
Con los impares haremos algo parecido, los separaremos en dos grupos, los que son congruentes a 1 módulo cuatro a la izquierda y los demás a la derecha, dentro de cada grupo, haremos lo mismo, sólo que separados por congruencia módulo 8, de menor a mayor de izquierda a derecha. De manera similar organizamos cada columna, en mitades y mitades por fila y cada mitad en mitades y así sucesivamente de manera que en la primera división se hace por laos números que tienen cierta congruencia módulo $2^{k+1}$ y los de la otra, para la siguiente división en dos es para el siguiente exponente de dos (cada mitad se divide en otras dos) y así sucesivamente, poniendo abajo siempre el de la congruencia menor. Veremos que este acomodo funciona.
Primero que nada, si tomamos un impar y un par, evidentemente su media aritmética, al no ser entera no se encuentra entre ellos, de manera similar, dentro de los pares, si se toma un npumero congruente a 2 módulo cuatro y un múltiplo de cuatro, el resultante es impar así que está fuera, y así sucesivamente, de modo que si se toma un número congruente a $2^{a}$ módulo $2^{a+1}$ y un número múltiplo de $2^{a+1}$ para $a$ un entero positivo menor a $k$ veremos que la media aritmética es congruente a $2^{a-1}$ o a $2^{a-1}+2^{a}$ y en cualquier caso, esas congruencias quedaron a un lado de nuestros números, por lo que sólo hace falta probar que con la parte de los impares funciona y de manera similar haremos para las potencias de dos conforme van aumentando (de la misma manera que hicimos para acomodarlos por columnas).
Veamos qué pasa si tomamos dos números de la misma columna: Por la manera de acomodarlos, todos tienen la misma congruencia módulo $2^{k}$, digamos que tomamos dos números de 'mitades' opuestas, en otras palabras, como los dividimos en mitades las columnas, nos referimos a que tomamos a un número de una mitad y a otro de la otra. Como tienen congruencias distintas módulo $2^{k+1}$, digamos, $b$ y $2^{k}+b$ entonces su media aritmética tiene congruencia $b+2^{k-1}$ módulo $2^{k}$ lo que significa que está ubicado en otra columna, ahora, de manera similar, para cada mitad, veremos que si de cada mitad tomamos uno de una mitad de la mitad y otro de la misma mitad pero de diferente mitad de mitad, entonces la media aritmética está localizada en diferente mitad, para esto sólo hace falta modificar el exponente de la demostración anterior, para que en vez de usar a $k$, usemos el exponente que corresponda a la separación por la que se hizo esa mitad (lo que nos hizo ponerlos en distintas mitades de las mitades formadas anteriormente) y ya. Con esto vemos que si tomamos dos números cualesquiera de una misma columna, sólamente hace falta ver cuál es el corte en mitades que dividió por primera vez su agrupación y con eso veremos que su media aritmética no se encuentra entre ambos.
Ahora veamos por columnas. Si tomamos un número de una columna de congruencia uno módulo cuatro y otro de una columna con congruencia 3 módulo cuatro (que es la primera separación por mitades que hicimos), entonces la media aritmética está en los pares que por nuestro acomodo, está a la derecha de estas columnas. Ahora, para cada mitad realizaremos lo mismo, sólo que veremos las congruecias correspondientes módulo el exponente de dos correspondiente al primer corte que los separó (de la misma manera que hicimos para las filas) y veremos que pues uno tiene, digamos, congruencia $c$ módulo $2^{d}$ y el otro tiene congruencia $c+2^{d-1}$ en el mismo módulo, por lo que su media aritmética tiene congruencia $c+2^{d-2}$ módulo $2^{d-1}$ y eso quedó en la otra separación por mitades (en la mitad anterior a la que separó estas dos columnas por primera vez) por lo que su media aritmética está en una columna que no comparte cuadritos con el rectángulo formado por estos dos cuadritos que seleccionamos.
En conclusión, para impares, si tomamos números de la misma columna, su media aritmética no está entre esos números, si tomamos números de distintas columnas, la columna que contiene la media aritmética no está entre estas dos columnas. Y como si mezclamos par con impar, no se puede, entonces nos enfocamos a los múltiplos de dos y hacemso lo mismo, de nuevo con los de cuatr y así sucesivamente, hasta el final. Veremos que como este acomodo sirve, entonces existió, y acabamos.
Pues usamos induccion sobre k, para k=0, pues es obvio.
Luego supongamos que para 2^k se puede. notemos que si para los numeros de 1 a n^2 se pueden acomodar, entonces se pueden acomodar los numeros f(1), f(2),..., f(n^2), donde f es una funcion lineal ( osea f(x)=mx+b), por que f cumple que
f((a+b)/2)=(f(a)+f(b))/2.Entonces lo vamos a probar para k+1. El tablero de $2^{k+1}x2^{k+1}$ lo dividimos en 4 tableros de $2^k x 2^k$ en el tablero superior izquierdo pondremos los numeros congruentes a 1 mod 4. en el superior derecho los congruentes a 2 , en el inferior izquierdo los congruentes a 3, y en el inferior derecho los congruentes a 0. Luego nos fijamos que uno del lado izquierdo con uno del lado derecho, su promedio no es entero, entonces no nos debemos preocupar por evitar que el promedio quede entre ellos. Luego entre los numeros de la izquierda que no son congruentes entre si, el promedio de un numero congruente a 1 y uno a 3, va a resultar ser par, o sea va a estar del lado derecho, y no es necesario preocuparnos pues los numeros estan en la izquierda. Igual nos fijamos que en el lado derechoentre dos de ahi que sean diferentes mod 4, su promedio es impar y estara del lado izquierdo. Por eso, cada tablero de $2^kx2^k$es independiente de los demas y no importa como los acomodemos, entre si no va a haber parejas que no cumplan lo que queremos. Luego, cada uno de esos tablero es lo mismo que nuestra hipotesis de induccion, aplicando f como (f(x)= 4x, f(x)= 4x-1, f(x)= 4x-2, f(x)= 4x-3).
Vemos por inducción: k=0 es trivial y para k=1
12 cumple.
34
Supongamos que es posible acomodar un tablero de $2^k*2^k$ entonces vemos para uno de $2^{k+1}*2^{k+1}$, lo podemos dividir en cuatro subtableros de $2^k*2^k$ y en base al tablero que ya formamoslos siguientes 4 acomodos:
A) a=4x-1
B) b=4x-3
C) c=4x
D) d=4x-2
donde para cualquier casilla $a_i$ de nuestro acomodo A tendra el número $4x_i-1$ donde $x_i$ es la casilla analoga, de nuestro tablero que ya acomodamos. Entonces nuestro nuevo tablero sera:
AB notamos que están escritos todos los
CD números y que en la mitad superior estan
los impares y en la inferior los pares, por lo tanto si tomamos cualesquiera dos casillas en mitades distintas su media no sera entera y por lo tanto no nos preocupa. Si tomamos dos casillas, una en A y otra en B su suma sera congruente con 0 (mod 4) y su media sera par, pero en las zonas A y B no hay numeros pares, analogamente la media de dos casillas una en C y otra en D sera impar y no nos preocupara. Finalmente si tomamos dos casillas en la misma zon estas seran de la forma 4i-r y 4j-r para $0<1<j<2^k+1$ y $r perteneciente a {0,1,2,3}$
entonces la media de los numeros sera
$(4i-r+4j-r)/2=[4(i+j)-2r]/2=4[(i+j)/2]-r]$ que implica que si en el nuevo acomodo esta la media aritmetica de los dos numeros dentro del rango del rectangulo entonces en el acomodo de $2^k*2^k$ también estaba, lo cual es una contradicción ya que nuestro acomodo es bueno, y asi completamos la inducción.
Lo hare por induccion
para n=2^1
se pone el 2 en el superior izquierdo, el 4 en el superior derecho, el 1 en el inferior izquierdo, y el 3 en el inferior derecho.
suponemos que n=2^k cumple
para n= 2^(k+1) dividimos el tablero en 4 regiones,
la superior izquierda sera A0, la superior derecha sera A1, la inferior izquierda sera A2, y la inferior derecha sera A3.
y colocamos en Ai los congruentes a i Mod 4, para i=0,1,2,3.
vemos que elementos de A0 con A1 o A3, la suma es impar, por lo que la media aritmetica no es un entero, y no puede estar en tablero, analogamente A2 con A1 o A3.Con elementos de A0 con A2 la suma es congruente a 2 Mod 4, por lo que la media aritmetica es impar, y no puede estar en un rectangulo del lado izquierdo del tablero, ya que del lado izquierdo estan los pares y del derecho estan los impares. Elementos de A1 con A3 la suma es congruente a 0 Mod 4, por lo que la media aritmetica es par, y no puede estar contenida en el lado derecho del tablero, solo faltan cubrir los casos en que la media se toma con elementos de la misma region.
Antes veamos que si f(a)= ax+r, para a,x,r naturales,y x,r fijos, se cumple que ((f(a)+f(b))/2)=f((a+b)/2)
pero se tiene que ((f(a)+f(b))/2)=(ax+bx+2r)/2=((x(a+b))/2) + r=f((a+b)/2).
ya que las ecuaciones para A0, A1, A2, A3 de los numeros del 1 al n^2 son 4r, 4(r-1)+1,4(r-1)+2,4(r-1)+3,respectivamente, con r entero entre 1 y n^2. y ya que existe por la base de induccion un acomodo para los numeros del 1 al n^2, como la ubicacion de los promedios se `preserva, entonces es posible acomodar las 4 regiones, por lo que el tablero para n=2^(k+1) tambien cumple, y entonces cumpla para todo n=2^k, para todo k natural.
Lo haremos por inducción sobre k.
Para k=1, es claro que sirve el siguiente acomodo:
1 2
3 4
Para k=2, empleamos el siguiente acomodo:
5 9 6 10
13 1 14 2
7 11 6 12
15 3 16 4
Para construirlo, dividimos el tablero en 4 partes iguales A1, A2, A3, A4 de esta manera:
A1 A2
A3 A4
Entonces, el cuadrante Ai, i=1,2,3,4, estará compuesto así:
i+4 i+8
i+12 i
Además, numeraremos el tablero en casillas de esta manera:
C1 C2 ...C4
C5 ..
... ..
C13 ... C16
Para k=3, dividiremos el tablero en 16 cuadrantes de 2x2, de esta manera:
A1 A2 ...A4
A5 ..
... ..
A13 ... A16
En la esquina inferior derecha de cada cuadrante pondremos el número que correspondió al mismo número de casilla en el tablero anterior (k-1), por ejemplo, en la esquina inferior derecha de A1 irá 5, en la de A2 irá 9, en la de A15 irá 16, etc. Cada cuadrante tendrá la siguiente configuración:
i+16 i+32
i+48 i
Así construiremos todos los tableros siguientes, se dividirá el tablero en n^2/4 cuadrantes, cada con la siguiente configuración:
i+2^(k-1) i+2(2^(k-1))
i+3(2^(k-1)) i
La i en cada cuadrante estará definida como lo estuvo en el tablero con k=3.
Ahora, veamos que este tablero funciona:
Por la construcción del tablero, tenemos que si hacemos un corte vertical por la mitad, del lado izquierdo estarán los impares y del derecho los pares. Si hacemos un corte horizontal por la mitad y nos fijamos en el lado de los impares, arriba estarán los de la forma 4k+1 y abajo los de la forma 4k+3. Si nos fijamos en el cuadrado con los números de la forma 4k+1 y lo partimos verticalmente por la mitad, a la izquierda estarán los de la forma 8k+5 y a la derecha los de la forma 8k+1. Si hacemos un corte horizontal por la mitad y nos fijamos en el lado de los números de la forma 8k+1, arriba estarán los de la forma 16k+9 y abajo los de la forma 16k+1. Podemos seguir haciendo cortes de esta manera hasta que nos queden casillas unitarias; estos cortes son análogos para todas las secciones.
Ahora, tenemos que si tomamos dos números en diferentes mitades del tablero (izquierda y derecha), como tienen diferente paridad no tienen media aritmética entera. Tomamos cualesquiera dos números a y b de la misma paridad en el tablero y el mínimo m menor que 2^(2k-1) tal que a≢b mod 2^m. Entonces, a≡b+2^(m-1) mod 2^m, de donde a+b≡2b+2^(m-1) mod 2^m, de donde (a+b/2)≡b+2^(m-2) mod 2^(m-1) Por la definición de m, a≡b mod 2^(m-1). Entonces, al dividir el tablero en secciones de acuerdo con las congruencias de números módulo 2^(m-1)(como lo hicimos arriba), tenemos que a y b están en la misma sección y que su media aritmética está en una diferente. Como el mínimo rectángulo de a y b está contenida en la sección en la que se encuentran, (a+b)/2 no se encuentra dentro del mínimo rectángulo de a y b.
Ahora, si no existe m, es decir, que no existe un número m menor que 2^(2k-1) tal que a≢b mod 2^m, tenemos que a≡b mod 2^(2k-1), pero por la construcción del tablero a y b están en casillas adyacentes, por lo que en su mínimo rectángulo sólo están ellas dos. ∎
Lo demostraré por inducción. Cuando n = 2, la forma sería:
|1|2|
|3|4|
y se cumple lo que buscamos según el problema.
Ahora, supongamos que para 2^k mayor o igual a 2 se puede encontrar el acomodo que estamos buscando. Entonces, para un cuadrado de lados de 2^(k+1), ¿se podrá también? Para esto, vamos a dividirlo a la mitad el cuadrado, por comodida diré que daremos un corte vertical al cuadrado. De esta manera, en el lado izquierdo pondremos a los impares, mientras que del otro pondremos a los impares. Haciendo esto, si tomáramos un número del hemisferio izquierdo del cuadrado y otro del derecho, la media aritmética no sería un entero puesto que estaríamos tomando un par y un impar. Lo único que tendríamos que hacer ahora sería acomodar los números de tal forma que si dos números de un mismo lado son tomados, en su rectángulo no esté su media aritmética.
Cabe mencionar que si a cada uno de los impares le sumanos uno, tendríamos todos que están en el lado derecho, no precisamente en el mismo orden. Ahora, si los pares los lográramos acomodar con las condiciones que buscamos y ese acomodo lo reprodujéramos en el lado izquierdo, restando 1 a cada casilla, tendríamos lo siguiente.
En la zona de los pares:
si tenemos números a,b entonces (a+b)/2 no está dentro del rectángulo que al que se refiere el problema. Eso significa que en la zona de los impares no se encontraría en ese rectángulo ese número menos uno, (a+b)/2 - 1.
En la zona de los impares:
En las posiciones donde se hallaban a y b se encuentran a-1 y b-1. Su media aritmética es (a-1 + b-1)/2 = (a+b-2)/2 = (a+b)/2 - 1. Y ese número no deseamos que exista en el rectángulo mencionado por el problema, aunque ya habíamos dicho que no iba a estar, dada la similitud del acomodo del lado derecho con el del izquierdo.
Ahora dividimos el rectángulo derecho en dos partes mediante un corte horizontal. En la sección de abajo colocaremos los múltiplos de 4 y los números congruentes con 2 módulo 4 los situamos arriba. De esta manera, ¿qué ocurre si escogemos un número de arriba y uno de abajo? Al ser uno de ellos múltiplo de cuatro y el otro no, su suma resulta no ser múltiplo de 4, así que al dividirlo entre dos nos da un número impar. Obviamente en ese rectángulo no habría un número impar, debido a que los números impares están en el lado izquierdo del Gran Cuadrado.
Por último tendríamos que hallar un acomodo de los múltiplos de 4 para que si escoges dos números a,b dentro de ese conjunto, su media aritmética no esté en el rectángulo formado por a y b. ¿Cómo podemos hacer esto? Tomemos en cuenta cada número dividido entre 4. En ese caso tendríamos los números del 1 al al 2^(2k). Sabemos que los podemos acomodar de tal forma que si tomamos x,y entonces en el rectángulo formado por ellos 2 no está (x+y)/2. Traducido a a y b, obtenemos que si tomamos 4x y 4y(i.e. a y b) en el rectángulo formado por ellos no está 4(x+y)/2 = (4x+4y)/2. Es decir, la media aritmética de a y b. Y esto es justo lo que deseamos. Entonces sí se puede construir la esquina inferior derecha del Gran Cuadrado y dada la forma en que se construye el resto de éste, concluimos en que se puede construir el Gran Cuadrado en su totalidad.
David, problema comentado y resuelto por
Manuel Alejandro, Jorge Chuck, Flavio, Danielimo, angel95, Enrique, FerchoAñorvus
Publicar un comentario