El siguiente es uno de los problemas más entretenidos que he encontrado recientemente en uno de esos libros de «Acertijos y Problemas para resolver con computadora».

Demuestre que si un jugador de béisbol registra un promedio de bateo de .334, tiene que haber tomado al menos 287 turnos al bate.

El énfasis en demuestre y al menos, es mío.

Me pareció entretenido porque no es de búsqueda exhaustiva (típico en esos libros), e involucra la frontera entre números racionales e irracionales, dos infinitos diferentes.

Promedio de bateo

El promedio de bateo en una temporada regular se calcula como la cantidad de hits conectados dividida entre la cantidad de turnos al bate, redondeado a tres decimales. Naturalmente, se puede tener un promedio .334 si bateas 334 hits en 1000 turnos. Sin embargo, ambos valores son absolutamente absurdos en una temporada regular.

Entonces, estamos buscando dos números enteros m y n tales que

    0.3335.. <= m / n < 0.3345...

y tenemos que observar que:

  • Tanto m (cantidad de hits) como n (turnos al bate) tienen que ser números enteros positivos. Eso implica que m/n es un número racional.

  • El intervalo [0.3335...,0.3345...) tiene infinitos números reales. Esto es, incluye racionales e irracionales.

  • Es posible que en ese intervalo haya más de un número racional. Cualquiera de ellos, al redondearlo, produciría .334. No nos sirve cualquiera de ellos, sólo nos sirve el que tenga el mínimo denominador, (que ojalá sea 287) para satisfacer el al menos de la pregunta.

Podemos hacer uso de nuestra aritmética de educación primaria para simplificar el intervalo. Esto es, podemos escribir

               3335      667
    0.3335 = ------- = ------
              10000     2000

               3345      669
    0.3345 = ------- = ------
              10000     2000

y ahora nuestro problema se reduce a encontrar

      667      m      669
    ------ <= --- < ------
     2000      n     2000

El lector astuto habrá notado que en ese intervalo hay infinitos números racionales.

Arboles infinitos con localidad finita.

Hay una forma muy elegante de construir el conjunto de todas las fracciones positivas, el «Árbol de Stern-Brocot». El método es simple y, por supuesto, recursivo.

En el caso base, hay dos semillas, izquierda y derecha respectivamente. La fracción izquierda 0/1 representa el cero, y la fracción derecha 1/0 representa el infinito positivo.

En el caso recursivo, se toma una fracción izquierda m/n y una fracción derecha m'/n', y se pone la fracción

   ( m + m') / ( n + n' )

en medio de las dos. Así, el proceso avanza

   0/1, 1/0

   0/1, 1/1, 1/0

   0/1, 1/2, 1/1, 2/1, 1/0

   0/1, 1/3, 1/2, 1/1, 3/1, 2/1, 1/0

En cada iteración aparece el doble de las fracciones del nivel anterior. En la mitad izquierda antes de 1/1 están todas las fracciones propias, y en la mitad derecha están todas las fracciones impropias.

Este método funciona, en cuanto cada fracción que aparece tiene el numerador y denominador más pequeños posibles para el número racional que representa, y en cuanto a que todos los números racionales aparecen eventualmente.

Podríamos aprovechar la flojera de Haskell para construir ese árbol infinito y recorrer solamente las partes que nos interesen. Y lo estaríamos haciendo mal...

Sistemas de Numeración y Lenguajes

El árbol Stern-Brocot es binario, y contiene a todas las fracciones reducidas positivas exactamente una vez. Esto quiere decir que hay exactamente un camino desde la raíz del árbol (1/1) hasta la fracción particular.

data SBT = L | R
  deriving (Show,Eq)

Usaremos los símbolos L y R para indicar que bajamos a la izquierda o la derecha, respectivamente, mientras descendemos hasta un nodo particular. Entonces, la palabra construida denota de forma unívoca un número particular. Por ejemplo, la lista [L,R,L,R,L] corresponde al descenso

   1/1, 1/2, 2/3, 3/5, 5/8, 8/13

y diremos que denota la fracción 8/13.

Dada una cadena, ¿cuál fracción denota?

Si tenemos una lista con la secuencia de pasos en el descenso, tenemos que calcular la fracción intermedia (mediant) después de cada paso. Para ello necesitamos conocer la fracción izquierda y derecha actuales.

Representaré las fracciones usando tuplas, con el numerador y denominador en ese orden.

value :: [SBT] -> (Int,Int)
value = result . foldl' step ((0,1),(1,1),(1,0))
  where 
    step (l,c,r) L = (l,mediant c l,c)
    step (l,c,r) R = (c,mediant c r,r)
    mediant (m,n) (m',n') = (m+m',n+n')
    result (_,c,_) = c

En cada paso (step) de cómputo necesitamos la fracción en el nodo actual, la fracción de referencia a la izquierda, y la fracción de referencia a la derecha. Al comenzar, estamos en la raíz (1,1) con las semillas (0,1) y (1,0) como referencias izquierda y derecha, respectivamente.

Procesaremos la lista de pasos de izquierda a derecha usando foldl'. En cada paso calculamos la nueva fracción que se convertirá en actual, mantendremos la fracción de referencia en el mismo sentido del descenso (i.e. izquierda se mantiene si es L, derecha se mantiene si es R, y haremos que la fracción previa reemplace a la referencia contraria al sentido del descenso.

Así, podemos determinar la fracción asociada a diferentes descensos

    ghci> value []
    (1,1)
    ghci> value [L,L]
    (1,3)
    ghci> value [R,L]
    (3,2)
    ghci> value [L,R,L,R,L]
    (13,8)

Dada una fracción, ¿cuál es el camino?

Dada una fracción cualquiera, podemos encontrarla en el árbol haciendo búsqueda binaria inocente combinada con aritmética. Aprovecharemos la manipulación de fracciones de Haskell, que asegura la forma reducida, y la función value definida anteriormente. Es una solución tan ineficiente como inocente.

path :: Int -> Int -> [SBT]
path m n = go m n []
  where 
    go m n c = let (mc,nc)  = value c
               in if m % n == mc % nc
                 then c
                 else if m % n < mc % nc 
                   then go m n (c ++ [L])
                   else go m n (c ++ [R])

En cada paso de la búsqueda tendremos el camino recorrido hasta ese punto (c). Calcularemos el valor del camino recorrido usando value y construiremos la fracción asociada usando el operador (%) provisto por Data.Ratio.

Si el valor calculado para el camino coincide con el valor calculado para la fracción objetivo, hemos calculado el camino completo.

Si la fracción objetivo es menor que el valor asociado al camino, agregamos una L al final del camino, y recurrimos. De lo contrario, agregamos una R al final del camino y recurrimos.

Esta solución, aunque correcta, es terriblemente ineficiente, pues recalcula el valor del camino en cada iteración. Además, agrega elementos al final de las listas.

Existe una solución muchísimo más rápida y compacta, pero su derivación requiere explicar el cómputo usando matrices, y calcular fórmulas cerradas para recurrencias. Pregunte si está interesado.

Confianza en mi matemática

Se supone que path y value son mutuamente inversas. Es decir, debería ser verdad

    uncurry path . value = id          (I)

es decir, para cualquier camino, obtener su valor y calcular el descenso, debería resultar en el mismo camino.

También debería ser verdad

    value . uncurry path = id          (II)

es decir, para cualquier fracción reducida en forma de tupla, calcular su camino y luego obtener su valor, debería resultar en la misma fracción reducida.

La librería QuickCheck de Haskell me permite expresar esas propiedades con mucha facilidad, incluyendo las precondiciones necesarias.

instance Arbitrary SBT where
  arbitrary = elements [L,R]

Nos interesa generar caminos de longitud y contenido arbitrario. La librería QuickCheck provee mecanismos para generar datos al azar para pruebas, aprovechando Arbitrary. En particular es capaz de generar listas de longitud y contenido arbitrario, siempre y cuando haya forma de generar arbitrariamente el tipo contenido. Es por eso que defino una instancia para generar un valor del tipo SBT, seleccionando con probabilidad uniforme (elements).

prop_I :: [SBT] -> Bool
prop_I p = p == (uncurry path . value) p

La primera propiedad se expresa directamente, siguiendo la convención de usar el prefijo prop_. Técnicamente no es necesario escribir la firma, pues no hay ambigüedad dado el tipo de la función value, y no tenemos ninguna restricción particular sobre los valores de prueba. Sin embargo, escribirla aclara la intención.

Para todo camino p, generado al azar por quickCheck debe cumplirse que dicho camino sea idéntico a evaluar la fracción asociada y calcular su camino.

prop_II :: Positive (Ratio Int) -> Bool
prop_II (Positive f) = v == (value . uncurry path) v
  where v = (numerator f, denominator f)

La segunda propiedad requiere una especificación más detallada, que logramos a través de la firma. Es necesario que quickCheck genere fracciones reducidas de enteros que sean positivas. La librería QuickCheck incluye generadores para números positivos (Positive a) siempre que a sea un tipo numérico generable, y Ratio Int lo es. La generación será un poco más lenta, pues primero se generan Ratio Int y luego se determina si son positivos.

Con estás propiedades definidas, puedo hacer que quickCheck genere 100 casos de prueba al azar y compruebe ambas propiedades.

    ghci> quickCheck prop_I
    +++ OK, passed 100 tests.
    ghci> quickCheck prop_II
    +++ OK, passed 100 tests.

¿Y el problema original?

Nuestras observaciones sobre el problema nos llevaron a concluir que tenemos que encontrar la fracción propia más pequeña entre (667,2000) y (669,2000).

La función path m n nos provee el camino desde la raíz del árbol Stern-Brocot hasta la fracción propia (m,n). Podemos comparar los caminos path 667 2000 y path 669 2000: el primero representa una fracción menor que el segundo, así que ambos caminos son iguales hasta cierto punto en que el primero tiene una L y el segundo tiene una R.

Resolviendo el problema general, queremos encontrar el prefijo común de dos caminos:

commonPrefixBetween m0 n0 m1 n1 =
  map fst $ takeWhile (uncurry (==)) $ zip sbm0 sbm1
  where
    sbm0 = path m0 n0
    sbm1 = path m1 n1

Emparejamos posición a posición (zip) los dos caminos sbm0 y sbm1, y conservamos (takeWhile) aquellos elementos que sean iguales en ambos caminos (uncurry (==) le agrega elegancia). Finalmente, conservamos el primer elemento de cada pareja en una lista. Precisamente los elementos comunes a ambas listas.

Ese prefijo común corresponde al número racional más simple que está en el rango especificado. Ahora podemos usarlo para calcular el número de hits y turnos al bate.

    ghci> value $ commonPrefixBetween 667 2000 669 2000
    (96,287)
    ghci> 96 / 287
    0.3344947735191638

Puede haber otras fracciones entre (667,2000) y (96,287), o entre (96,287) y (669,2000), que al redondearse a tres decimales produzcan .334. Pero ninguna de esas fracciones tiene un denominador más pequeño que 287. En consecuencia queda demostrado que si un bateador tiene un promedio de .344 tuvo que haber tomado al menos 287 turnos al bate y conectado 96 hits.

Bonus Fun Facts

Por su construcción, repetir la secuencia [L] genera, para cada cadena, un elemento de la Serie Armónica (1/n)

    ghci> value $ take 1 $ cycle [L]
    (1,2)
    ghci> value $ take 2 $ cycle [L]
    (1,3)
    ghci> value $ take 50 $ cycle [L]
    (1,51)

mientras que repetir la secuencia [R] genera, para cada cadena, el número entero correspondiente.

Más interesante resulta saber que el Árbol Stern-Brocot se puede usar para aproximar números irracionales. Por ejemplo, es posible aproximar la «Proporción Áurea», relacionada con la Secuencia de Fibonacci, simplemente extendiendo la aparentemente inocente secuencia [R,L], i.e.

    ghci> value $ take 10 $ cycle [R,L]
    (144,89)
    ghci> 144 / 89
    1.6179775280898876
    ghci> value $ take 50 $ cycle [R,L]
    1.618033988749895

con este último valor preciso hasta la décima posición decimal. Usar la secuencia [L,R] se obtiene el conjugado o «Silver Ratio».

Quizás uno de los resultados más interesantes está en usar el Árbol Stern-Brocot para aproximar e. Hace más de un siglo se sabe que la secuencia

    RL^0RLR^2LRL^4RLR^6LRL^8RL...

resulta en una fracción que aproxima e con mucha precisión.

    ghci> let e = [R,R,L,R,R,L,R,L,L,L,L,R,L,R,R,R,R,R,R,L]
    ghci> value e
    (2721,1001)
    ghci> 2721 / 1001
    2.7182817182817183
    ghci> exp 1
    2.718281828459045

Existe un algoritmo general para aproximar números irracionales usando el Árbol Stern-Brocot. Naturalmente, sólo se detiene si se le interrumpe forzosamente, cuando uno se harta de coleccionar elementos de la secuencia. Y con esta secuencia

    ghci> let wat = replicate    3 R
                  ++ replicate   7 L
                  ++ replicate  15 R
                  ++ [L]
                  ++ replicate 292 R
                  ++ [L,R,L,R,R,L,R,R,R,L]
                  ++ replicate  14 R
    ghci> value wat
    (85563208,27235615)
    ghci> 85563208 / 27235615
    3.141592653589794

no solamente se puede aproximar Pi, sino que se pueden encontrar todas las fracciones que le aproximan

    ghci> map value (Data.List.inits wat)