Cual es la mayor cantidad de fichas que puede haber en una hilera?
Cuantas hileras de esa longitud maxima se pueden construir?
martes, 27 de septiembre de 2011
problema del dia (combinatoria) 27/09/11
Una ficha de domino tiene 2 numeros (no necesariamente diferentes), entre 0 y 6. Las fichas se pueden voltear, es decir (4-5) es la misma que (5-4). Se quiere formar una hilera de fichas de domino distintas de manera que en cada momento de la construccion de la hilera, la suma de todos los numeros de las fichas puestas hasta ese momento sea impar. Las fichas se pueden agregar de la manera usual a ambos extremos de la hilera, de manera que en cualesquiera 2 fichas consecutivas aparezca el mismo numero en los extremos que se juntan. Por ejemplo, se podria hacer la hilera (1-3)(3-4)(4-4), en la que se coloco primero la ficha del centro y luego la de la izquierda. Despues de poner la primera ficha, la suma de tdos los numeros es 7, despues de poner la segunda es 11, despues de la tercera 19.
Suscribirse a:
Comentarios de la entrada (Atom)
bueno en total tenemos 49 fichas porque son 7 los numeros que podemos escoger :1,2,3,4,5,6,0
ResponderBorrary tenemos que hay 25 ficha que suman un numero par y 24 que suman un numero impar porque
y luego me fijo que como 5-4 es igual a 4-5 pues le quito la mitad pero antes de eso le quito mlas mulas porque esas no tienen fichas "clones" y pues solo hay 7 mulas y pues 49-7=42 y ahora si divido 42/2=21 y a 21 le sumo las siete fichas que abia quitado y 21+7=28 eso significa que tenemos 28 fichas unicas de las cuales 16 son pares y 12 pares
me fijo que para que siempre la ilera tenga una suma impar tiene que aber almenos una ficha impar pero no puede aber un numero par de fichas impares porque sino toda la suma seria par
entonces la cantidad de fichas pares en la ilera no importa sino la de fichas impares y aqui respondo a la primera pregunta
la mayor cantidad de fichas que puede aber en una ilera es (12-1)+16=27 el 12-1 es porque como tenemos que siempre debe aber una cantidad impar de fichas impares pues solo le resto 1 y el 16 porque pues tenemos 16 fichas pares y esas no las modificamos porque no afectan y entonces tenemos que maximo puede haber 27 fichas en una ileray la otra pregunat aun no la termino pero seguire intentado
hay 28 fichas distintas porque el 6 se puede combinar con 7 numeros, el 5 podra ya solo con 6, el 4 con 5 y asi sucesivamente y nos quedan 7+6+5+4+3+2+1=28. como nos dicen que siempre la suma debe ser impar la primer ficha debe tener un numero par y otro impar y tambien que en los extremos de dos fichas debe haber 2 numeros iguales entonces cuando empecemos a poner fichas a partir de donde esta el numero impar habra puras fichas con puros numeros impares y igual con el extremo del numero par habra puras fichas con numeros pares. como hay 28 fichas hay 56 numeros y hay 8 de cada uno y voy a restar a las 28 fichas las fichas que contengan un numero par y otro impar que son 12 entonces podra haber como maximo 28-12=16 fichas y le agrego una porque es la que va al principio y nos quedan 17 fichas como maximo en una hilera.
ResponderBorrarla otra pregunta seguire intentandola
Este comentario ha sido eliminado por el autor.
ResponderBorrarEste comentario ha sido eliminado por el autor.
ResponderBorrarla primer ficha debe sumar una cantidad impar, entonces uno de los numeros es par y el otro impar
ResponderBorrarde las otras fichas como la suma debe seguir siendo impar, o ambos son pares o ambos impares
primero vemos que las mulas no afectan como ponemos las fichas con numeros diferentes, entonces estas las consideramos al final
elegimos con cual de las fichas que tienen un par y un impar vamos a empezar, que hay $4 \times 3=12$ fichas, ya que hay 4 pares y 3 impares, denominamos a estos dos numeros como $p_1$ e $i_1$
ahora vemos que hay 3 fichas con dos impares diferentes, y hay 2 maneras de ponerlas: $(i_1,i_2)(i_2,i_3)(i_3,i_1)$ y $(i_1,i_3)(i_3,i_2)(i_2,i_1)$
hasta aqui vemos que podemos usar 4 fichas
hay $\binom{4}{2}=6$ fichas con dos pares
vemos las fichas como un grafo de 4 vertices, cada uno con una arista a los otros, y queremos hacer un camino que pase con la mayor cantidad posible, como cada vertice tiene 3 aristas, no se puede pasar por todos, pero si se puede pasar por 5, y vemos que hay 6 caminos diferentes que podemos tomar fijando cual es vertice final del camino (el inicial ya lo sabemos)entonces podemos formar una hilera con 3+1+5=9, mas las 7 mulas = 16 fichas
para ver cuantos hileras diferentes hay:
multiplicamos cuantas fichas iniciales se pueden (12), por los caminos que tienen los impares (2), por los caminos que tienen los pares (6), por cual de los pares podemos fijar para terminar la hilera (3)
para acomodar las mulas vemos que las del impar de la ficha inicial tiene dos opciones, al principio y al final de la hilera de impares, y las otras dos mulas de impares tienen una sola opcion, entonces multiplicamos por 2
para las pares, vemos que las que no son el principio ni al final tienen una opcion para poner la mula, y las otras dos tienen dos opciones, y multiplicamos por 2x2
Total: $12 \times 2 \times 6 \times 3 \times 2 \times 2 \times 2 = 2^7 \times 3^3$
Para que la suma sea impar al inicio, la suma de la primera ficha debe ser impar y sólo se puede lograr si tiene un par y un impar; para que se conserve la paridad se debe sumar un par, que solo se obtiene con dos pares o dos impares, como en la primera ficha hay un par y un impar y las fichas que se pueden sumar tienen dos pares o dos impares, de un lado de la primera sólo puede haber números pares y del otro impares.
ResponderBorrarHay 6 fichas diferentes con solo impares (son tres números impares, con el primer número hay 3 combinaciones, con el segundo 2 omitiendo la que está en el primero, y con el tercero hay 1), por tanto del lado de los impares hay 6 fichas.
Hay 10 fichas distintas con solo pares, excluyendo las 4 mulas, que se pueden poner en cualquier lugar donde haya una ficha con el mismo número sin alterar el orden, hay 6 fichas y cada número se repite tres veces. Como para unir dos fichas se necesita que aperzca dos veces el mismo número, hay una cantidad par de fichas con cada número, que solo puede ser 2, salvo los que tienen un número en un extremo que se repiten 3 veces. Entonces como solo dos números pueden repetirse 3 veces y los otros dos solo 2, de ese lado hay 2+2+3+3 números y por tanto 5 fichas mas las 4 mulas.
Entonces hay máximo 1+6+9=16 fichas por hilera.
El lado de los impares excluyendo a las mulas sólo se puede acomodar de la forma i1i2,i2i3,i3i1 donde los valores de i2,i3 se pueden permutar de 2 formas (i1 depende de la primera ficha y no puede cambiar), las mulas pueden ir la de i1 en 2 lugares y las de i2 e i3 en 1 cada una, por tanto hay 1x2x2 formas = 4 combinaciones.
Del lado de los pares excluyendo a las mulas, sólo puede ser p1p2,p2p3,p3p4,p4p1,p1p3 o p1p2,p2p3,p3p1,p1p4,p4p2 o p1p2,p2p3,p3p1,p1p4,p4p3 donde los valores de p2,p3,p4 se pueden permutar de 6 formas (como importa el orden es 3x2x1), la mula de p1 puede ir en 2 lugares, la de p2 y p3 uno en 2 y el otro en 1 lugares (dependiendo del acomodo) y la de p4 en 1 un lugar. Por tanto el lado de los pares se puede acomodar de 3x6x2x2 formas = 72 combinaciones.
Por tanto hay 12x4x72=3456 formas de crear la hilera.
Este comentario ha sido eliminado por el autor.
ResponderBorrarDadas las instrucciones la suma de los números de la primera ficha debe ser impar, la ficha debe contener un número par y otro impar. Para seguir cumpliendo con este requisito, solo se podrán ir adhiriendo fichas a la hilera solo si la suma de los números que contenga suman par. Y para que ocurra esto, las fichas deben contener o dos números pares o dos números impares.
ResponderBorrarComo ya se había mencionado, la ficha central debe contener un número par y otro impar, y existen $12$ fichas que cumplen con esto. De un lado de la hilera, solo se podrán poner las fichas con números impares y del otro solo las que tengan números pares.
Sin pérdida de generalidad llamaremos a la ficha central $(i_1,p_1)$.
Vemos que existen $3$ fichas con números impares diferentes, y $3$ mulas de números impares, con los números $1$, $3$ y $5$. Sin pérdida de generalidad se llaman a las fichas con números impares diferentes $(i_1,i_2)(i_1,i_3)(i_2,i_3)$. Si se toma en cuenta que la ficha central es $(i_1,p_1)$, las únicas maneras de acomodar estas $3$ fichas serian $(i_1,i_2)(i_2,i_3)(i_3,i_1)$ y $(i_1,i_3)(i_3,i_2)(i_2,i_1)$ (Comenzando con cualquier ficha que contenga $i_1$). Y en ambos casos cada mula puede colocarse en un solo lugar excepto $(i_1,i_1)$, ya que esta puede colocarse, o al inicio, o al final de la hilera. Hasta este paso llevamos utilizadas $7$ fichas, y $12 * 2 * 2$ combinaciones diferentes ($12$ fichas centrales * $2$ opciones de acomodo de fichas con números impares diferentes * $2$ opciones de posición de la mula $(i_1,i_1)$).
Vemos que existen $6$ fichas con números pares diferentes, y $4$ mulas de números pares, con los números $0$, $2$, $4$ y $6$. Sin pérdida de generalidad se llaman a las fichas con números pares diferentes $(p_1,p_2)(p_1,p_3)(p_1,p_4) (p_2,p_3)(p_2,p_4)(p_3,p_4)$. Si se toma en cuenta que la ficha central es $(i_1,p_1)$, solo sería posible utilizar a lo máximo $5$ de estas fichas. Entonces, el numero de combinaciones posibles con estas $6$ fichas está dada por $\binom{6}{5}=6$. Y sabiendo que el orden es de importancia y que debemos comenzar con una ficha que contenga $(p_1)$, existen $3$ fichas que comienzan con este número, por la tanto tenemos otras $3$ combinaciones. En cuanto a las $4$ mulas, todas tendrán $2$ opciones de acomodo, excepto las $2$ mulas que coincidan con la ficha que no se utilizara de las $6$ disponibles, estas últimas solo tendrán $1$ lugar de acomodo. A este paso, llevamos otras $9$ fichas utilizadas, y otras $6 * 3 * 2 * 2$ combinaciones mas ($6$ opciones de acomodo de fichas con números pares diferentes * $3$ opciones de ficha inicial * $2$ opciones de posición de mula * $2$ opciones de posición de mula).
La mayor cantidad máxima de fichas que puede haber en una hilera es $7+9=16$.
La cantidad de hileras diferentes con esta longitud está dada por $12 * 2 * 2 * 6 * 3 * 2 * 2 = 2^7 * 3^3= 3456$.
La fila debe comenzar con un par y un impar en la primer fila para que sume desde un principio par, y para que siga siendo par tenemos que las demas tienen que ser par en la suma de sus numeros internos, por lo que debe haber un 2 pares o 2 impares, y como tenemos que de cada lado de la ficha inicial hay un par y un impar, entonces todas las fichas con 2 impares seran de un lado y las demas del otro, tenemos que, empezando de un lado despues de la ficha inicial, comenzando con los impares, existen 3 fichas con impares diferentes que son de la forma i1,i2,i3, y se pueden acomodar como (i1,i2)(i2,i3)(i3,i1), y llendonos para el lado de las fichas de pares tenemos que son de la forma n1,n2,n3,n4, por las mulas hay 1 par mas que impar, hay 6 fichas de esta forma ya que son 4 numeros en 2 espacios, pero como en la ficha central tenemos un n1, entonces por lo menos un numero no sera posible de usar por lo que el maximo de fichas sera 5, mas las mulas que se pueden usar acomodandolas de separadores de 2 fichas, con 2 fichas de mulas entonces mas las 7 mulas hay 16 fichas que es el maximo de fichas posibles. y en la cantidad de hileras posibles aun estoy con eso, pero ahi me reporto con lo que saque.
ResponderBorrar