Sea
viernes, 5 de octubre de 2012
Problema del día. Combinatoria (5 de Octubre)
Resolver con inducción el siguiente problema:
Sean 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?
Sea
Suscribirse a:
Comentarios de la entrada (Atom)
*En la solución cuando menciono: "el problema anterior" me refiero al Problema del Día del 21 de Septiembre.
ResponderBorrarComenzamos la inducción, lo que queremos demostrar es la fórmula: $2(n^{2}-n+2)$ que se obtuvo en el problema anterior
Caso base.-
$n=1\Rightarrow 2(n^{2}-n+2)=2(1-2+2)=2$ lo cual es facil ver que es cierto.
Para la inducción, agregaremos una columna, por lo que se agregan acomodos, veamos cuantos se agregan
Veamos los acomodos que se agregan en cada caso.-
$\bullet$ Cuando iniciamos en alguna casilla no agregada y no esta en alguna esquina.- Por el problema anterior, solo estamos agregando un acomodo para cada una de estas casillas, si se tienen $2n-4$ casillas de este tipo, estamos agregando $2n-4$ acomodos para este caso, el argumento era que la cantidad de acomodos desde una casilla que no esta en esquina, es igual a la suma de la cantidad de columnas a su derecha y a su izquierda, como agregamos una columna, sumamos $1$ acomodo a cada casilla.
$\bullet$ Cuando iniciamos en alguna esquina.- Por el problema anterior se agrega $1$ acomodo para cada esquina, son $4$ esquinas, por lo que se agregan $4$ acomodos.
$\bullet$ Cuando iniciamos en alguna casilla agregada.- Por el problema anterior, ambas casillas agregadas tendrán $n+1-1=n$ acomodos, el argumento era que la cantidad de acomodos desde una casilla que no esta en esquina, es igual a la suma de la cantidad de columnas a su derecha y a su izquierda, es decir $(n+1)-1=n$ acomodos.
En total se agregaron: $2n-4+4+2n=4n$ acomodos.
Para terminar la inducción se debe cumplir que la proposición para $n$ mas los acomodos agregados, sea igual a la proposición para $n+1$:
$2(n^{2}-n+2)+4n=2((n+1)^{2}-(n+1)+2)$
Expandimos:
$2n^{2}-2n+4+4n=2n^{2}+4n+2-2n-2+4$
$\Rightarrow 2n^{2}+2n+4=2n^{2}+2n+4$ lo cual es cierto. Q.E.D.
Este comentario ha sido eliminado por el autor.
ResponderBorrarQueremos demostrar que el resultado es $2n^2-2n+4$.Primero el caso base me fijo que para n=2 deberia haber $2(2)^2-2(2)+4=8$ y nos fijamos que si hay una cuadricula de 2*2 entonces las posibilidades son para escoger la primera casilla hay 4 posibles, y para escoger la que sigue hay otras 2, y para las demas ya queda deginido, entonces son 4*2=8 acomodos. Por lo tanto el caso base cumple.
ResponderBorrarLuego supongamos que cumple para k, entonces para n=k hay $2k^2-2k+4$ acomodos.Entonces veo que para k+1 hay que demostrar que hay $2(k+1)^2-2(k+1)+4=2k^2+2k+4$. entonces demostrar que eso se cumple es como demostrar que del tablero de k al tablero de k+1 se aumentan 4k acomodos.
Entonces lo vere por casos:
Veo que en el tablero de 2*k+1 se agrega una columna de 2*1 en relacion al tablero para k. Entonces en el pirmer caso cuando iniciamos en alguna casilla agregada, veo que pueden ser dos y estas estan en una esquina y por el argumento usado en el otro problema del 21 de septiembre estos son 2*2=4 acomodos mas, aun no puedo contar los acomodos q se agregan al agregar la columna que no sea en la esquina.Luego subo demas intentos
tienes que por el otro problema tienes que la base de induccion es $1$ y tienes que $2(2^2-2+2)=8$ entonces tienes que para n se cumple que $2(n^2-2n+2)$ entonces para $n+1$ deben de cumplir y tienes que $2((n+1)^2-(n+1)+2)=2(n^2)+2-2n-2+4=4n^2-2n+4=2n^2+2n+4$ y por eso tienes que aumenta en $4n$ tienes que se agrega una fila de $2(1)$ y eso hace que las esquinas siguan siendo las misma cantidad y ahora tienes que para elegir de los demas lados ahora tienes $2n-2$ opciones para colocarlo
Borrary bueno hasta ahi voy mañana la termino o mas tarde
(Antonio) Ok, esta bien lo que dices... aunque al final esta un poco reborujado, tu puedes decir donde agregar la columna en tu inducción, ya solo sería ver cuantos casos más se agregan al empezar en cada cuadro.
Borrar(Alberto) Esta bien, pero procura ser más explicito, en realidad no "tienes" que se cumple para n, "supones" que se cumple y quieres demostrar para n+1, a veces si quienes te revisan no entienden que estas haciendo puedes perder puntos asi que procura ser claro con las ideas :3
BorrarBase: $2n^2-2n+4=2(n^2-n+2)$
ResponderBorrarQue es lo obtenido en el otro problema.
Vemos que cumple para $2$ :
$2(n^2-n+2)=2(2^2-2+2)=2(4)=8$
Cada uno de los caminos, se hace tomando cualquiera de los cuadros, y hacer el camino para cualquiera de los lados, son $2$ caminos por cuadro.
Entonces debemos demostrar que cumple para $n+1$ , siendo la respuesta:
$2((n+1)^2-(n+1)+2))=2(n^2+2n+1-n+1+2)=2(n^2+n+2)$
Vemos la diferencia de caminos entre $n$ y $n+1$ .
$2(n^2+n+2)-2(n^2-n+2)=4n$
Entonces debemos ver que al cambiar el tablero de $n$ a $n+1$ , se pueden hacer $4n$ caminos más.
Como había dicho en el otro problema, cuando se hace cierta cantidad de vueltas y luego se sigue derecho esta dar una vuelta en $\text{U}$ , representa un posible camino. Entonces cuando el $1$ no esta en esquina, se agrega un camino para cada cuadro, es decir $4n-4$ , porque son $2n-2$ , pero se cuenta doble porque el $2$ se puede poner a la derecha o izquierda.
Cuando se pone en esquina, hay $4$ caminos, que es una vuelta posible más para cada cuadro.
Al sumar los dos casos, tenemos $4n$ caminos, que es lo que buscabamos. $\blacksquare$
Lo primero esta bien, o ultimo no lo entendí n_n
BorrarA partir de donde es lo último?
BorrarEl ultimo parrafo
Borrarprimero me fijo en el caso baso que segun la formula tendrian que ser 2 formas y sabemos facilmente que si es cierto, entonces veamos cuantos caminos se vana agrgando cuando $n$ aumenta en 1.
ResponderBorrardigamos que originalmente el tablero era de $n*2$ y ahora tenemos uno de $(n+1)*2$ entonces sabiamos que en el tablero de n*2 empesabamos en una esquina ibamos a tener n formas de hacerlo, entonces en el nuevo vamos a tener n+1 formas de hacerlo pero como son 4 esquinas vamos a tener 4n+4 formas.
si en el tablero de n*2 empesabamos en un lugar que no fuera esquina teniamos $2(n-2)(n-1)=2n^2-6n+4$ maneras y el argumento era que no podiamos empesar verticalmente si no que solo se podia horisontal y que si empesabamos en la columna k ibamos q tener que llenar 2n-2k cuadritos y sabiamos que eso se podia aser de n-k cuadritos y sabiamos que cada "subcuadricula" se reflejaba y se tenia que contar dos veses y por eso era $\frac{(n-2)(n-1)}{2}$ entonces en el nuevo solamente se va a agregar 2 veces el subtablero de (n-1)2 entonces solo se van a agragar 2n-2 maneras.
entonces como ya sabemos cuanto se agrego de cada caso solo ponemos la induccion:
suponemos que para n se cumple entonces las maneras son $2n^2-2n+4$
entonces para n+1 solo hay que demostrar que :
$2n^2-2n+4+(2n-2+4)= \frac{2*2(n-1)n}{2} +4n+4$
y eso es lo unico que llevo
ok, eso esta bien, aunque lo de subtablero me parece confuso
BorrarQueremos demostrar la fórmula $2(n^2-n+2)$. Consideramos las formas de trazar la línea de 1 a 2n.
ResponderBorrarCaso base: n=2. Vemos que partiendo de cualquier vértice hay dos formas y hay 4 vértices, entonces hay 8 formas y $8=2(2^-2+2)$, entonces es cierto.
Supongamos que es cierto para k.
Ya había demostrado que para cada posición del 1 había una forma por cada columna distinta de en la que está en 1 (para las columnas de en medio), entonces al agregar la columna k+1, se agregan 2k caminos, y agregamos los 2k caminos equivalentes que solo se invierte el orden. Los caminos que ya estaban y que dan una vuelta en la orilla donde se agregó la nueva columna se conservan (solo se prolonga la vuelta), estos son todos menos 2, que son los que parten y terminan en la penúltima columna (contando la que se agregó), entonces restamos 2 caminos. También se agregan 2 caminos que parten y terminan en la nueva columna (estos simplemente dan la vuelta por la cuadrícula sin zigzagear).
Si para k hay $2(k^2-k+2)$ formas, por esto para k+1 hay 2(k^2-k+2)+2k+2k-2+2=2(k^2-k+2+2k)=2(k^2+2k+1-1-k+2)=2((k+1)^2-(k+1)+2$ que es lo que buscábamos.
Como si se cumple para k se cumple para k+1, y como se cumnple para 1, se cumple para toda n.
http://s739.photobucket.com/albums/xx34/leo0_9506/Ommch/?action=view¤t=CAM001481.jpg
ResponderBorrarExlica que es una casilla agregada, donde esta esa casilla?
Borrar