Cálculo con la balanza

Se trata de averiguar cual es la moneda falsa que hay en un montón de monedas. Todas las monedas pesan exactamente igual excepto la que es falsa. Disponemos de una balanza. ¿Cuántas pesadas tendremos que realizar?

Balanza plateada

Introducción

Autores:

Jaume Saura Bort y Francisco Cascales Rueda

Propósito:

Averiguar en el mínimo número de pesadas posible la bola mala entre N bolas. Y si pesa más o menos.

Material:

Se supone que se dispone de una balanza con tres posibles estados: equilibrio, se desnivela a la izquierda o se desnivela a la derecha.

Asignatura:

Cibernética. Teoría matemática de la información.

Estrategia:

Se trata de que la división de los estados posibles sea lo más equiprobable posible, para conseguir el máximo de información.

El applet:

Utilización del applet:

Supongamos que tenemos una serie de monedas y sabemos que una de las monedas es falsa. La moneda falsa no sabemos si pesa más o si pesa menos. Etiquetamos cada una de las monedas con un número. El programa nos propone que monedas hemos de colocar en cada plato de la balanza. Y nosotros hemos de informar del resultado de la pesada.

La manera de ver si el programa funciona es pensar cual es la moneda falsa (y si pesa más o menos) De esta forma podremos decidir el equilibrio de la balanza en cada pesada que se nos proponga.

Con 12 monedas siempre se necesitan 3 pesadas para que el programa deduzca la moneda falsa. ¿Cúantas pesadas le harían falta con 1000 monedas?

A continuación se muestra una imagen de ejemplo del applet ya que el plugin de Java está desactivado:

El programa:

  • Descargar CalcBalance.jar
  • Para ejecutar el programa: javaw -jar CalcBalance.jar

Análisis:

Hay N bolas. Para que el problema tenga sentido (que se pueda resolver) N ha de ser mayor o igual a 3. La probabilidad de encontrarte con la bola mala es 1/N. La probabilidad de que pese más es 1/2. La probabilidad conjunta de ambos sucesos (son independientes) es:

              1   1    1
          p = - · - = --- 
              N   2   2·N
  

La incertidumbre asociada, o información necesaria para averiguar lo que deseamos, es:

                  1
          I = log - = log 2N
                  p
  

Para estados equiprobables, la probabilidad de cada pesada es 1/3, por tanto su incertidumbre es log 3. Necesitamos que la información de todas las pesadas que realicemos sea mayor o igual que la información que necesitamos I.

          log 2N ¾ k·log 3
  

donde k es el mínimo entero que cumple la desigualdad (número de pesadas realizadas). Pero no siempre podremos hacer que los estados de la balanza sean equiprobables. Por tanto k es una cota inferior del número de pesadas. La cota superior del número de pesadas es k+1

Algoritmo:

Analizando el problema nos hemos encontrado con cuatro posibles estados, para cada uno de los cuales hemos diseñado una función recursiva. Estas funciones deciden la pesada más equiprobable y dependiendo del resultado deciden a que estado llegamos y por tanto a cual de las funciones recursivas hay que llamar a continuación. Tras cada pesada se reduce lo máximo posible la incertidumbre y al final se llega a casos triviales.

Nomenclatura:

(=) Balanza en equilibrio.
(>) Pesa más el lado izquierdo.
(<) Pesa más el lado derecho.
(+) La bola mala pesa más.
(-) La bola mala pesa menos.
X, Y, Z Son conjuntos de bolas.
#C Cardinal del conjunto C.
A _ B El conjunto A está contenido o es igual al B.
N, M Indican la cantidad de bolas.
{Y ,Z} Conjuntos de bolas en cada plato de la balanza. En el plato izquierdo Y y en el derecho Z.
(LC) cuando la balanza se desnivela hacia el Lado Contrario.
(ML) cuando la balanza se desnivela hacia el Mismo Lado.

Estados:

  • ESTADO0 (parámetro X)

    Tenemos N bolas = #X de las que no sabemos nada. Buscamos un número M tal que:

    N = 3·M {Y, Z} (#Y = #Z = M)
    N = 3·M + 1 {Y, Z} (#Y = #Z = M)
    N = 3·M + 2 {Y, Z} (#Y = #Z = M+1)
    No importa cuales sean las bolas de los conjuntos Y y Z. Dependiendo del resultado de la pesada pasaremos a un estado u otro (llamaremos a una función recursiva u otra). Los resultados y los estados a los que pasamos son:

    (=) ESTADO1(X - Y - Z)
    (>) ESTADO2(>, Y, Z)
    (<) ESTADO2(<, Y, Z)
  • ESTADO1 (parámetro X)

    Tenemos N bolas = #X de las que no sabemos nada y tenemos bastantes bolas buenas adicionales. Buscamos un número M tal que:

    2·N = 3·M {Y, Z} (#Y = #Z = M)
    2·N = 3·M + 1 {Y, Z} (#Y = #Z = M)
    2·N = 3·M + 2 {Y, Z} (#Y = #Z = M+1)

    El conjunto Y está compuesto de bolas buenas y el conjunto Z de bolas candidatas a malas. Los resultados y los estados a los que pasamos son:

    (=) ESTADO1(X - Z)
    (>) ESTADO3(-, Z)
    (<) ESTADO3(+, Z)

    Nota:

    Si teníamos que 2·N = 3·M. Podemos utilizar una estrategia equivalente pero distinta. En la que no utilizamos las bolas buenas adicionales;

    2·N = 3·M {Y, Z} (#Y = #Z = M/2)

    Las bolas de los conjuntos Y y Z son todas de las bolas candidatas a malas. Los resultados y los estados a los que pasamos son:

    (=) ESTADO1(X - Y - Z)
    (>) ESTADO2(>, Y, Z)
    (<) ESTADO2(<, Y, Z)

    Casos patológicos:

    • Si N = 1 entonces se tiene que pesar esta bola (que es la mala) con otra cualquiera (se necesita saber cuántas bolas hay disponibles). El resultado de esta pesada es la solución del problema. Si (=) no hay ninguna bola mala.
    • Si N = 2 entonces se reduce a una o dos veces el caso anterior (dependiendo si encontramos la bola mala en la primera pesada o en la segunda).
  • ESTADO2 (parámetros: DESNIVEL, X1, X2)

    Ha habido desnivel (en el estado 0 o 1). Tenemos 2·N bolas = #X1 + #X2 y sabemos hacia donde se inclinó la balanza. Consideramos sólo el caso de desnivel a la izquierda (el desnivel a la derecha es un caso simétrico). Utilizaremos los siguientes conjuntos de bolas:

    W _ X1
    Y _ X2
    Z _ B (B = conjunto de bolas buenas)
    #W = #Y = #Z = K

    Casos posibles:

    2·N = 3·M {X1 - W + Y, X2 - Y + Z} (K = M)
    2·N = 3·M + 1 {X1 - W + Y, X2 - Y + Z} (K = M)
    2·N = 3·M + 2 {X1 - W + Y, X2 - Y + Z} (K = M+1)

    Los resultados y los estados a los que pasamos son:

    (=) ESTADO3(+, W)
    (ML) ESTADO2(DESNIVEL, X1-W, X2-Y)
    (LC) ESTADO3(-, Y)

    Caso patológico:

    Si N = 1 entonces pesaremos la bola que desniveló la balanza a su favor (en el plato izquierdo) con una de buena (en el plato derecho). Posibles resultados:

    (=) La mala es la que no hemos pesado y pesa menos.
    (>) La mala es la que hemos pesado y pesa más.
    (<) Este caso es imposible.
  • ESTADO3 (parámetros: PESO, X)

    Tenemos N bolas = #X y ya sabemos si la mala pesa más o menos (parámetro PESO). Suponemos que pesa más (el otro caso es simétrico). Casos posibles:

    N = 3·M {Y, Z} (#Y = #Z = M)
    N = 3·M + 1 {Y, Z} (#Y = #Z = M)
    N = 3·M + 2 {Y, Z} (#Y = #Z = M+1)

    Nota:

    Aquí se puede realizar una mejora heurística. Cuando sólo nos quedan siete bolas el algoritmo general pesaría dos con dos y necesitaría siempre dos y sólo dos pesadas para encontrar la bola errónea. Ahora bien, si pesamos tres con tres también necesitamos como máximo dos pesadas pero hay un caso particular en el que sólo necesitamos una. Nosotros no hemos encontrado ningún otro caso de estas características.

    Los resultados y los estados a los que pasamos son:

    (=) ESTADO3(PESO, X - Y - Z)
    (>) ESTADO3(PESO, Y)
    (<) ESTADO3(PESO, Z)

    Nota:

    Si el resultado es (=) normalmente hacemos la llamada ESTADO3(PESO, X - Y - Z), pero hay un caso imposible, y es cuando #(X - Y - Z) es igual a cero; comparabamos las dos últimas bolas y alguna de ellas tenía que ser la mala. En este caso ha habido un error en alguna de las pesadas.

    Caso patológico:

    Si X = 1 entonces ésta es la bola mala y su peso viene determinado por el parámetro PESO.

Transiciones de estado:

                              (=)
                        +-------------+
                        ¦             ¦
                        ¦  +-------+  ¦
                        +->¦       ¦--+
                 (=)       ¦   1   ¦      (>)
                   +------>¦       ¦------+          +-------+
                   ¦       +-------+   (<)¦          v       ¦
     +-------+     ¦           ¦          ¦      +-------+   ¦(siempre)
     ¦       ¦-----+           ¦          +----->¦       ¦   ¦
     ¦   0   ¦              (>)¦(<)              ¦   3   ¦---+
     ¦       ¦-----+           ¦          +----->¦       ¦
     +-------+     ¦           v          ¦      +-------+
                   ¦(>)    +-------+   (=)¦
                   +------>¦       ¦------+
                 (<)       ¦   2   ¦      (LC)
                        +->¦       ¦--+
                        ¦  +-------+  ¦
                        ¦             ¦
                        +-------------+
                             (ML)
  

Comentarios

Proinf.net, ©2003-2019 ci 3.1.10 (CC) Esta obra está bajo una licencia de Creative Commons Este software está sujeto a la CC-GNU GPL