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) comon(turnos al bate) tienen que ser números enteros positivos. Eso implica quem/nes 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á sea287) 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)