{"id":99,"date":"2017-08-11T19:18:53","date_gmt":"2017-08-11T19:18:53","guid":{"rendered":"https:\/\/blogs.ua.es\/dimates\/?p=99"},"modified":"2018-09-22T08:32:08","modified_gmt":"2018-09-22T08:32:08","slug":"la-consultora-grande-s","status":"publish","type":"post","link":"https:\/\/blogs.ua.es\/dimates\/2017\/08\/11\/la-consultora-grande-s\/","title":{"rendered":"Soluci\u00f3n a la consultora grande"},"content":{"rendered":"
Reto de selecci\u00f3n para el Mathcamp 2017\r\nSe dirige a una edad de: 13-18\r\nAutor: Bill Kuszmaul<\/pre>\n
La doctora Grande es una consultora matem\u00e1tica que se especializa en n\u00fameros grandes. Inicia su negocio con una lista de 100 clientes ordenados en orden de importancia (el 1 es el m\u00e1s importante). Cada d\u00eda, Grande tiene tiempo de visitar s\u00f3lo a uno de sus clientes.<\/p>\n
Un cliente se siente insatisfecho si Grande a\u00fan no le ha visitado, o si Grande ha visitado a alguien menos importante desde la \u00faltima vez que le visit\u00f3. Cada d\u00eda, Grande visita al cliente m\u00e1s importante que se siente insatisfecho. El primer d\u00eda, Grande visita al cliente 1, el segundo d\u00eda, al cliente 2, el tercer d\u00eda, al cliente 1, y as\u00ed sucesivamente.<\/p>\n
Cuando ninguno de los clientes se sienta insatisfecho, la doctora Grande podr\u00e1, por fin, retirarse.<\/p>\n
(a) Prueba que la doctora Grande podr\u00e1 retirarse, eventualmente, alg\u00fan d\u00eda.<\/p>\n
(b) A lo largo de la carrera de la doctora Grande \u00bfcu\u00e1ntos d\u00edas se despierta insatisfecho el cliente que ocupa la posici\u00f3n n-\u00e9sima de la lista?<\/p>\n
(c) Describe de forma clara el conjunto de clientes que se despiertan insatisfechos en el n-\u00e9simo d\u00eda de la carrera de la doctora Grande.\"\"<\/p>\n
<\/p>\n
Es un problema que trata de poner a prueba nuestra capacidad para encontrar sentido a los patrones, en este caso un patr\u00f3n muy largo, con mucha regularidad, pero dif\u00edcil de manejar.<\/p>\n
Si queremos probar cosas en sucesiones de n\u00fameros, debemos tener muy claro lo que es la inducci\u00f3n completa en matem\u00e1ticas, porque suele ser una t\u00e9cnica muy \u00fatil, en especial en las sucesiones recursivas, en las que cada t\u00e9rmino depende de cierta forma de los anteriores. Si est\u00e1s familiarizado\/a con esta t\u00e9cnica, puedes saltarte la explicaci\u00f3n, y si no quieres demostrar las conclusiones, si no s\u00f3lo intuirlas, tambi\u00e9n, pero el problema estar\u00e1 incompleto.<\/p>\n
La inducci\u00f3n 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\u00e1s sencillos. La segunda, que suele necesitar de un trabajo m\u00e1s te\u00f3rico, 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\u00e1 cierta en todo caso, ya que el segundo se apoya en el primero, el tercero en los dos anteriores, y as\u00ed sucesivamente.<\/p>\n
Apartado (a)<\/p>\n
Ahora, para nuestro problema, vamos a simplificarlo a s\u00f3lo unos pocos clientes, a ver qu\u00e9 pasa. Si s\u00f3lo tuviese dos clientes en la lista, acabar\u00eda en 3 d\u00edas (1 \u2013 2 \u2013 1 y todos estar\u00edan satisfechos). Si tuviese 3 clientes, necesitar\u00eda 7 d\u00edas (1 \u2013 2 \u2013 1 \u2013 3 \u2013 1 \u2013 2 \u2013 1 y, claro, necesitar\u00eda el doble del tiempo anterior m\u00e1s un d\u00eda. Observa que, al visitar al \u00faltimo cliente, todos los dem\u00e1s est\u00e1n insatisfechos, con lo que debe volver a empezar su recorrido. El \u00faltimo cliente permanece satisfecho el resto del tiempo, ya que no visita a nadie por detr\u00e1s de \u00e9l. La secuencia de 15 d\u00edas para 4 clientes ser\u00eda, entonces,  1 \u2013 2 \u2013 1 \u2013 3 \u2013 1 \u2013 2 \u2013 1 \u2013 4 \u2013 1 \u2013 2 \u2013 1 \u2013 3 \u2013 1 \u2013 2 \u2013 1.<\/p>\n
Eso significa que el n\u00famero de d\u00edas que es necesario, en funci\u00f3n de los clientes, ser\u00eda: 1 para 1 cliente, 3 para 2, 7 para 3, 15 para 4, y, en general, el doble que para la cantidad anterior m\u00e1s uno, que es una sucesi\u00f3n recursiva. Podr\u00edamos escribirlo as\u00ed: D(N) = 2*D(N \u2013 1) + 1. Observa que D(N) se refiere a la forma de calcular el n\u00famero de d\u00edas que corresponden a N clientes.<\/p>\n
Es decir, que en efecto, alg\u00fan d\u00eda acabar\u00e1 con su trabajo. Pero ser\u00e1 un d\u00eda muy, muy lejano. Si queremos saber m\u00e1s, podemos intuir que tiene algo que ver con las potencias de 2, porque cada vez multiplicamos por 2.<\/p>\n
Imagina que intuimos que la f\u00f3rmula ser\u00eda algo as\u00ed como 2^N \u2013 1. \u00bfC\u00f3mo podr\u00edamos probarlo?<\/p>\n
Los primeros d\u00edas lo cumple, desde luego, con lo que el primer paso de la inducci\u00f3n est\u00e1 asegurado.<\/p>\n
Supongamos que se cumple esa f\u00f3rmula hasta el d\u00eda N \u2013 1, en el que D(N \u2013 1) = 2^(N \u2013 1) \u2013 1.<\/p>\n
\u00bfQu\u00e9 vale D(N)? Como Hemos visto, recursivamente ser\u00e1 2*D(N \u2013 1) + 1 = 2*( 2^(N \u2013 1) \u2013 1) + 1 = 2^N \u2013 2 + 1 = 2^N \u2013 1, luego la f\u00f3rmula se cumple en todos los casos.<\/p>\n
Bueno, pues podemos calcular el d\u00eda de su jubilaci\u00f3n, pero os advierto que va a necesitar alg\u00fan tratamiento de longevidad, ya que necesita trabajar 2^100 \u2013 1 d\u00edas, y eso son muchos millones de a\u00f1os. Ya tenemos la respuesta al apartado (a).<\/p>\n
Apartado (b)<\/p>\n
Para empezar el apartado (b), volvamos a nuestra lista con s\u00f3lo tres clientes, recuerda que el patr\u00f3n de visitas era  1 \u2013 2 \u2013 1 \u2013 3 \u2013 1 \u2013 2 \u2013 1.<\/p>\n
Los d\u00edas seg\u00fan c\u00f3mo despierta el cliente 1 ser\u00e1n i \u2013 s \u2013 i \u2013 s \u2013 i \u2013 s \u2013 i \u2013 s (hemos a\u00f1adido el d\u00eda de la jubilaci\u00f3n, para que quede claro que queda satisfecho al final), est\u00e1 claro que cada vez que visite a alguien m\u00e1s, al d\u00eda siguiente se va a despertar  insatisfecho, y va a recibir la visita de la doctora Grande. Por tanto, la mitad de d\u00edas despertar\u00e1 satisfecho, y la otra mitad, insatisfecho.<\/p>\n
El cliente 2 tendr\u00e1 un ritmo diferente, i \u2013 i \u2013 s \u2013 s \u2013 i \u2013 i \u2013 s \u2013 s. Si estudiamos m\u00e1s el caso, veremos que hasta que no le llega su d\u00eda de visita, est\u00e1 insatisfecho, y cuando pasa a estado satisfecho, volver\u00e1 a cambiar cuando visiten a alguien posterior suyo. Como cada vez que le visita a \u00e9l o a alguien posterior, el primero queda insatisfecho y vuelve a empezar el ciclo, se repetir\u00e1 todo el tiempo, as\u00ed que de nuevo la mitad de d\u00edas despertar\u00e1 satisfecho, y la otra mitad, insatisfecho.<\/p>\n
El tercer cliente tiene el ritmo i \u2013 i \u2013 i \u2013 i \u2013 s \u2013 s \u2013 s \u2013 s. Como podemos intuir, vuelve a suceder lo mismo.<\/p>\n
Esta situaci\u00f3n se puede extender f\u00e1cilmente a la lista de 100 clientes. Un cliente que ocupe la posici\u00f3n N estar\u00e1 insatisfecho durante 2^(N \u2013 1) d\u00edas, que ser\u00e1 el d\u00eda en que reciba su primera visita, porque durante ese tiempo, Grande est\u00e1 ocupada satisfaciendo a los N \u2013 1 clientes anteriores. Ese d\u00eda, le visita y, repentinamente, los N \u2013 1 clientes anteriores vuelven a estar insatisfechos, con lo que pasar\u00e1 otros  2^(N \u2013 1) d\u00edas visit\u00e1ndoles, durante los cuales, nuestro cliente N seguir\u00e1 satisfecho. Precisamente ese d\u00eda, o bien visita a un cliente posterior, con lo que vuelve a iniciarse la secuencia, o se jubila porque todos est\u00e1n ya satisfechos.<\/p>\n
En definitiva, la soluci\u00f3n al apartado (b) es que todos los clientes est\u00e1n satisfechos exactamente la mitad de los d\u00edas (si contamos el d\u00eda de la jubilaci\u00f3n de Grande).<\/p>\n
Apartado (c)<\/p>\n
Por \u00faltimo, el apartado (c) es el m\u00e1s dif\u00edcil. Volvamos a analizar el problema de tres clientes, para entender primero el patr\u00f3n.<\/p>\n
El primer d\u00eda, todos los clientes estar\u00e1n insatisfechos.<\/p>\n
El segundo d\u00eda, s\u00f3lo el primer cliente est\u00e1 satisfecho.<\/p>\n
El tercer d\u00eda, el segundo cliente est\u00e1 satisfecho, pero todos los dem\u00e1s est\u00e1n insatisfechos.<\/p>\n
El cuarto d\u00eda el primer y el segundo cliente est\u00e1n satisfechos, pero el tercero sigue insatisfecho..<\/p>\n
El quinto d\u00eda, el tercer cliente est\u00e1 satisfecho y los dem\u00e1s no.<\/p>\n
El sexto d\u00eda, el primer y el tercer cliente est\u00e1n satisfechos y el segundo no.<\/p>\n
El s\u00e9ptimo d\u00eda, el primero est\u00e1 insatisfecho y los otros dos, satisfechos.<\/p>\n
El octavo d\u00eda, el de la jubilaci\u00f3n, todos est\u00e1n satisfechos.<\/p>\n
Si conoc\u00e9is el sistema binario de numeraci\u00f3n, y alguna vez hab\u00e9is contado del cero al siete con \u00e9l, seguramente estar\u00e9is familiarizados con este ritmo de crecimiento.<\/p>\n
No es f\u00e1cil pensar en un sistema que describa esta situaci\u00f3n en pocas palabras, pero est\u00e1 claro, por el apartado anterior, que debemos pensar en potencias de 2.<\/p>\n
Por ejemplo, cada d\u00eda determinado, sabremos si un cliente est\u00e1 satisfecho o insatisfecho seg\u00fan la cantidad que nos d\u00e9 al dividir el n\u00famero de d\u00edas entre 2^(N \u2013 1), pero sumando 1 si el resultado no es exacto. Si esa cantidad (tomada como n\u00famero entero) es par, entonces est\u00e1 satisfecho y si no, est\u00e1 insatisfecho. Esta respuesta no es muy satisfactoria, pero podemos comprobar que funciona, de nuevo recursivamente.<\/p>\n
Lo m\u00e1s dif\u00edcil es dar la siguiente caracterizaci\u00f3n, bien por analog\u00eda con los n\u00fameros binarios, bien por similitud con alg\u00fan otro problema que hayamos visto.<\/p>\n
Cada n\u00famero entero se puede escribir de una \u00fanica 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\u00ed, 3 = 1 + 2, o bien 11 = 1 + 2 + 8. Pues bien, si buscamos qu\u00e9 potencias suman exactamente el d\u00eda anterior al que queramos estudiar, entonces, los clientes que ocupen la posici\u00f3n correspondiente a esas potencias ser\u00e1n los \u00fanicos satisfechos. Los dem\u00e1s estar\u00e1n insatisfechos.<\/p>\n
Veamos algunos ejemplos, y veremos por qu\u00e9 sucede. El primer d\u00eda, el n\u00famero es cero, que es suma de cero potencias de 2, y todos los clientes estar\u00e1n insatisfechos. El d\u00eda sexto, por ejemplo, el n\u00famero es 5, suma de 1 y 4, por lo que el primero y el tercero (el cuatro es la tercera potencia de dos) estar\u00e1n satisfechos y todos los dem\u00e1s insatisfechos.<\/p>\n
Podemos comprobar que los primeros d\u00edas lo cumplen de forma precisa. Ahora bien, cuando pasa un d\u00eda m\u00e1s, y sumamos uno al n\u00famero anterior, estamos sumando la primera potencia de 2. Si el primer cliente est\u00e1 insatisfecho, ser\u00e1 ese al que visitamos, por lo que seguir\u00e1 siendo cierta la propiedad, pero si no, sumaremos uno a una suma de la forma 1 + 2 + 4 + 8\u2026., 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 \u00e9se pase a estar satisfecho, y todos los dem\u00e1s queden insatisfechos.<\/p>\n
Por ejemplo. Supongamos que un cierto d\u00eda, tenemos satisfechos a los clientes 1, 2, 3 y 5. Ese d\u00eda ser\u00e1 el que corresponde al n\u00famero  2^0 + 2^1 + 2^2  + 2^4 = 23, es decir el d\u00eda 24. Para pasar al d\u00eda 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\u00ed que el d\u00eda 25 est\u00e1n satisfechos los clientes 4 y 5, y todos los dem\u00e1s insatisfechos.<\/p>\n
Supongo que tendr\u00e9is la cabeza algo liada, pero a\u00fan falta una vuelta de tuerca m\u00e1s sorprendente. Si queremos hacer algo parecido para los clientes insatisfechos, la suma de las potencias que corresponden a sus posiciones es precisamente \u00a1el n\u00famero de d\u00edas que faltan a la doctora para la jubilaci\u00f3n! Esta afirmaci\u00f3n se basa en propiedades similares, y la dejo en el aire como ejercicio para el lector que haya llegado hasta aqu\u00ed.<\/p>\n","protected":false},"excerpt":{"rendered":"
Reto de selecci\u00f3n para el Mathcamp 2017 Se dirige a una edad de: 13-18 Autor: Bill Kuszmaul La doctora Grande es una consultora matem\u00e1tica que se especializa en n\u00fameros grandes. Inicia su negocio con una lista de 100 clientes ordenados en orden de importancia (el 1 es el m\u00e1s importante). Cada d\u00eda, Grande tiene tiempo […]<\/p>\n","protected":false},"author":4267,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2849,3303],"tags":[],"class_list":["post-99","post","type-post","status-publish","format-standard","hentry","category-problemas","category-soluciones"],"_links":{"self":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/99","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/users\/4267"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/comments?post=99"}],"version-history":[{"count":3,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/99\/revisions"}],"predecessor-version":[{"id":804,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/99\/revisions\/804"}],"wp:attachment":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/media?parent=99"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/categories?post=99"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/tags?post=99"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}