viernes, 21 de septiembre de 2012
Problema del dia. Combinatoria (21 de Septiembre)
Sea n un número entero mayor que 1. ¿De cuántas formas se pueden acomodar todos los números 1,2,…,2n en las casillas de una cuadrícula de 2×n , uno en cada casilla, de manera que cualesquiera dos números consecutivos se encuentren en casillas que comparten un lado de la cuadrícula?
Suscribirse a:
Comentarios de la entrada (Atom)
Nos fijamos que si están juntos los números consecutivos, se puede trazar una línea que vaya del 1 al 2n pasando por todos en orden sin repetir, y las formas de trazar la línea son las formas de acomodar los números
ResponderBorrarNos fijamos que si tenemos el 1 en un lado (no en una de las 4 esquinas) el 2n no puede estar en ninguno de los tres en la otra fila frente al 1:
... - 1 - ...
... x x x ...
Porque entonces la línea no podría pasar de un lado al otro de la cuadrícula pero tiene que cubrirla toda. El 2 tampoco puede estar en la otra fila frente al 1 porque pasaría lo mismo, entonces está a un lado, además si la línea de vuelta antes de llegar a la orilla también separa a la cuadrícula en dos. Entonces la línea debe seguir derecho hasta la orilla y dar vuelta hasta cruzar al 1.
... * 1 ------ ... -
... ---------- ... -
A partir de aquí, la línea tiene que zigzaguear hasta 2n, si no lo hace quedaría un cuadro al que la línea puede llagar pero no regresarse pero tiene que regresar a 2n.
... 2n ... - * 3 2 ...
... -- ... 6 5 4 1 ... (No necesariamente está ahí el 1, el * es el cuadro del que la línea no podría regresar).
Cuando la línea llega a donde está 2n y deja de zigzaguear, pasa lo mismo que al principio (la línea tiene que seguir derecho hasta la orilla y luego regresar a 2n).
Entonces si definimos 1 y 2n (de forma que 1 no esté en una esquina) sólo hay una línea.
Vemos que hay dos posibilidades para el punto donde se encuentran 2n y la línea en zigzag:
... 2n 7 6 3 2 ...
... -- 8 5 4 1 ...
o
... 2n 8 5 4 2 ...
... -- 7 6 3 1 ...
Es obvio que sólo en el primer caso se puede terminar la línea (en el segundo la línea no podría llegar a donde está el 8 o donde está --), entonces definiendo 1 y 2n sólo hay una línea, y sólo hay una posibilidad de escoger 2n por columna por lo tanto las formas de escoger 1 y 2n en este caso son $(2n-4)(n-1)=2n^2-6n+4$ (2n-4 son las formas de colocar 1 porque no estamos considerando las esquinas, y n-1 las formas de poner 2n porque no puede estar en la misma columna que 1).
Si 1 está en la esquina, pasa más o menos lo mismo. Si tenemos
1 ...
2n ...
la línea sólo puede ir derecho y regresar, si da vuelta dividiría a la cuadrícula. Si tenemos
1 2n ...
-----...
la línea tiene que bajar y luego ir derecho hasta la orilla y regresar. No podemos tener
1 -- ...
* 2n ...
porque entonces la línea no podría llegar a *.
En los demás casos, el 2 debe estar debajo del 1, si está a un lado tenemos
1 2 ...
* - ...
y no puede llegar a *. A partir de aquí es como el otro caso (tiene que zigzaguear y hay una sola posibilidad por columna para 2n [igual que en las primeras dos columnas]) y también hay un solo camino después de elegir 1 y 2n, las formas de escogerlos son $4n$ (porque hay 4 esquinas y n columnas).
Las formas totales es la suma de los dos subcasos: $2n^2-6n+4+4n=2n^2-2n+4=2(n^2-n+2)$
que bueno que yo no reviso esto (:
Borrar:) ... tardé para entenderle jaja ... supongo que es culpa de que no se pueden hacer dibujos aqui xD ... y bueno, no entendí que significa el caso inmediato anterior a: Es obvio que .... creo que ese caso esta mal... pero me gustaría que lo revisaras y me dijeras que onda jeje n_n
BorrarAhí hay dos casos porque la línea que va zigzageando se puede acercar a 2n de dos formas (de los números nada más el 2n representa el número que está en ese cuadro, los otros representan cómo avanza la línea):
Borrar... 1 4 5 - -- ...
... 2 3 6 - 2n ...
o
... 1 4 5 - 2n ...
... 2 3 6 - -- ...
El primer caso se puede terminar igual que como empieza la línea:
... 5 8 9 ---> ...
... 6 7 2n <--- ...
Pero el segundo caso no se puede terminar
... 5 - 2n ...
... 6 7 - ...
porque la línea debe pasar por los dos "-", pero al ir a uno ya no puede llegar al otro sin pasar por el 2n que es donde termina la línea.
¿Sí era esa parte? Nada más lo volví a escribir...
Si jeje esta bien n_n ... :)
BorrarAqui esta link para ver un documento que hize con la solución:
ResponderBorrarhttps://www.dropbox.com/s/20h8lxc7atr4v9s/21%20Septiembre%20-%20C.docx
:) .... es cierto que por cada rayita hay un camino, pero no vi muy claro porque representa un posible camino. Mejor dicho, la explicación es confusa. Podrías haber escrito, por cada rayita contamos el camino en que se da la vuelta entera y seguimos el siguiente caso con rayita...o algo asi, pero si esta bien n_n
Borrarme falta sacar el otro caso, tengo la idea pero no se como interpretarlo :l,
ResponderBorrarhttp://www.facebook.com/photo.php?fbid=4651522210291&set=a.4586100454788.189149.1360331970&type=3&theater
perdon por tardar, esta fuemi semana de examenes :S
Borrarhttp://www.facebook.com/photo.php?fbid=4651522210291&set=a.4586100454788.189149.1360331970&type=3&theater
Esta bien esa parte, pero los 2 enlaces son iguales o que onda? solo pude ver el caso del 1 en la orilla, donde esta todo lo demás? jaja xD
Borrarjajajajajajaja no me habia dado cuenta O.o jajajajaja
Borrarperdon karina es este
http://www.facebook.com/photo.php?fbid=4668005542364&set=a.4586100454788.189149.1360331970&type=3&theater
Creeeo que esta bien... bueno, hay que definir bien eso de la paridad, es cierto que se eliminan la mitad de los cuadros... pero no todas las columnas... aunque se tenga la misma paridad en una columna se puede poner el 2n en uno de los cuadros.... creo que solo es cuestión de explicar eso de la paridad n_n
Borrardividire el problema en dos casos.
ResponderBorrarCASO 1: El numero 1 esta en una de las 4 esquinas.
Es facil ver que si esta puesto el uno, y para donde sea que pongamos el numero 2 los demas numeros no podran estar en la otra fila, ya que lo que queda del otro lado de la cuadricula se dejaria sin utilizar.POdran estar en la otra fila, hasta que lleguen a una de las orillas y ahi den la vuelta; es mas facil analizar esto si imaginamos que hay una linea que recorre el camino formado por los numeros. Sabiendo esto es facil ver que en este caso solo hay 8 posibles acomodos(4 esquinas posibles para el uno por los 2 caminos diferentes que puede tomar).
CASO 2:El uno esta en cualquier casilla excepto las 4 esquinas.
Me fijo que escogiendo el lugar del 1 y el lugar del numero 2n, quedara definido los demas numeros,(ya que solo hay un camino en el que la linea pase por todos los cuadros hasta llegar al 2n).Entonces el 1 tiene 2n-4 posibilidades, y para el 2n, si numero las columnas del 1 hasta n, si el 2n esta en la misma fila que el 1, el 2n no podra estar en las columnas que tengan la misma paridad que la columna en la que esta el uno. Y si el 2n esta en la otra fila no podra estar en las columnas que tengan la misma paridad que la columna en la que esta el 1, y tampoco podra estar en la casilla que queda frente al 1. Esto es n-1 posibilidades. Entonces en este caso son (2n-4)(n-1).
Por lo tanto las maneras en que se puede acomodar son
8+(2n-4)(n-1).
Una disculpa el caso 1 esta mal, el caso 1 es viendo que el 1 tiene 4 posibles lugares, y usando el mismo argumento que en el caso 2 de que el 2n no puede estar en las columnas de la misma paridad que la columna en que esta el uno y eso,el 2n tiene n posibles.(es n y no n-1 porque ahora el 2n si puede estar en la casilla frente a la casilla en que esta el uno. Entonces este caso es 4n. y el total de acomodos son $4n+(2n-4)(n-1)$
BorrarFalta explicar porque solo hay un camino para un 1 y 2n definidos y porque el lugar de 2n depende de donde este el 1
Borrarhttp://www.facebook.com/photo.php?fbid=389248367813650&set=a.389248274480326.91304.100001854706497&type=3&theater
ResponderBorrarFalta explicar porqué del 1 al 2n hay solo un camino definido, en el segundo caso 2n no tiene n posibles opciones de donde colocarse
BorrarTenemos una cuadrícula de $2$ x $n$, llamaré a la primer fila: $A$ y a la segunda fila: $B$ y a las columnas las numeraré desde $1$ hasta $n$ de izquierda a derecha, esto para manejar coordenadas. En todo momento comienzo colocando el $1$, luego el $2$, ..., hasta el $2n$.
ResponderBorrarVeamos primero lo que sucede cuando no estamos en alguna esquina.-
Si estamos en $A$ y bajamos directamente hacia $B$ no podremos colocar los números consecutivos en ambos lados, por lo que la tabla no se llenará, por lo que para este caso, solo nos podemos mover horizontalmente. Digamos que estamos en $(k, A)$ donde $1 \textless k \textless n$ (pues no debemos estar en las esquinas), primero digamos que nos movemos a $((k+1), A)$, estamos obligados a movernos hasta $(n, A)$ pues no podemos regresar a la izquierda ni bajar hacia $B$ ya que solo completaríamos parte de la cuadrícula, llegando a $(n, A)$ solo podemos bajar hacia $(n, B)$ y desplazarnos hasta $((k-1), B)$.
A partir de $((k-1), B)$ podemos subir o ir a la izquierda, si nos vamos a la izquierda, solo existe un camino (continuar, dar vuelta en U y llegar a $((n-1), A)$, aquí tenemos un camino, por otro lado, si nos vamos hacia la izquierda estando en $((k-1), B)$ tendremos $2$ opciones válidas, una de ellas nos lleva a un camino ya determinado y la otra nos lleva a $2$ nuevas opciones desde $((k-2), A)$, luego sucede lo mismo, tendremos $2$ opciones desde $((k-3), B)$ , etc., hasta que llegamos ya sea a $(2, A)$ o a $(2, B)$ pero tendremos $2$ opciones finales y terminamos, tendríamos $(k-2)$ formas, pero es un argumento análogo a si desde un principio en lugar de ir a la derecha, nos vamos a la izquierda, por lo que en este último caso, serán $(n-k-1)$ formas y tendremos en total: $k-2+n-k-1=(n-1)$ formas para cualquier cuadro que no este en esquina, estos son: $2n-4$ cuadros.
Si estamos en esquina, sucede lo mismo, solo que solo tendremos una forma de más pues nos quitamos la restricción de no poder bajar o subir y no poder cubrir alguna parte de la cuadrícula, se tienen entonces $n$ formas en cada esquina y se tienen $4$ esquinas, de aquí que el resultado es:
$\boxed{(2n-4)(n-1)+4n}$
OwO owww que bonita redacción!! muy claro jeje n_n ... :)
Borrarprimero me fijo que 1,2 y 2n,2n-1 deben estar en un mismo cuadro ya que 1 t 2n no tienen otro numero consecutivo, por lo tanto deben estar cada uno en uno de estos grupo, en cada cuadrado hay 4 posibilidades y para el siguiente numero solo hay dos por lo tanto teemos 8 posibilidades por cuadro y existen n-1 cuadros entonces hay 8n-8 posibilidades para el 1,2 y para el 2n,2n-1 quedan n-2 cuadrados y otros caso mas que es el de el cuadrado donde estan el 2 y el 1 pero en este solo hay dos posibilidades el permutar el numero, en tonces hay 8n-16+2 casos donde se acomodan 2n, 2n-1
ResponderBorrarEsto no me queda claro
BorrarRumbo al nacional
ResponderBorrarEsta bien, pero falta explicar porqué hay n-1,n-2... acomodos dependiendo de donde estas iniciando.
BorrarTenemos 2 lineas y n columnas. Para trabajar con coordenadas, sean las filas X y Y, y las columnas 1,2,...,n.
ResponderBorrarPrimero nos fijamos en el caso en el cual el 1 está en alguna de las esquinas. El 2 tiene dos posibiidades: cambiar de columna, o de linea. Si se va a la siguiente columna, todo el "camino" ya está definido, ya que tendrá que completar la misma línea, y podrá cambiar hasta la siguiente esquina de la fila donde está el 1, para después completar toda la otra,l línea. Si cambia de línea, el 3 ya está definido, pero hay 2 posibilidades para el 4: que esté a un lado o que esté abajo o arriba del 3. Luego, repetimos este proceso y nos fijamos que se forma una especia de zig-zag, y en el momento en el que se quiera cortar, ya queda definido todo lo demás, ya que primero se debe completar la fila en la cual se "cortó" el zig zag, para después cambiar de línea hasta el extremo contrario al 1, y por último terminar dicha línea. El zig zag se puede cortar en cualquier momento entre las columnas 1 y n-1. Luego, hay n-1 posibilidades, más la cual en la que no se hace zig zag, sino que se completa la fila del 1, se cambia de fila en el extremo contrario y se completa la otra fila, con lo cual nos quedan n posibilidades para cada esquina, y en total 4n.
Nos fijamos en el caso en el cual el 1 no está en una esquina. Digamos que está, SPDG en las coordenadas (X,k) con 2 menor o igual a k menor o igual a n-1.
Podemos ver que el 2 sólo puede estar en la fila X, ya que si estuviera en Y, todos los cuadritos de alguno de los dos lados de la "barrera" que se formaría quedarían bloqueados. Luego, el 2 está en la misma fila, y se podrá pasar a la otra fila hasta llegar a alguna de las dos esquinas de la fila donde está el 1, dígase la (X,1) ó (X,n), pero veremos sólo el caso en el cual empezamos a la derecha, ya que el otro caso es análogo. Luego, después de esto, el "camino" queda definido hasta llegar de nuevo a la columna k. Al llegar a la columna siguiente de donde está el 1, ó la k-1 se nos presenta el mismo caso que si fuera una cuadrícula de k-1, dónde el primer número está en una esquina, para lo cual ya sabemos que hay k-1 posibilidades. Ahora vemos que las posibilidades para (X,r) empezando hacia la izquierda son las mismas que las de (X,n-r) empezando hacia la derecha. Luego al sumar las posibilidades de todos los casos en los que 1 está en la fila X, y no está en las esquinas será igual a 2 veces la suma de lo mismo pero empezando siempre hacia un sólo lado. Podemos ver que esto será igual a la sumatoria desde k=2 hasta n-1 de k-1, o lo que es igual, la suma desde 1 hasta n-2, lo cual es igual a (n-2)(n-1)/2, pero como ya habíamos visto, esto se multiplica por dos para el total de posibilidades de toda la fila X, con lo cual nos queda (n-2)(n-1). Por último nos fijamos en que el caso donde el 1 está en Y es análogo, por lo tanto en total tenemos 2(n-2)(n-1) posibilidades. Por último sólo le sumamos los casos de las 4 esquinas con lo cual el total nos queda 2n^2-2n+2=2(n^2-n+1)
Que bonita solución, esta bien... bueno.. yo le daría 7 a pesar de que hiciste la última suma mal, debería quedarte 2(n^2-n+2) jeje ... :)
BorrarPrimero me fije en que habia 3 formas de llenarlo cuando empiezas desde una esquina. Con zigzag, con linea recta o combinado. Cuando escoges combinado empiezas con zigzag y luego cambias a linea. Una vez que cambias a linea ya no puedes regresar.
ResponderBorrarLuego lo separe por casos
Caso 1: Cuando 1 esta en la esquina
Me fije en que si estamos usando zigzag y acabas de ir hacia arriba o hacia abajo, el proximo movimiento sera hacia la izquierda o la derecha y sera lo mismo iniciar la linea desde cualquiera de esos 2 cuadros. Entonces la linea puede iniciarse desde $n$ lugares. Por lo tanto hay $4n$ acomodos posibles cuando el 1 esta en la esquina.
Caso 2: Cuando 1 no esta en la esquina.
Cuando $1$ no esta en la esquina tiene $2n-4$ lugares para empezar. Luego, pinte los caudros como si fuera tablero de ajedrez. Me fije en que $2n$ no puede estar en un cuadro del mismo color que $1$ porque $1$ es impar y $2n$ es par. Entonces si escogemos donde estara $2n$ solo habra un camino que deje a $2n$ ahi. Como $2n$ tiene $n$ lugares para escoger, el total de acomodos con el caso 2 es $(2n-4)(n)$
Total de formas de acomodar=$4n+(2n-4)(n)$
Bueno, vass bien.. pero no está completo, falta explicar bien algunas cosas, por ejemplo, por qué no puedes hacer zig zag una vez que inicias una línea, por qué solo hay un camino desde 1 hasta n, y hay un errorcito en eso de que en el segundo caso tienes n lugares para escoger a 2n.
BorrarLa demostración de que 2n no puede estar en ciertas casillas con coloración esta muy bonita, bastante clara jeje ... pero falta terminar esos detalles que te puse n_n
lo dividire en dos casos:
ResponderBorrarcaso uno empesamos en una de las cuatro esquinas
me fijo que en esa tenemos dos opciones o cambiarnos de fila o cambiernos de columna entonces si nos cambiamos de columna vamos a tener que completar esa fila porque si bajamos no podremos llenar la esquina q estaba debajo de la que empesamos, y la otran manera que si cambiemos de fila nomas vamos a tener una opcion para el siguiente movimientos y luego vamos a tener dos opciones o a un lado o vertical y asi sucesivamente pero me fijo en que si en una de esas elegimos irnos a un lado todo el camino ya va a estar definido por el mismo argumento q usamos en el primer subcaso entonces en este subcaso tenemos la opcion de irnos totalmente en zig-zag o de en cada dos cuadritos escoger el irnos a un lado entonces tenemos las posibilidades de n-1 de elegir irnos a un lado y mas el caso de irnos totalmente en sigsag pero como tenemos 4 esqinas vamos a tener 4n maneras para el primer caso
caso 2 empesamos en un lugar q no sea esqina
nos fijamos que no podemos empesar verticalmente porque si no no podriams rellenar algunnoos cuadro entonces solo podemos de dos opciones a isquierda o derecha y aplicamos el mismo argumento de que se va a tener que llenar casi toda esa fila osea si empesamos a la derecha vamos a tener que llenar todo el lado derecho de esa fila hasta que toopemos y vamos a tener que llener todo el lado derecho de la fila de abajpo pero cuando llegemos a la misma columna de donde empesamos pero claro que vamos a estar en la fila distinta y despues va a ser como si tuvieramos un tablero mas pequeño y vamos a aplicar los mismos argumentos que en el caso 1 entonces solo vamos a tener las dos opciones d3 derecha o isquierda luego ya sabemos q si empesamos en la columna k vamos a tener que llenar 2n-2k cuadritos y ya sabiamos q eso se podia de n-k form,as entonces podemos ver que como la cuadricula es de cantidad para va a pasar los mismo de un lado que en el otro y vamos a poner ka para cada uno de los caso entonnses ba a ser la suma de los numeros desde 1 hasta n-2 pero como se refleja entonces la formula va a ser ent total
$\frac{2x2(n-2)(n-1)}{2}+4n=4n^2-2n+4$
jaja esta muy bien!!!! ... peeero... la última operación te quedó mal jaja ... debería quedarte 2n^2-2n+4 ... esa algebraaa jaja xD ... :)
Borrar