Archivo de la etiqueta: media geométrica

Geometría Moderna I: Desigualdades geométricas

Por Rubén Alexander Ocampo Arellano

Introducción

En esta entrada, con la ayuda de varias fórmulas y resultados que hemos visto hasta ahora, mostraremos algunas desigualdades geométricas básicas e importantes, entre ellas la desigualdad entre las medias geométrica y aritmética, y la desigualdad de Erdos Mordell.

Medias armónica, geométrica, aritmética y cuadrática

Teorema 1. Dados dos segmentos de longitudes a y b tenemos las siguientes desigualdades:
2aba+baba+b2a2+b22.

De izquierda a derecha estas cantidades se conocen como media armónica, media geométrica, media aritmética y media cuadrática de a y b.

Demostración. Tracemos un semicírculo tomando como diámetro un segmento BC  de longitud a+b y sea DBC tal que BD=a y DC=b, en D levantamos una perpendicular a BC que corta al arco CB en A, entonces ABC es un triángulo rectángulo con A=π2.

Por criterio de semejanza AA ADBCDA y tenemos que ADCD=BDAD.

Por lo tanto AD es la media geométrica de BD y DC, esto es AD2=BD×CD.

Figura 1

Consideremos O el punto medio de BC, sea EAO tal que DEAO, como ADOAED entonces
ADAE=AOAD
AE=2AD22AO=2BD×DCBC=2aba+b.

Por el teorema de Pitágoras en AED
AD2=AE2+DE2AEAD2aba+bab.

Por el teorema de Pitágoras en ADO
AO2=AD2+DO2ADAOaba+b2.

Ahora tracemos OF el radio perpendicular a BC, entonces
OD=a+b2a=ba2.

Aplicando el teorema de Pitágoras a ODF obtenemos,
DF2=OF2+OD2=(ba2)2+(a+b2)2=a2+b22.

Como OFDFa+b2a2+b22.

◼

Corolario. Sean w, x, y, z números reales positivos entonces:
wxyz(w+x+y+z4)4, y la igualdad se da si y solo si w=x=y=z.

Demostración. Aplicamos la desigualdad entre las medias geométrica y aritmética a los pares de números w, x; y, z.
wxw+x2, yzy+z2.

Por lo tanto, wxyz(w+x2)(y+z2).

Ahora volvemos a usar la desigualdad entre las medias geométrica y aritmética
(w+x)2(y+z)2w+x2+y+z22=w+x+y+z4

Por lo tanto, wxyz4(w+x)2(y+z)2w+x+y+z4.

En consecuencia, wxyz(w+x+y+z4)4.

◼

Desigualdad de Erdos Mordell

Lema de Mordell. Sea ABC y P un punto en su interior, considera D, E y F las proyecciones de P a los lados BC, AC y AB respectivamente, entonces PAsinAPFsinB+PEsinC.

Demostración. Notemos que la circunferencia con diámetro PA pasa por F y por E, pues AP subtiende ángulos rectos en F y E.

Figura 2

Por la ley extendida de los senos,
sinBAC=sin(πBAC)=sinEPF=EFPA, esto implica que PAsinA=EF.

Sean G y H las proyecciones de E y F respectivamente en la recta que pasa por P y D.

◻FBDP es cíclico, pues PB subtiende ángulos rectos en F y D, entonces DBA y FPD son y suplementarios por lo tanto sinDBA=sinHPF=FHFP.

Como resultado FPsinB=FH, igualmente podemos ver que PEsinC=EG.

Sea I=EFHP, por el teorema de Pitágoras podemos ver que IEGE y FIFH,

Por lo tanto, PAsinAPFsinB+PEsinC.

◼

Teorema 2, desigualdad de Erdos Mordell. Sea ABC y P un punto en su interior, considera D, E y F las proyecciones de P a los lados BC, AC y AB respectivamente, entonces PA+PB+PC2(PD+PE+PF).

Demostración. Debido al lema anterior tenemos lo siguiente:
PAPFsinBsinA+PEsinCsinA,
PBPFsinAsinB+PDsinCsinB,
PCPEsinAsinC+PDsinBsinC.

Sumamos estas tres desigualdades
PA+PB+PC

PF(sinBsinA+sinAsinB)+PE(sinCsinA+sinAsinC)+PD(sinBsinC+sinCsinB)

=PF(sin2A+sin2BsinAsinB)+PE(sin2A+sin2CsinAsinC)+PD(sin2B+sin2CsinBsinC).

Sustituimos a y b por a2 y b2 en la desigualdad entre las medias geométrica y aritmética
a2+b22a2b2, por lo tanto, a2+b2ab2.

Aplicamos esto a nuestra suma y como resultado obtenemos
PA+PB+PC2(PD+PE+PF).

◼

Problema 1. Sea ABC e I su incentro, considera P, Q y R los puntos medios de los arcos BC, CA y AB que no contienen a los vértices de ABC, entonces IP+IQ+IRIA+IB+IC.

Solución. Sean D=PQCR, E=QRAP y F=RPBQ.

Figura 3

Por la entrada anterior sabemos que Q es el centro de una circunferencia que pasa por I, A y C, y que R es el centro de una circunferencia que pasa por I, A y B, entonces QA=QI y RA=RI.

Por lo tanto, ◻ARIQ es un rombo, de esto se sigue que QRAI y AE=IE.

Igualmente vemos que RPBI, BF=IF y PQCI, CD=ID.

Aplicamos la desigualdad de Erdos Mordell a PQR y al punto I
IP+IQ+IR2(ID+IE+IF)=2(IC2+IA2+IB2).

En conclusión, IP+IQ+IRIA+IB+IC.

◼

Desigualdades de Euler y de Padoa

Proposición 1, desigualdad de Euler. El circunradio R y el inradio r de todo triangulo cumplen R2r y la igualdad se cumple si y solo si el triángulo es equilátero.

Demostración. La fórmula de Euler nos asegura que 0OI2=R(R2r)=R22Rr, donde I es el incentro y O el circuncentro del triángulo.

Como resultado, R2r.

◼

Proposición 2, desigualdad de Padoa. Sea ABC con lados c=AB, a=BC y b=AC entonces abc(a+bc)(a+cb)(b+ca).

Demostración. Sean s=a+b+c2, R el circunradio y r el inradio de ABC, entonces tenemos las siguientes fórmulas para el área de ABC:
(ABC)=s(sa)(sb)(sc)=abc4R=rs.

Notemos lo siguiente
(a+bc)(a+cb)(b+ca)=(2s2)(2s2b)(2s2a)=8(sc)(sb)(sa)
=8(ABC)2s=8r2s2s=8r2s.

Por otro lado, abc=4Rrs.

Por lo tanto, la desigualdad que queremos mostrar es equivalente a 8r2s4Rrs que a su vez es equivalente a 2rR, lo cual es cierto por la proposición anterior.

◼

Transformación de Ravi

Recordemos que las tangentes desde un punto a una circunferencia son iguales, por lo que los puntos de tangencia del incírculo de un triángulo, divide al perímetro del triángulo en tres pares de segmentos iguales, así que podemos expresar a los lados de un triángulo de esta manera para resolver algunas desigualdades geométricas.

a=BC=y+z, b=AC=x+z, c=AB=x+y.

Figura 4

Problema 2. Para los ángulos internos de un triángulo ABC tenemos la siguiente desigualdad.
sinA2sinB2sinC218.

Solución. Usando la identidad para el seno del ángulo medio y la ley de los cosenos tenemos:
sin2A2=12(1cosA)=12(1+a2(b2+c2)2bc)
=a2(bc)24bc=y2+2yz+z2(zy)24bc=yzbc.

Igualmente tenemos
sin2B2=xzac y sin2C2=xyab.

A continuación despejamos y hacemos el producto
sinA2sinB2sinC2=yzxzxyabc.

Ahora aplicamos la desigualdad entre las medias geométrica y aritmética
yzxzxyabc1abc(y+z2)(x+z2)(x+y2)=abc8abc=18.

Por lo tanto, sinA2sinB2sinC218.

◼

Desigualdad de Nesbitt

Proposición 3. Sean a, b y c tres números positivos entonces la siguiente desigualdad es cierta
(a+b+c)(1a+1b+1c)9.

Demostración. La desigualdad entre las medias geométrica y aritmética puede ser vista como
ab+ba2abba=2.

Por lo tanto,
(a+b+c)(1a+1b+1c)=ab+ba+ac+ca+bc+cb+36+3=9.

◼

Proposición 4. Desigualdad de Nesbitt. Para cualesquiera números positivos a, b, c ocurre que ab+c+ba+c+ca+b32.

Demostración.
ab+c+ba+c+ca+b
=ab+c+b+cb+c+ba+c+a+ca+c+ca+b+a+ba+b3
=a+b+cb+c+a+b+ca+c+a+b+ca+b3
=(a+b+c)(1b+c+1a+c+1a+b)3
=12((a+b)+(a+c)+(b+c))(1b+c+1a+c+1a+b)3
923=32.

Donde la última desigualdad se obtiene al aplicar la proposición anterior.

Por lo tanto, ab+c+ba+c+ca+b32.

◼

Desigualdad de Weitzenböck

Proposición 5. Desigualdad de Weitzenböck. Si a, b, c son las longitudes de los lados de ABC entonces a2+b2+c243(ABC).

Demostración. De acuerdo a la fórmula de Herón
(ABC)=s(sa)(sb)(sc)
=(a+b+c2)(b+ca2)(a+cb2)(a+bc2)
=142(a2b2+a2c2+b2c2)(a4+b4+c4).

Por otro lado
(1)(a2b2)2+(b2c2)2+(c2a2)20

2(a4+b4+c4)2(a2b2+a2c2+b2c2)0
43(a4+b4+c4)43(a2b2+a2c2+b2c2)
43(a4+b4+c4)+3(a4+b4+c4)+2(a2b2+a2c2+b2c2)3
43(a2b2+a2c2+b2c2)+3(a4+b4+c4)+2(a2b2+a2c2+b2c2)3
a4+b4+c4+2(a2b2+a2c2+b2c2)32(a2b2+a2c2+b2c2)(a4+b4+c4)
(a2+b2+c2)232(a2b2+a2c2+b2c2)(a4+b4+c4)=(4(ABC))2.
a2+b2+c243(ABC).

De la desigualdad (1) podemos notar que la igualdad ocurre si y solo si a=b=c, es decir el triángulo es equilátero.

◼

Más adelante…

En la próxima entrada estudiaremos algunas propiedades de las medianas y el centroide de un triángulo.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Sea P un punto en el interior de un triangulo ABC, muestra que al menos uno de los ángulos BAP, CBP y ACP es igual a π6.
  2. Considera P un punto en el interior de ABC cuyo circunradio es R, demuestra que PABC2+PBAC2+PCAB21R.
  3. Sea P un punto en el interior de ABC, denota por Ra, Rb, Rc los circunradios de los triángulos PBC, PAC y PAB respectivamente, prueba que PB×PCRa+PA×PCRb+PA×PBRcPA+PB+PC.
  4. Si a, b y c son los lados de un triangulo prueba que (a+b)(b+c)(a+c)8(a+bc)(b+ca)(a+cb).
  5.  Sean ABC, α=BAC, β=CBA, γ=ACB, muestra que cosα+cosβ+cosγ32.
  6. Sean ABC, AD, BE, CF, sus alturas y H el ortocentro muestra que:
    i) ADHD+BEHE+CFHF9,
    ii) HDHA+HEHB+HFHC32.
Figura 5
  1. Sea ABC un triángulo rectángulo con catetos a y b e hipotenusa c, muestra que se cumple la siguiente desigualdad a+b2c.
  2. Considera A y B los puntos medios de BC y AC en ABC, muestra que 3(BC+AC)>2(AA+BB).

Entradas relacionadas

Fuentes

  • Andreescu, T., Korsky, S. y Pohoata, C., Lemmas in Olympiad Geometry. USA: XYZ Press, 2016, pp 287-297.
  • Gomez, A. y Bulajich, R., Geometría. México: Instituto de Matemáticas, 2002, pp 27-29, 98-103.
  • Art of Problem Solving
  • Wikipedia
  • Cut the Knot

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»

Seminario de Resolución de Problemas: Desigualdades básicas

Por Leonardo Ignacio Martínez Sandoval

Introducción

En las entradas correspondientes a esta parte del curso aprenderemos varias técnicas que nos permitirán resolver problemas que involucren desigualdades. El área es enorme y hay libros enteros dedicados a ello. Nosotros sólo veremos algunas técnicas. Comenzaremos con desigualdades básicas y nos enfocaremos en los siguientes temas:

  • Desigualdad x20 y desigualdad del triángulo
  • Desigualdades de medias
  • La desigualdad de Cauchy-Schwarz
  • Técnicas de cálculo en desigualdades

En esta entrada veremos el primer inciso, que consiste de dos ideas muy sencillas:

Desigualdad x20. El cuadrado de cualquier número real es mayor o igual a cero. Es cero si y sólo si el número es cero.

Desigualdad del triángulo. Si V es un espacio vectorial con norma , entonces para cualesquiera vectores u y v se tiene que u+vu+v.

La desigualdad x20 parece muy inocente. Sin embargo, es una herramienta muy versátil cuando se combina con manipulaciones algebraicas creativas. La desigualdad del triángulo la estamos enunciando para espacios vectoriales con norma en general. Dos casos particulares que a lo mejor te son más familiares son los siguientes:

Desigualdad del triángulo para R. Si a y b son números reales, entonces |a|+|b||a+b|.

Desigualdad del triángulo en Rn. Si ABC es un triángulo en el plano (o dimensiones más altas) , de lados de longitudes AB=c, BC=a y CA=b, entonces
a+bcb+cac+ab.

Si una de las igualdades se da, ABC es un triángulo degenerado, es decir, con sus tres vértices alineados. En otro caso, todas las desigualdades son estrictas.

Veamos aplicaciones de estas desigualdades básicas.

La desigualdad a2+b22ab

Comenzaremos probando de dos formas distintas una desigualdad que también resulta útil en otras ocasiones.

Problema. Sean a y b números reales mayores o iguales a cero. Muestra que a+b2ab, y que la igualdad se da si y sólo si a y b son iguales.

A esta desigualdad se le conoce como la desigualdad MA-MG para dos números reales. También forma parte de las desigualdades básicas que te ayudará conocer. Se llama así pues en el lado izquierdo tenemos a la media aritmética de los números a y b, y al lado derecho tenemos la media geométrica de los números a y b. En realidad la desigualdad se vale para más reales no negativos, pero esto lo veremos en otra entrada.

Sugerencia pre-solución. El problema se puede resolver tanto de manera algebraica, (usando x20) como de manera geométrica (usando la desigualdad del triángulo).

Para resolverlo de la primera forma, trabaja hacia atrás. Haz manipulaciones algebraicas para formular problemas equivalentes hasta que llegues a una desigualdad obvia.

Para resolverlo de la segunda forma, haz una figura en la que puedas representar tanto a la media geométrica como a la aritmética. Una forma de hacerlo es comenzar con una semicircunferencia de diámetro a+b.

Para identificar el caso de igualdad, haz un análisis de casos.

Solución algebraica. Queremos mostrar que a+b2ab. Pasando el dos multiplicando, y luego 2ab restando al lado izquierdo, esta desigualdad igualdad ocurre si y sólo si a+b2ab0. En el lado izquierdo identificamos un binomio al cuadrado, que se puede factorizar para dar la desigualdad equivalente (ab)20.

Esta desigualdad es de la forma x20, así que es claramente cierta. La igualdad ocurre si y sólo si ab=0, lo cual sucede si y sólo si a=b. Todos los pasos que hicimos son reversibles. Esto termina la solución.

◻

Solución geométrica. Consideremos la siguiente figura, en donde tenemos una semicircunferencia de diámetro AB=a+b y centro O. Aquí C es un punto en AB tal que AC=a y entonces CB=b. Además, D es un punto sobre la circunferencia tal que DC es perpendicular a AB. Llamemos d=CD.

Prueba visual de la desigualdad entre la media aritmética y media geométrica usando desigualdades básicas
Prueba visual de MA-MG

Como AOD y BOD son isósceles por tener dos lados iguales al radio de la circunferencia, tenemos que ADO=DAO y BDO=DBO. Usando estas igualdades y que la suma de los ángulos internos de ABD es 180, se puede mostrar que el ángulo ADB es de 90.

De este modo, ACD y DCB son semejantes (por ser ambos semejantes a ABD por criterio AA). Por la semejanza, tenemos que ad=db, de donde d=ab.

Para terminar la demostración, tomamos un punto E sobre DO tal que EOC=ECO. Por la desigualdad del triángulo en DEC, tenemos que

ab=DCDE+EC=DE+EO=DO=a+b2.

Con esto demostramos la desigualdad. Para terminar el problema, necesitamos ver cuándo se dan los casos de igualdad. Se tiene la igualdad si y sólo si DEC es un triángulo degenerado, lo cual sucede si y sólo si E está en el segmento DC. Esto sólo es posible cuando DO es perpendicular a AB, lo cual sucede si y sólo si C=O, si y sólo si AC=CB, si y sólo si a=b.

◻

Desigualdades básicas aplicadas a un problema de la Olimpiada Mexicana de Matemáticas

El siguiente problema apareció como parte de los exámenes selectivos que el Comité Nacional de la Olimpiada Mexicana de Matemáticas envía a los estados para seleccionar a sus estudiantes en distintas etapas. Tiene muchas formas de resolverse, pero veamos cómo se puede resolver con desigualdades básicas.

Problema. Sean a,b,c,d reales positivos con a2+b2+c2+d2=4. Muestra que a5+b5+c5+d5a+b+c+d

Sugerencia pre-solución. Modifica el problema a mostrar como desigualdad auxiliar que para un real no negativo x se tiene que x52x2x+20. Esta desigualdad se puede demostrar usando que los cuadrados son no negativos.

Solución. Vamos a probar primero la desigualdad x52x2x+20. Para que sea un poco más fácil, factorizaremos la expresión del lado izquierdo.

Notemos que 1 es una raíz de x52x2x+2, de modo que por el teorema del factor podemos factorizar x1 del polinomio. Obtenemos que x52x2x+2=(x1)(x4+x3+x2x2).

Notemos que, nuevamente, 1 es una raíz de (x4+x3+x2x2). Al factorizar x1 de nuevo, obtenemos que x52x2x+2=(x1)2(x3+2x2+3x+2).

Ya estamos listos para probar la desigualdad que queremos. Notemos que (x1)20 y que x3+2x2+3x+2 es mayor o igual que cero para x0 pues es un polinomio con puros coeficientes positivos. Esto prueba la desigualdad auxiliar. Reescribiéndola, tenemos que x52x2+x2. Aplicándola en esta forma a los cuatro reales positivos a,b,c,d del problema, y usando que la suma de cuadardos es 4, obtenemos que
a5+b5+c5+d52(a2+b2+c2+d2)+a+b+c+d8=24+a+b+c+d8=a+b+c+d.

Esto termina el problema.

◻

El primer paso parece un poco artificial. ¿Por qué queremos probar esa desigualdad auxiliar? En otra entrada de blog escribí cómo se puede llegar a las ideas de esta solución.

Desigualdad del triángulo aplicada a la construcción de tetraedros

Si pegamos cuatro triángulos equiláteros en el espacio se hace un tetraedro regular. De manera similar, si pegamos cuatro triángulos como el siguiente, también se hace un tetraedro en el espacio:

Pegar cuatro triángulos congruentes para hacer un tetraedro

La intuición nos dice que debería poderse con cualquier triángulo. Pero esta intuición está mal.

Problema. Sea ABC un triángulo con un ángulo mayor a 90. Muestra que no existe ningún tetraedro en el espacio tal que sus cuatro caras sean congruentes a ABC.

Sugerencia pre-solución. Procede por contradicción. Por simetría, puedes asumir que el ángulo mayor a 90 es el ángulo en A. Usa como punto auxiliar al punto medio de BC y usa desigualdades.

Solución. Una observación inicial es que si ABC es un triángulo, M es el punto medio de BC y su ángulo interno en A es mayor a 90, entonces 2AM<BC. Esto se muestra trazando una circunferencia de diámetro BC.

Desigualdad para la mediana en términos del ángulo que hace.

De hecho,

  • Un punto X está sobre la circunfencia si y sólo si BXC=90, si y sólo si OX=OA.
  • X está dentro de la circunferencia si y sólo si BXC>90, si y sólo si OX<OA y
  • X está fuera de la circunferencia si y sólo si BXC<90, si y sólo si OX>OA.

Resolvamos el problema. Sin pérdida de generalidad, el ángulo en A es mayor a 90. Entonces AM<BC2, de donde 2AM<BC.

Supongamos que se pudiera hacer en el espacio un tetraedro WXYZ tal que cada una de las caras es congruente al triángulo ABC. Sin pérdida de generalidad, tenemos que
WX=YZ=ABXY=ZW=BCWY=XZ=CA.

Tomemos el punto medio M de XY. En ZMW, tenemos que
ZM=AMWM=AM.

Así, usando la desigualdad del triángulo en ZMW tenemos que 2AM=ZM+WMZW=BC.

Esto es una contradicción con la desigualdad 2AM<BC que ya habíamos mostrado.

◻

Más problemas

Puedes encontrar más problemas de desigualdades básicas en la sección 7.1 del libro Problem Solving through Problems de Loren Larson. También puedes consultar más técnicas y problemas en el libro Desigualdades de la Olimpiada Mexicana de Matemáticas.

Un problema de probabilidad y escuchar música

Por Leonardo Ignacio Martínez Sandoval

El problema

Les comparto un problema que se me ocurrió en las (muchas) horas que he pasado en el carro escuchando música, cuando vivía en la Ciudad de México. El estéreo del carro ordena las canciones alfabéticamente. Tiene un botón que permite «avanzar una canción». Pero a veces tarda mucho: si estoy escuchando «Adele – Hello», hay que apretar el botón muchas veces para llegar a «Shakira – Dónde están los ladrones».

En esas épocas descubrí una estrategia «intuitiva» para llegar más rápido a la canción. La idea es la siguiente: pasar temporalmente al modo de «canción aleatoria», apretar el botón unas cuantas veces para acercarme a la canción que quiero (en el ejemplo anterior, digamos que después de dos o tres veces el botón me lleva a «Paquita la del Barrio – Rata de dos Patas»), y de ahí quitar el aleatorio y avanzar normal. Eso, intuitivamente, siempre me ahorró muchos pasos. El problema consiste en encontrar la estrategia óptima, en donde se permiten mezclar pasos normales y aleatorios.

Para eso, voy a plantear un problema muy concreto. De aquí en adelante supondré que el lector sabe un poco de probabilidad. Pensemos que hay 2n canciones, numeradas de 1 a 2n. Estoy en la canción n y quiero llegar a la canción 2n. Pensemos que el estéreo tiene exactamente dos botones, el A que avanza 1 (y de 2n lleva a 1), y el B que lleva a una canción aleatoria (cualquiera de las canciones, incluida la actual, tiene probabilidad 1/2n de ser elegida). En cada paso se permite ver en qué canción estoy, y de ahí decidir apretar A o B. ¿Cuál es la estrategia que en valor esperado tiene menos pasos? ¿Cuál es ese valor esperado?

En la imagen de aquí abajo se muestra un ejemplo de una forma de apretar los botones para n=5, con 2n=10 canciones. Las flechas rojas corresponden a avanzar 1 apretando el botón A. Las flechas azules corresponden a ir a un lugar aleatorio apretando el botón B. Se apretaron los botones en el orden ABBAA, de modo que se hicieron 5 pasos.

Ejemplo de estrategia ABBAA
Un ejemplo en el que se usa la estrategia ABBAA. La canción 1 es de ABBA. Es Dancing Queen. «Feel the beat form the tambourine… Oh yeah…».

Ese es el enunciado del problema. De aquí en adelante empiezo a hablar de ideas para resolverlo, así que si quieres intentarlo, este es el momento correcto.

Primeras ideas

Notemos que la estrategia «siempre A, hasta llegar a 2n» toma exactamente n pasos siempre. La estrategia «siempre B» es para intentar atinarle, y en cada paso tiene probabilidad de éxito 1/2n. Entonces, en esta segunda estrategia la cantidad de pasos requeridos es una variable aleatoria con distribución geométrica de parámetro p=1/2n, de modo que el número esperado de pasos es 1/p=2n.

Sin embargo, suena a que la estrategia esbozada al inicio de esta entrada es intuitivamente mejor: usar el B para acercarse y luego el A para llegar.

La solución

Vamos a mostrar que la mejor estrategia en valor esperado es la siguiente: «apretar el botón B hasta llegar aproximadamente al intervalo [n2n,n], y de ahí apretar el botón A» hasta llegar a n.

El primer argumento es que en cada paso, lo que hace la estrategia sólo depende de en qué canción estamos. En efecto, el paso A es determinista y el B es una variable uniforme independiente de todo lo demás.

El segundo argumento es que, si en algún momento de la estrategia usamos el botón A, entonces después de ello nunca nos conviene usar el botón B. Lo probamos por contradicción: supongamos que por cualquier razón en la estrategia óptima tenemos que hacer un AB. El paso A es determinista, y sabíamos exactamente a qué canción nos iba a llevar (a la siguiente). Pero hacer el paso B en cualquier lugar que estemos es simétrico, pues nos lleva a una canción aleatoria. Si a priori sabíamos que íbamos a hacer un paso B, lo mejor es hacerlo lo antes posible. Así, la estrategia que substituye esos pasos AB por B se ahorra un paso, y no es óptima. Contradicción.

Ahora, afirmo lo siguiente. Si la estrategia óptima es apretar A cuando estamos en la canción j, entonces también va a ser apretar A cuando estemos en cualquier canción k con jk<2n. Esto es debido al argumento anterior: al apretar A llegamos a j+1, que por el párrafo de arriba, no le puede tocar B. Entonces le toca A. De ahí llegamos a j+2, que de nuevo no le puede tocar B. Y así sucesivamente (inductivamente), hasta llegar a 2n1.

Lo que acabamos de probar es que la estrategia óptima se ve de la siguiente manera para algún entero k: «Apretar B hasta que lleguemos a alguno de los últimos k elementos. De ahí, apretar A hasta llegar a 2n.» Nos falta determinar cuál es la mejor k que podemos usar.

A estas alturas ya podemos calcular explícitamente el valor esperado de pasos en esta estrategia. El evento «llegar a alguno de los últimos k elementos» tiene probabilidad k/2n de ocurrir cada que se aprieta el botón B, así que la cantidad de veces que hay que apretar B para ello es una variable aleatoria geométrica de valor esperado 2n/k. Una vez que llegamos a los últimos k elementos, caemos a cualquier elemento del intervalo {2nk+1,2nk+2,,2n} con la misma probabilidad, y respectivamente nos tomará {k1,k2,,0} pasos en llegar a 2n, es decir, la cantidad de pasos que hacemos es una variable aleatoria uniforme discreta de media (k1)/2.

Así, en total usamos (2n/k)+(k1)/2 pasos para llegar. Queremos lograr que esta expresión sea lo más pequeña posible. Usando la desigualdad entre la media geométrica y la aritmética, notamos que 2nk+k12=2nk+k2122n12, y que la igualdad se da si y sólo si 2nk=k2, es decir, si y sólo si k=2n. En este caso, la cantidad media de pasos que usamos es 2n12.

Aquí arriba hicimos un poquito de trampa. En realidad k=2n tiene sentido para la estrategia sólo cuando n es un número entero. Sin embargo, por la convexidad de la función 2nk+k2 tenemos la garantía de que o bien 2n o bien 2n dan el máximo.

Conclusión y otros problemas

Está cool que hayamos bajado la cantidad de pasos que se necesitan de valor esperado de algo que era n a algo que es del tamaño 2n. Para hacerse una idea de los pasos que se pueden ahorrar, toma una colección de 800 canciones. Originalmente se necesitaban 400 pasos +1 para ir de la mitad al final. Con la nueva estrategia se requieren como 40.

Hacer esta estrategia en la vida real es un poco complicado pues los estéreos no muestran el número exacto de la canción en la que se está, además de que es difícil memorizar a qué canción le toca qué número. Pero a veces sí muestran el nombre de la canción y más o menos «se le puede aproximar».

Hay un par de variantes interesantes. Una es ¿qué sucede si además de tener botón +1 y aleatorio, también tenemos botón 1?. En esta variante la solución no cambia mucho, pero es bueno intentarla para repasar las ideas de la prueba.

La otra variante es la siguiente. La estrategia óptima, como está descrita arriba, tiene un problema: es posible que nunca termine, o que tome muchísimos pasos en terminar (esto será muy improbable y por eso el valor medio se compensa). Así, imaginemos que queremos la restricción adicional de que la estrategia que usemos nunca use más de, digamos, 4n pasos. En esta variante: ¿cuál es la estrategia óptima? ¿cuántos pasos toma?

¿Ahora qué?

Si te gustó esta entrada, puedes compartirla o revisar otras relacionadas con matemáticas a nivel universitario:

Modificar el problema

Por Leonardo Ignacio Martínez Sandoval

HeuristicasOtra técnica de resolucion de problemas es proponer un problema que ayude, pero que no necesariamente sea equivalente. Esto puede ser a través de problemas más particulares o de problemas más difíciles.

En esta serie de videos veremos esta técnica en acción en cuatro problemas.

Ir a los videos…