Ao ver a
entrada de Matemáticas na Rúa sobre un dos problemas da LII Olimpíada Matemática Española, sentín o ruxerruxe da curiosidade e boteille un ollo aos problemas. Chamoume a atención o enunciado do segundo problema porque restrinxía a operatividade a usar unha ferramenta que denominaba trazador de puntos medios:
Un trazador de puntos medios é un instrumento que debuxa o punto medio exacto de dous puntos previamente sinalados. Partindo de dous puntos a distancia 1 e utilizando só o trazador de puntos medios, debes obter dous puntos a unha distancia estrictamente comprendida entre 1/2017 e 1/2016 , trazando o menor número posible de puntos. Cal é o mínimo número de veces que necesitas utilizar o trazador de puntos medios, e que estratexia seguirías para lograr o teu obxectivo?
Non puiden poñerme a traballar nel inmediatamente. Comencei a facelo nunha garda na que (inusitado) non faltaba ningún profesor. Os ordenadores da sala de profesores estaban ocupados, así que ante a falta de perspectiva doutra diversión quixen meterlle o dente ao problema pero... non me acordaba do enunciado. Así que fixen memoria e así establecín o que pensaba que era o texto do segundo exercicio olímpico, pero que, realmente, era outro problema distinto:
Utilizando só o trazador de puntos medios, debes obter dous puntos entre p=1/2017 e q=1/2016 , trazando o menor número posible de puntos. Cal é o mínimo número de veces que necesitas utilizar o trazador de puntos medios, e que estratexia seguirías para lograr o teu obxectivo?
O primeiro paso é sempre explorar un pouco o problema. Se utilizamos o trazador 3 veces obtemos un conxunto de 7 novos puntos, todos os da forma:
$$\frac { a }{ { 2 }^{ 3 } } \quad \quad con\quad 1\le a\le { 2 }^{ 3 }-1$$
Eventualmente, algunhas das fraccións poden simplificarse.
Ademais a distancia entre un punto obtido no último paso e os máis próximos dos xa existentes no paso anterior é de 1/2
3 . E todo isto pode xeneralizarse para calquera valor do expoñente.
Púxenme a buscar un punto intermedio entre
p e
q. Xa vería despois como obter un segundo punto.
Para colmo de males, non tiña calculadora a man, así que estaba nas mesmas condicións que os sufridos participantes da olimpíada. Os primeiros cálculos:
$$p-q=\frac { 1 }{ 2016 } -\frac { 1 }{ 2017 } =\frac { 1 }{ 4056272 } $$
Debía buscar unha potencia de 2 da orde dos 4 millóns. Sabendo que 2
10=1024, e multiplicando este valor por si mesmo: 2
20=1048576, polo que multiplicando desta vez por 4: 2
22=4194304. Un número intermedio entre
p e
q:
$$\frac { 1 }{ 2016 } <\frac { a }{ { 2 }^{ 22 } } <\frac { 1 }{ 2017 } $$
Parece que había que realizar 22 operacións co trazador. Intentemos determinar o valor de a:
$$\frac { { 2 }^{ 22 } }{ 2016 } <\quad a\quad <\frac { { 2 }^{ 22 } }{ 2017 } $$
Facendo as divisións (a man): 2079'....< a < 20180'..... Velaí que
a=2080. O punto intermedio será:
$$m=\frac { 2080 }{ { 2 }^{ 22 } } =\frac { { 2 }^{ 5 }\cdot 65 }{ { 2 }^{ 22 } } =\frac { 65 }{ { 2 }^{ 17 } } $$
Entón parece que chega con utilizar o trazador 17 veces para obter un punto intermedio.
Aquí quedara.
Cando puiden volver a consultar o enunciado do problema das olimpíadas, decateime de que estivera traballando nun problema distinto. Poderían servir para algo os cálculos anteriores para resolver o problema orixinal? As divisións inacabadas anteriores eran tan axustadas que mostraban claramente que para atopar un punto que distara doutro do conxunto de puntos construídos co trazador un valor que estivera entre
p e
q precisabamos polo menos de 17 pasos. Agora ben. acababa de achar un punto,
m, que distaba do
0 un valor,
m, que caía dentro do pedido polo enunciado, pois
m estaba ente
p e
q. Ademais, pola forma de obtención do punto, mediante o trazador,
m equidista de
0 de de
2m, e resulta que
2m=65/216 era un punto obtido mediante o trazador xusto no paso anterior. Velaí que tiña os dous puntos pedidos. Así, traballando nun problema distinto, achara a solución do problema orixinal.
Queda aínda unha cuestión por responder, a da determinación dos pasos que hai que dar para chegar aos puntos pedidos,
m e
2m. Está claro que basta con determinar a obtención de
m, xa que
2m, tal e como se dixo, obteríase no paso anterior. Para iso basta decatarse de como escribir 65 como potencias de 2:
$$\frac { 65 }{ 64 } =\frac { 64 }{ 64 } +\frac { 1 }{ 64 } =1+\frac { 1 }{ { 2 }^{ 6 } } $$
Sucesivamente, durante 7 utilizacións do trazador, obtemos os valores:
$$\frac { 1 }{ 2 } ,\quad \frac { 1 }{ { 2 }^{ 2 } } ,\frac { 1 }{ { 2 }^{ 3 } } \quad .....,\quad \frac { 1 }{ { 2 }^{ 6 } } $$
Despois calculamos o punto medio entre 1 e este último punto:
$$\frac { 1 }{ 2 } \left( 1+\frac { 1 }{ { 2 }^{ 6 } } \right) =\frac { 65 }{ { 2 }^{ 7 } } $$
Os seguintes 10 pasos consisten na bipartición reiterada deste último punto.
Cómpre comentar un último detalle. Dase a solución partindo do intervalo (0,1), non entre dous puntos calquera que disten 1. Pero isto, como é sabido, non inflúe no proceso nin na xeneralidade dos resultados obtidos.
Outro problema
Traballar con este problema levou que se me fixera presente outra cuestión. Pensemos nas potencias de 2. Máis arriba vimos que hai unha potencia de 2 que comenza por 102: 2
10=1024 e que hai outra que comenza por 104: 2
20=1048576.
Haberá algunha potencia de 2 que teña por primeiras cifras 103? Se a resposta é afirmativa, haberá algunha potencia de 2 que comence por abcdef....., unha serie de cifras determinada calquera?
