Autor Tema: Problema interesante de combinatoria

0 Usuarios y 1 Visitante están viendo este tema.

14 Diciembre, 2007, 08:27 pm
Leído 2294 veces

juanmaflyer

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 13
  • Karma: +0/-0
  • Sexo: Masculino
Hola gente, les quiero dejar un ejercicio de parcial del cual tengo la respuesta y está como bien, pero yo llegue a otro resultado y creo que el mio es el correcto. A ver si me rectifican. Ahi va el enunciado:

Citar
Un empleado olvidó su clave de acceso a la base de datos de la empresa en la que trabaja. De ella recuerda que tenía 8 caracteres: 4 letras y 4 dígitos y que ademas:

Había una A entre las letras, figuraban la R y la S, juntas y en ese orden, los dígitos de la clave iban del 0 al 6 y había exactamente una letra o dígito repetido.

Hallar la cantidad de posibles combinaciones de letras y números bajo las condiciones dadas


BIEN, yo tengo que la respuesta correcta (según la corección del parcial) es 6.626.800.

Pero yo llego al siguiente resultado: 6.615.000

Espero que me ayuden, gracias. Consideren si no les molesta 26 letras ya que yo hice el ejercicio con ese resultado.



14 Diciembre, 2007, 09:56 pm
Respuesta #1

Jabato

  • Visitante
Como siempre tenemos un enunciado mal escrito para variar.

¿Cuales son las posibles letras?

a).- Solo mayúsculas ó pueden entrar también las minúsculas.

Nota.- La Ñ, la W y la Ç. Las tres aparecen en un teclado español, eso nos conduciría a 28 letras posibles, aunque consideraré 26 letras mayúsulas, es lo que parece que dices en el enunciado.

Bien, consideremos el conjunto de letras incluidos en la clave {A, RS, x}. x representa la cuarta letra para la que se admiten 26 valores posibles ya que puede estar repetida.

1º Admitiendo que es la letra la que está repetida podemos decir entonces que x solo presenta tres valores posibles, luego solo existen tres "conjuntos" posibles para las letras:

{A, RS, A}     {A, RS, R}    {A, RS, S}

Nota: No son conjuntos propiamente dichos ya que el primero tiene un elemento repetido, lo que no sería admisible para conjuntos.

En este caso los dígitos no pueden estar repetidos luego existen \( {\bold{7}\choose \bold{4}} \) posibles conjuntos de números incluidos en la clave {a, b, c, d}, que serían las combinaciones de 7 elementos tomados de 4 en 4.

Haciendo ahora todas las posibles uniones de uno de los primeros y otro de los segundos veríamos cada uno de los conjuntos de caracteres posibles para formar la clave. Las permutaciones de cada uno de esos conjuntos serían una posible solución, ahora bién existe un detalle tático que no debemos pasar de largo, uno de los conjuntos de caracteres tiene un elemento repetido y las permutaciones cuando ese conjunto interviene en la solución se deben calcular en forma distinta que en los otros dos casos.

2º Admitiendo ahora que es el dígito el que se repite tendremos que los posibles conjuntos de caracteres son 23, ya que el último caracter solo puede adoptar 23 valores al no poder repetirse.

En este caso los conjuntos posibles para dígitos son, teniendo en cuenta que uno debe repetirse, \( 3{\bold{7}\choose \bold{3}} \) ya que para cada combinación de los 7 dígitos tomados de 3 en 3 se generará 3 combinaciones que seran las obtenidas al repetir uno de estos dígitos.

En este caso el detalle tático comentado no se produce para las letras, pero sí se produce para los números y en todos los casos, hecho que debemos tener en cuenta a la hora de calcular las permutaciones posibles.

Una vez analizados todos los casos posibles basta solo realizar cada una de las uniónes de un conjunto de letras con un conjunto de números y calcualr las permutaciones que pueden realizarse con sus elementos, teniendo en cuenta claro los casos en que alguno de los caracteres aparecerá repetido.

Teniendo en cuenta que:

\( {\bold{7}\choose \bold{4}}=35 \)                  \( 23\cdot 3\cdot {\bold{7}\choose \bold{3}}=2415 \)

tenemos:

Para el primer caso:

35 conjuntos del tipo {A, RS, A, a, b, c, d} que generan P permutaciones distintas cada uno.

35 conjuntos del tipo {A, RS, R, a, b, c, d} que generan 7! permutaciones distintas cada uno.

35 conjuntos del tipo {A, RS, S, a, b, c, d} que generan 7! permutaciones distintas cada uno.

Para el segundo caso:

2415 conjuntos del tipo {A, RS, x, a, a, b, c} que generan P permutaciones distintas cada uno.

Basta calcular ahora las permutaciones distintas en cada caso y sumarlas todas para obtener el resultado buscado.

En el primero y último tipo la fórmula a aplicar para el cálculo de las permutaciones, P, será idéntica ya que deben calcularse las permutaciones posibles con 7 elementos, sabiendo que uno de ellos es repetido. En los otros dos casos son las permutaciones de 7 elementos distintos sin más, 7!.

La solución vendría dada por la expresión:

(35 + 2415)P + 2·35·7! = 2450·P + 352800

Disculparme si no acabo la cosa, no tengo tiempo. Solo me queda calcular P. Si el valor de P resultara ser 2556 tu solución sería la correcta, pero la solución que dices os dieron del parcial nunca podría ser la correcta puesto que, de acuerdo a mi cálculo, debería ser:

P = (6626800 - 352800)/2450 = 2560,8...

y es imposible que P tome un valor fraccionario.

¡Ojo! que yo también puedo equivocarme.

Saludos, Jabato.

14 Diciembre, 2007, 10:53 pm
Respuesta #2

Jabato

  • Visitante
Bueno, parece que tengo un momento para calcular el valor de P, siguiendo con mi mensaje anterior. P era el número de permutaciones distintas que pueden hacerse con 7 elementos sabiendo que uno es repetido.

Para razonar la solución nos basta ver que cada permutación de los 7 elementos admite otra idéntica que se obtiene al intercambiar los dos elementos iguales, por lo que resulta que:

P = 7!/2 = 2520

lo que nos lleva a que la solución correcta es:

N = 2450·P + 352800 = 6526800

No sabes como siento tener que quitaros la razón a los dos, a tu catedrático y a ti. Una lástima.

Saludos, Jabato.

15 Diciembre, 2007, 03:06 am
Respuesta #3

juanmaflyer

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 13
  • Karma: +0/-0
  • Sexo: Masculino
Muchas gracias por tu completa respuesta, sinceramente todavía no comprendo tus explicaciones pero buen, voy a seguir leyendo.

A ver, te cuento lo que hice yo a ver si me podés decir cual es el error o que casos estaría contando demás, YA que me dio un numero mas grande que el tuyo.

Caso en el que el carácter que se repite sea una letra:

\( \displaystyle\binom{7}{1}.\displaystyle\binom{6}{1}.\displaystyle\binom{5}{1}\cdot \,3\,\cdot 7\,\cdot 6\,\cdot 5\,\cdot4\, \)

El \( \displaystyle\binom{7}{1} \) para elegir donde colocaré la A entre los 7 lugares que tengo.

El \( \displaystyle\binom{6}{1} \) para elegir donde colocaré mi conjunto  RS entre los 6 lugares restantes.

El \( \displaystyle\binom{5}{1} \) para elegir donde colocaré mi letra repetida entre los 5 lugares que tengo. Multiplico luego por 3 porque son 3 las posibilidades que tengo de elegir esas letras que son A R o S

Y luego elijo el \( \displaystyle\frac{7!}{3!} \) que serían los posibles números que puedo colocar en los 4 carácteres restantes

Caso en el que el carácter que se repite sea un número

\( \displaystyle\binom{7}{1}.\displaystyle\binom{6}{1}.\displaystyle\binom{5}{1}\cdot \,23\,\cdot \displaystyle\binom{4}{2}\cdot \,7\,\cdot 6\,\cdot 5 \)

El \( \displaystyle\binom{7}{1} \) para elegir donde colocaré la A entre los 7 lugares que tengo.

El \( \displaystyle\binom{6}{1} \) para elegir donde colocaré mi conjunto  RS entre los 6 lugares restantes.

El \( \displaystyle\binom{5}{1}\,23 \) para elegir mi la letra restante (DE LAS CUALES TENGO 23 POSIBILIDADES)

El \( \displaystyle\binom{4}{2} \) para elejir 2 LUGARES entre 4 que me quedan en los cuales colocaré mis 2 dígitos iguales. Tengo 7 dígitos posibles para elegir.

Luego \( \displaystyle\frac{6!}{4!} \) las combinaciones que puedo lograr con 6 números en los 2 lugares que me quedan.


Calculando los 2 casos y sumándolos obtengo lo siguiente:


\( \displaystyle\binom{7}{1}.\displaystyle\binom{6}{1}.\displaystyle\binom{5}{1}\cdot \,3\,\cdot 7\,\cdot 6\,\cdot 5\,\cdot4\,=529200 \)


\( \displaystyle\binom{7}{1}.\displaystyle\binom{6}{1}.\displaystyle\binom{5}{1}\cdot \,23\,\cdot \displaystyle\binom{4}{2}\cdot \,7\,\cdot 6\,\cdot 5=6085800 \)


\( 529200+6085800=6615000 \)

Para mi no estoy omitiendo ni contando casos demás.




15 Diciembre, 2007, 05:29 am
Respuesta #4

Jabato

  • Visitante
Comparando tu solución y la mia resulta que ambos obtenemos el mismo resultado para el segundo caso, es decir cuando suponemos que es un número el caracter que se repite, pero no obtenemos el mismo resultado en el primer caso, cuando es una letra la que se repite.

Creo que el error estriba en que duplicas las permutaciones cuando el caráter repetido es el A, me explico, primero consideras 7 casos para colocar la primera A en los 7 lugares posibles, y luego multiplicas por 5 debido a los 5 lugares en que puedes colocar la letra repetida, y ahí cometes un error porque cuando la letra repetida es la A estas duplicando combinaciones. Curioso que no cometes el error en el caso en que se repiten los dígitos, porque haces dicho cálculo en forma distinta, con las combinaciones de los 4 lugares tomados de 2 en 2, y de esa forma no repites combinaciones.

Deberías distinguir si la letra repetida es la A ó no y hacer el análisis independientemente.

Saludos, Jabato.

20 Diciembre, 2007, 12:11 am
Respuesta #5

juanmaflyer

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 13
  • Karma: +0/-0
  • Sexo: Masculino
Muchas gracias por rectificarme. Entiendo ese caso que planteas cuando la letra repetida es la A. Lo voy a hacer de nuevo como vos decís.