CyM98 << Contar sin Repetición >>
Dificultad: Computación Matemática

Se necesitan solamente conociminetos elementales de computación y de matemática.

Lecciones anteriores:

ninguna

 
Google
Web www.oma.org.ar

Resumen:

Va a ver como contar de cuantas formas diferentes se pueden elegir algunos números, pero con la condición adicional de que no aparezcan repetidos. Los vamos a contar con un programa sencillo, que además sirve para mostrar las posibles elecciones.

Introducción:

En esta lección vamos a analizar algunos trucos para contar. Muchas veces nos interesa saber de cuantas maneras diferentes se cumple con una determinada condición (o condiciones), por ejemplo al jugar a la generala, ¿es más fácil sacar generala servida o escalera servida?

Para calcular de cuantas maneras se puede sacar generala no hacen falta muchas cuentas: Puede ser generala de 1, de 2, de 3, de 4, de 5 o de 6. Además hay una sola forma de sacar generala de unos (¡todos 1!), lo mismo para el resto así que en Total hay 6 formas distintas de sacar generala.

Para calcular de cuantas formas se puede sacar escalera vamos a utilizar un programa primero y después vamos a ver una fórmula sencilla de obtener este resultado. En otros casos esta formula sencilla no existe o es tan complicada que es casi lo mismo que no existiera.

Podemos separar en dos casos :

  • La escalera del 1 al 5
  • La escalera del 2 al 6

Vamos a calcular de cuantas formas se puede obtener la escalera del 1 al 5 y como hay la misma cantidad de formas de obtener la otra vamos a multiplicar por dos.

Contando:

La primera idea es buscar 5 números A, B, C, D y E todos entre 1 y 5, y luego fijarnos que no estén repetidos.

Defint A-Z
Cls ' Borro Pantalla
Dim Tot As Long
Const Max = 5 'o 30
' Usamos una constante para que sea facil de modificar
For A = 1 To Max
  For B = 1 To Max
    For C = 1 To Max
      For D = 1 To Max
        For E = 1 To Max
          If A<>B And A<>C And A<>D And A<>E And B<>C _
              And B<>D And B<>E And C<>D And C<>E _
              And D<>E Then
            Tot = Tot +1
          End If
        Next E
      Next D
    Next C
  Next B
Next A
Print Tot

Mejoras:

Este programa es casi instantáneo y da 120 ( o sea que la cantidad de escaleras servidas es de 240), pero tiene dos defectos :

El primero es que es muy fácil cometer un error al escribir la condición, porque es muy larga y difícil de controlar. Por ejemplo la siguiente condición esta mal. Tratá de encontrar el error :

If A <> B And A <> C And A <> D And A <> E And B <> C And B <> E And C <> D And C <> E And D <> E Then

El segundo defecto es que es lento. Bueno en realidad seria lento si usáramos un número mas grande que 5, por ejemplo 30 (reemplazando la línea "Const Max = 5" por "Const Max = 30"). Esto equivale al problema de obtener 5 valores distintos al tirar "dados de 30 caras". Con numeroa asi de grandes tarda alrededor de 8 minutos, pero el tiempo se puede acortar haciendo una pequeña observación.

Para ver si A=B no hace falta esperar a que estén elegidos todos los números, se podría haber hecho mucho antes y no hace falta controlar uno por uno todos estos casos, ya que seguro que fallan porque A=B.

Ambos defectos se solucionan partiendo la condición en parte pequeñas e intercalarlas entre los For, como se ve en el siguiente programa que tarda sólo 1 minuto (cuando Max vale 30 ). En este caso es fácil controlar que cada condición sea la correcta.

Defint A-Z
CLS
Dim Tot as Long
Const Max = 5 'o 30
' Usamos una constante para que sea facil de modificar
For A = 1 TO Max
  For B = 1 TO Max
    IF A <> B Then
      For C = 1 TO Max
        IF A <> C And B <> C Then
          For D = 1 TO Max
            IF A <> D And B <> D And C <> D Then
              For E = 1 TO Max
                IF A<>E And B<>E And C<>E And D<>E Then
                  Tot = Tot + 1
                End If
              Next E
            End IF
          Next D
        End IF
      Next C
    End IF
  Next B
Next A
Print Tot

 

  

Menos dados:

En este programa se puede cambiar la cantidad de "caras" en los dados de manera sencilla, aunque es más difícil cambiar la cantidad de dados. Lo más fácil es sacar dados, así que analicemos que pasa con menos dados. (Una forma de hacer esto es guardar el programa por si después lo queremos e ir borrando los ciclos más internos de a uno). Por ejemplo para 3 dados queda

Defint A-Z
CLS
Dim Tot as Long
Const Max = 5 'o 30
'Usamos una constante para que sea facil de modificar
For A = 1 TO Max
  For B = 1 TO Max
    IF A <> B Then
      For C = 1 TO Max
        IF A <> C And B <> C Then
          'Lineas Borradas
          Tot = Tot +1
          'Lineas Borradas
        End IF
      Next C
    End IF
  Next B
Next A
Print Tot

De esta manera obtenemos la siguiente tabla

  1 dado 2 dados 3 dados 4 dados 5 dados
5 caras 5 20 60 120 120
30 caras 30 870 24360 657720 17100720

En este momento es interesante que cada uno se tome un tiempo para analizar los resultados y ver que relación hay entre uno y otro (sobre todo entre los que usan dados con la misma cantidad de caras), incluso probar con otras cantidades de caras y tratar de conjeturar alguna relación, y si pueden probarla mejor.

Solución:

Obtenemos que los valores de la tabla anterior son iguales a

  1 dado 2 dados 3 dados 4 dados 5 dados
5 caras 5 5*4 5*4*3 5*4*3*2 5*4*3*2*1
30 caras 30 30*29 30*29*28 30*29*28*27 30*29*28*27*26

O sea el primero es igual al número de caras (porque hay un sólo dado), el segundo es el producto del número de caras por el número de caras menos uno. Para pasar al siguiente multiplico por el número de caras menos dos y así sigo. Tratemos de justificarlo :

Si llamo n al número de caras, en el primer dado puedo elegir cualquier cara, o sea hay n posibilidades. Para el segundo dado puedo elegir todas menos una (la que elegí en el primero), así que por cada uno de los n casos del primero tengo (n-1) en el segundo, o sea que en Total hay n(n-1) casos. En el tercero tengo dos caras prohibidas porque las dos elegidas en los dos primeros dados son distintas, o sea que hay n-2 para elegir. Por lo tanto hay (n-2) elecciones por cada caso de dos dados y por eso hay n*(n-1)*(n-2) . Y así sucesivamente.

Esta propiedad nos permite escribir el siguiente programa, que es muchísimo más rápido que los anteriores:

Defint A-Z
Const Max = 5' o 30
Tot = 1
For D = 1 TO 5 ' cada dado
  Tot = Tot * (Max - (D - 1))
Next D
Print Tot

En el caso particular en el que la cantidad de dados es igual a la de caras el resultado obtenido se llama el factorial. Por ejemplo el factorial de 5 se escribe 5! y es igual a

5!=5*4*3*2*1=120


Ejercicios:

  1. ¿Por que vale menos puntos una escalera servida que una generala servida?

  2. ¿De cuántas formas se pueden ordenar 10 personas en una fila?

  3. Tengo dos dados con los números del 1 al 10 y dos con los números del 1 al 5. ¿De cuantas maneras puedo obtener valores distintos en todos los dados? ¿Podés obtener además una fórmula similar al caso en que eran todos los dados iguales?

  4. Tengo tres dados con 50 caras con los números pares entre 1 y 100 (inclusive), y otros dos con 50 caras con los números entre 1 y 50 (los dos inclusive). ¿De cuantas maneras puedo obtener valores distintos en todos los dados?

Lecciones siguientes:

Por ahora ninguna

 


La idea es que hagan los ejercicios y piensen que otras cosas interesantes se pueden hacer relacionadas con estos temas. Cuéntennos lo que consiguieron y pregunten lo que no les salió. Envíen sus preguntas, dudas, sugerencias, experiencias y propuestas. Nuestra dirección es cym98@oma.org.ar .

También nos gustaría saber tu opinión sobre esta clase. Les pedimos que se tomen unos instantes y contesten estas preguntas. Con tu ayuda podremos hacer un curso cada vez mejor.

¿Cuál es tu calificación general de esta clase?

No entendí nada   Mala   Regular   Buena   Muy buena

El contenido de esta clase te resultó:

Nuevo   Conocido en parte   Conocido

El contenido de esta clase te pareció:

Difícil   Regular   Fácil

Los ejercicios de esta clase te parecieron:

Difíciles   Regulares   Fáciles

Comentarios, preguntas, sugerencias:

Agregar más información o una nueva lección sobre:

Operadores And, Or, Not

Nombre y apellido (opcional):

E-mail (opcional):

    


OmaNet   Curso CyM98 OmaNet - Educación Interactiva
   
www.oma.org.ar/omanet | omanet@oma.org.ar
mensajes: webmaster@oma.org.ar
buy duty free alcohol online duty free cigs uk buy cigars online buy cosmetics duty free where to buy duty free perfumes online where to buy tobacco online