Reto de selección para el Mathcamp 2017 Se dirige a una edad de: 13-18 Autor: Bill Kuszmaul
La doctora Grande es una consultora matemática que se especializa en números grandes. Inicia su negocio con una lista de 100 clientes ordenados en orden de importancia (el 1 es el más importante). Cada día, Grande tiene tiempo de visitar sólo a uno de sus clientes.
Un cliente se siente insatisfecho si Grande aún no le ha visitado, o si Grande ha visitado a alguien menos importante desde la última vez que le visitó. Cada día, Grande visita al cliente más importante que se siente insatisfecho. El primer día, Grande visita al cliente 1, el segundo día, al cliente 2, el tercer día, al cliente 1, y así sucesivamente.
Cuando ninguno de los clientes se sienta insatisfecho, la doctora Grande podrá, por fin, retirarse.
(a) Prueba que la doctora Grande podrá retirarse, eventualmente, algún día.
(b) A lo largo de la carrera de la doctora Grande ¿cuántos días se despierta insatisfecho el cliente que ocupa la posición n-ésima de la lista?
(c) Describe de forma clara el conjunto de clientes que se despiertan insatisfechos en el n-ésimo día de la carrera de la doctora Grande.
Es un problema que trata de poner a prueba nuestra capacidad para encontrar sentido a los patrones, en este caso un patrón muy largo, con mucha regularidad, pero difícil de manejar.
Si queremos probar cosas en sucesiones de números, debemos tener muy claro lo que es la inducción completa en matemáticas, porque suele ser una técnica muy útil, en especial en las sucesiones recursivas, en las que cada término depende de cierta forma de los anteriores. Si estás familiarizado/a con esta técnica, puedes saltarte la explicación, y si no quieres demostrar las conclusiones, si no sólo intuirlas, también, pero el problema estará incompleto.
La inducción consiste en comprobar dos cosas. La primera suele ser muy sencilla, y es que la propiedad que buscamos se cumple en el primer caso, o en los casos más sencillos. La segunda, que suele necesitar de un trabajo más teórico, consiste en probar que, suponiendo que tenemos demostrada la propiedad para los casos previos, el siguiente caso podemos demostrarlo a partir de ellos. Si se dan esas dos condiciones, la propiedad será cierta en todo caso, ya que el segundo se apoya en el primero, el tercero en los dos anteriores, y así sucesivamente.
Apartado (a)
Ahora, para nuestro problema, vamos a simplificarlo a sólo unos pocos clientes, a ver qué pasa. Si sólo tuviese dos clientes en la lista, acabaría en 3 días (1 – 2 – 1 y todos estarían satisfechos). Si tuviese 3 clientes, necesitaría 7 días (1 – 2 – 1 – 3 – 1 – 2 – 1 y, claro, necesitaría el doble del tiempo anterior más un día. Observa que, al visitar al último cliente, todos los demás están insatisfechos, con lo que debe volver a empezar su recorrido. El último cliente permanece satisfecho el resto del tiempo, ya que no visita a nadie por detrás de él. La secuencia de 15 días para 4 clientes sería, entonces, 1 – 2 – 1 – 3 – 1 – 2 – 1 – 4 – 1 – 2 – 1 – 3 – 1 – 2 – 1.
Eso significa que el número de días que es necesario, en función de los clientes, sería: 1 para 1 cliente, 3 para 2, 7 para 3, 15 para 4, y, en general, el doble que para la cantidad anterior más uno, que es una sucesión recursiva. Podríamos escribirlo así: D(N) = 2*D(N – 1) + 1. Observa que D(N) se refiere a la forma de calcular el número de días que corresponden a N clientes.
Es decir, que en efecto, algún día acabará con su trabajo. Pero será un día muy, muy lejano. Si queremos saber más, podemos intuir que tiene algo que ver con las potencias de 2, porque cada vez multiplicamos por 2.
Imagina que intuimos que la fórmula sería algo así como 2^N – 1. ¿Cómo podríamos probarlo?
Los primeros días lo cumple, desde luego, con lo que el primer paso de la inducción está asegurado.
Supongamos que se cumple esa fórmula hasta el día N – 1, en el que D(N – 1) = 2^(N – 1) – 1.
¿Qué vale D(N)? Como Hemos visto, recursivamente será 2*D(N – 1) + 1 = 2*( 2^(N – 1) – 1) + 1 = 2^N – 2 + 1 = 2^N – 1, luego la fórmula se cumple en todos los casos.
Bueno, pues podemos calcular el día de su jubilación, pero os advierto que va a necesitar algún tratamiento de longevidad, ya que necesita trabajar 2^100 – 1 días, y eso son muchos millones de años. Ya tenemos la respuesta al apartado (a).
Apartado (b)
Para empezar el apartado (b), volvamos a nuestra lista con sólo tres clientes, recuerda que el patrón de visitas era 1 – 2 – 1 – 3 – 1 – 2 – 1.
Los días según cómo despierta el cliente 1 serán i – s – i – s – i – s – i – s (hemos añadido el día de la jubilación, para que quede claro que queda satisfecho al final), está claro que cada vez que visite a alguien más, al día siguiente se va a despertar insatisfecho, y va a recibir la visita de la doctora Grande. Por tanto, la mitad de días despertará satisfecho, y la otra mitad, insatisfecho.
El cliente 2 tendrá un ritmo diferente, i – i – s – s – i – i – s – s. Si estudiamos más el caso, veremos que hasta que no le llega su día de visita, está insatisfecho, y cuando pasa a estado satisfecho, volverá a cambiar cuando visiten a alguien posterior suyo. Como cada vez que le visita a él o a alguien posterior, el primero queda insatisfecho y vuelve a empezar el ciclo, se repetirá todo el tiempo, así que de nuevo la mitad de días despertará satisfecho, y la otra mitad, insatisfecho.
El tercer cliente tiene el ritmo i – i – i – i – s – s – s – s. Como podemos intuir, vuelve a suceder lo mismo.
Esta situación se puede extender fácilmente a la lista de 100 clientes. Un cliente que ocupe la posición N estará insatisfecho durante 2^(N – 1) días, que será el día en que reciba su primera visita, porque durante ese tiempo, Grande está ocupada satisfaciendo a los N – 1 clientes anteriores. Ese día, le visita y, repentinamente, los N – 1 clientes anteriores vuelven a estar insatisfechos, con lo que pasará otros 2^(N – 1) días visitándoles, durante los cuales, nuestro cliente N seguirá satisfecho. Precisamente ese día, o bien visita a un cliente posterior, con lo que vuelve a iniciarse la secuencia, o se jubila porque todos están ya satisfechos.
En definitiva, la solución al apartado (b) es que todos los clientes están satisfechos exactamente la mitad de los días (si contamos el día de la jubilación de Grande).
Apartado (c)
Por último, el apartado (c) es el más difícil. Volvamos a analizar el problema de tres clientes, para entender primero el patrón.
El primer día, todos los clientes estarán insatisfechos.
El segundo día, sólo el primer cliente está satisfecho.
El tercer día, el segundo cliente está satisfecho, pero todos los demás están insatisfechos.
El cuarto día el primer y el segundo cliente están satisfechos, pero el tercero sigue insatisfecho..
El quinto día, el tercer cliente está satisfecho y los demás no.
El sexto día, el primer y el tercer cliente están satisfechos y el segundo no.
El séptimo día, el primero está insatisfecho y los otros dos, satisfechos.
El octavo día, el de la jubilación, todos están satisfechos.
Si conocéis el sistema binario de numeración, y alguna vez habéis contado del cero al siete con él, seguramente estaréis familiarizados con este ritmo de crecimiento.
No es fácil pensar en un sistema que describa esta situación en pocas palabras, pero está claro, por el apartado anterior, que debemos pensar en potencias de 2.
Por ejemplo, cada día determinado, sabremos si un cliente está satisfecho o insatisfecho según la cantidad que nos dé al dividir el número de días entre 2^(N – 1), pero sumando 1 si el resultado no es exacto. Si esa cantidad (tomada como número entero) es par, entonces está satisfecho y si no, está insatisfecho. Esta respuesta no es muy satisfactoria, pero podemos comprobar que funciona, de nuevo recursivamente.
Lo más difícil es dar la siguiente caracterización, bien por analogía con los números binarios, bien por similitud con algún otro problema que hayamos visto.
Cada número entero se puede escribir de una única forma como suma de potencias diferentes de 2, teniendo en cuenta que 1 lo escribimos como 2^0, que consideraremos que es la primera potencia. Así, 3 = 1 + 2, o bien 11 = 1 + 2 + 8. Pues bien, si buscamos qué potencias suman exactamente el día anterior al que queramos estudiar, entonces, los clientes que ocupen la posición correspondiente a esas potencias serán los únicos satisfechos. Los demás estarán insatisfechos.
Veamos algunos ejemplos, y veremos por qué sucede. El primer día, el número es cero, que es suma de cero potencias de 2, y todos los clientes estarán insatisfechos. El día sexto, por ejemplo, el número es 5, suma de 1 y 4, por lo que el primero y el tercero (el cuatro es la tercera potencia de dos) estarán satisfechos y todos los demás insatisfechos.
Podemos comprobar que los primeros días lo cumplen de forma precisa. Ahora bien, cuando pasa un día más, y sumamos uno al número anterior, estamos sumando la primera potencia de 2. Si el primer cliente está insatisfecho, será ese al que visitamos, por lo que seguirá siendo cierta la propiedad, pero si no, sumaremos uno a una suma de la forma 1 + 2 + 4 + 8…., suma de potencias consecutivas, que podemos comprobar que da exactamente la primera potencia que falte en la lista, borrando todas las potencias anteriores. Que es exactamente lo que pasa, que se visita al primer cliente insatisfecho, haciendo que ése pase a estar satisfecho, y todos los demás queden insatisfechos.
Por ejemplo. Supongamos que un cierto día, tenemos satisfechos a los clientes 1, 2, 3 y 5. Ese día será el que corresponde al número 2^0 + 2^1 + 2^2 + 2^4 = 23, es decir el día 24. Para pasar al día siguiente, sumamos uno, con lo cual, tendremos 1 + 2^0 + 2^1 + 2^2 + 2^4 = 2^1 + 2^1 + 2^2 + 2^4 = 2^2 + 2^2 + 2^4 = 2^3 + 2^4 = 24, así que el día 25 están satisfechos los clientes 4 y 5, y todos los demás insatisfechos.
Supongo que tendréis la cabeza algo liada, pero aún falta una vuelta de tuerca más sorprendente. Si queremos hacer algo parecido para los clientes insatisfechos, la suma de las potencias que corresponden a sus posiciones es precisamente ¡el número de días que faltan a la doctora para la jubilación! Esta afirmación se basa en propiedades similares, y la dejo en el aire como ejercicio para el lector que haya llegado hasta aquí.
