Archivo de la etiqueta: desigualdad

Seminario de Resolución de Problemas: Sucesiones monótonas y acotadas

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

Introducción

En entradas anteriores hablamos de sucesiones aritméticas y geométricas. También hablamos de sucesiones periódicas y pre-periódicas. Cuando una sucesión es de cualquiera de estos tipos, entonces no es tan compleja pues depende de pocos parámetros. Hay otros dos sentidos en los que podemos restringir una sucesión: orden y en tamaño. Esto nos da, respectivamente, las definiciones de sucesiones monótonas y acotadas.

Por un lado, para hablar de sucesiones acotadas se necesita una noción de distancia. Por otro, para hablar de sucesiones monótonas se necesita de una noción de orden. En las siguientes secciones veremos ejemplos numéricos, pero mucho de lo que discutimos en esta entrada es generalizable a espacios métricos o conjuntos ordenados arbitrarios.

A menos que digamos lo contrario, supondremos que las sucesiones de las que hablamos empiezan con un término de subíndice $0$, aunque esto en realidad no afecta las ideas que discutimos.

Sucesiones acotadas

Las sucesiones acotadas son aquellas que siempre están «cerca de un punto». Cuando estamos hablando de sucesiones de reales, o de elementos en un conjunto linealmente ordenado, podemos hablar de cotas por arriba y por abajo.

Definición. Sea $\{x_n\}$ una sucesión de reales. Decimos que $\{x_n\}$ es:

  • Inferiormente acotada si existe un real $m$ tal que $x_n\geq m$ para todo entero $n\geq 0$.
  • Superiormente acotada si existe un real $M$ tal que $x_n\leq M$ para todo entero $n\geq 0$.
  • Acotada si es inferiormente acotada y superiormente acotada.

Se puede usar como definición alternativa del tercer punto la conclusión de siguiente proposición. Esto permite definir sucesiones acotadas en cualquier espacio normado.

Proposición. Sea $\{x_n\}$ una sucesión de reales. Se tiene que $\{x_n\}$ es acotada si y sólo si existe un real $A\geq 0$ tal que $|x_n|\leq A$ para todo entero $n\geq 0$.

Cualquier sucesión periódica de reales toma sólo una cantidad finita de valores, así que es acotada. ¿Cómo son las sucesiones aritméticas y geométricas que son acotadas?

Problema. La sucesión $\{x_n\}$ está definida para $n\geq 1$ y está dada por $$x_n=3+\sqrt{3+\sqrt{3+\sqrt{\ldots\sqrt{3+\sqrt{3}}}}},$$ en donde tenemos $n$ signos de raíz cuadrada. Muestra que esta sucesión es acotada.

Sugerencia pre-solución. La notación es algo difícil. Usa una mejor notación, conjetura una cota superior trabajando hacia atrás, y pruébala por inducción.

Solución. El primer término es $3+\sqrt{3}$ y para $n\geq 1$ tenemos $$x_{n+1}=3+\sqrt{x_n} \geq 0.$$ Falta ver que la sucesión está acotada superiormente.

Trabajemos hacia atrás, suponiendo que podemos mostrar por inducción que un real $C$ es cota superior. Al hacer el paso inductivo, nos bastaría que $$3+\sqrt{C}\leq C.$$ Esto se cumple para muchos valores de $C$, por ejemplo, podemos tomar $C=9$.

Hagamos la prueba formalmente. Mostraremos que $\{x_n\}$ está acotada superiormente por $9$. El primer término es $3+\sqrt{3}$, que está acotado por $9$. Si $x_n$ está acotado por $9$, entonces $$x_{n+1}=3+\sqrt{x_n}\leq 3+\sqrt{9}\leq 3+3 \leq 9.$$ Esto termina la inducción y muestra que $\{x_n\}$ es acotada.

$\square$

Sucesiones monótonas

Otra forma de limitar los «movimientos» de una sucesión es a través de una noción de orden. Las siguientes definiciones son para sucesiones de reales, pero es sencillo extenderlas a cualquier conjunto parcialmente ordenado.

Definición. Sea $\{x_n\}$ una sucesión de reales. Decimos que $\{x_n\}$ es:

  • Creciente si para todo par de enteros enteros $k>l\geq 0$ se tiene que $x_k\geq x_l$.
  • Estrictamente creciente si para todo par de enteros enteros $k>l\geq 0$ se tiene que $x_k> x_l$.
  • Decreciente si para todo par de enteros enteros $k>l\geq 0$ se tiene que $x_k\leq x_l$.
  • Estrictamente decreciente si para todo par de enteros enteros $k>l\geq 0$ se tiene que $x_k<x_l$.

Las sucesiones monótonas son aquellas que cumplen alguna de las definiciones anteriores.

Aunque la definición requiere que cierta desigualdad se cumpla para todo par de índices $k>l\geq 0$, basta con demostrar que se cumple para $k=n+1$ y $l=n$, es decir, para índices consecutivos. Esto típicamente se reduce a demostrar una desigualdad. Hablaremos más adelante de técnicas para resolver desigualdades, pero por el momento veremos un ejemplo sencillo.

Problema. Muestra que la sucesión $\{x_n\}$ dada por $$x_n=\left(1 +\frac{1}{n}\right)^n$$ es estrictamente creciente.

Sugerencia pre-solución. Basta con que pruebes la desigualdad para subíndices consecutivos. Para hacer esto, usa el binomio de Newton y modifica el problema a comparar ciertos términos.

Solución. Tenemos que mostrar que $$\left(1+\frac{1}{n}\right)^{n} \leq \left(1+\frac{1}{n+1}\right)^{n+1}.$$

Para mostrar esto, primero demostraremos la siguiente desigualdad auxiliar para $0\leq k \leq n+1$: \begin{equation}\binom{n}{k}\frac{1}{n^k}\leq \binom{n+1}{k}\frac{1}{(n+1)^k}.\end{equation}

Si $k=n+1$, la desigualdad se cumple pues el término izquierdo es $0$. Para $0\leq k \leq n$, esta desigualdad es equivalente a la desigualdad $$\frac{\binom{n+1}{k}}{\binom{n}{k}}\geq \left(\frac{n+1}{n}\right)^k.$$ Usando la expresión en términos de factoriales y simplificando el lado izquierdo, tenemos que
\begin{align*}
\frac{\binom{n+1}{k}}{\binom{n}{k}}&=\frac{\frac{(n+1)!}{k!(n+1-k)!}}{\frac{n!}{k!(n-k)!}}\\
&=\left(\frac{n+1}{n}\right)\cdot\left(\frac{n}{n-1}\right)\cdot \ldots\cdot\left(\frac{n+2-k}{n+1-k}\right)
\end{align*}

Afirmamos que cada uno de los $k$ términos de la derecha es mayor o igual a $\frac{n+1}{n}$. Para ello, basta mostrar que la sucesión $\left\{\frac{m+1}{m}\right\}$ definida para $m\geq 1$ es decreciente. Pero esto es fácil de ver, pues cada término es $\frac{m+1}{m}=1+\frac{1}{m}$ que claramente decrece conforme $m$ crece. Con esto terminamos la prueba de la desigualdad auxiliar (1).

Sumando la desigualdad (1) para todos los valores de $k$ de $0$ a $n+1$ y usando el binomio de Newton, obtenemos la desigualdad deseada.

$\square$

Más allá de sucesiones monótonas

De entre las sucesiones monótonas, hay algunas que podemos entender mejor. Una sucesión de reales puede ser estrictamente creciente, y no irse a infinito. Por ejemplo, considera la sucesión: $$0.3, 0.33, 0.333, 0.3333,\ldots$$ en donde de un término al siguiente se agrega un dígito $3$. Esta sucesión es estrictamente creciente, pero todos los términos son menores a $\frac{1}{3}$.

Hay diferentes grados de información que podemos tener de una sucesión con respecto a cuánto crece. En cada uno de los siguientes puntos, cada vez sabemos mejor qué tanto crece la sucesión:

  • Saber que la sucesión es creciente
  • Saber que es estrictamente creciente
  • Determinar si es acotada superiormente
  • Conocer qué tan rápido crece

Por supuesto, hay una jerarquía análoga para funciones decrecientes.

Veamos un ejemplo de entender bien el crecimiento de una sucesión. El siguiente problema apareció en uno de los concursos de matemáticas Pierre Fermat que organiza el IPN.

Problema. Considera una sucesión $\{a_n\}$ de reales tal que $a_0>0$ y para cada $n\geq 0$ se cumple que $a_{n+1}=a_n+\frac{1}{a_n}$. Muestra que $a_{200}>20$.

Sugerencia pre-solución. En vez de entender la sucesión $\{a_n\}$, modifica el problema a entender la sucesión $\{a_n^2\}$, que es más fácil de estudiar cómo crece. En cierta forma, tendrás que generalizar el problema, entendiendo qué tan grande es cada término.

Solución. Es fácil ver que la sucesión es creciente. Para ello podemos probar simultáneamente por inducción que cada término es positivo y mayor que el anterior. Sin embargo, esto es todavía muy débil para nuestros fines: aún no sabemos si la sucesión superará $20$ y, peor aún, no sabemos si sucederá antes del término $200$.

Quedémonos con el hecho de que $a_n$ es de términos positivos. Pero en vez de estudiar cómo crece $\{a_n\}$, mejor estudiamos cómo crece $\{a_n^2\}$. Observemos que
\begin{align*}
a_{n+1}^2&=\left(a_n+\frac{1}{a_n}\right)^2\\
&=a_n^2+2+\frac{1}{a_n^2}\\
&>a_n^2+2,
\end{align*}

de modo que podemos probar inductivamente que $a_n^2\geq 2n$. De aquí, deducimos que $a_n\geq \sqrt{2n}$. En particular, $a_{200}\geq \sqrt{400}=20$.

$\square$

Descenso infinito

Una herramienta bastante útil para la resolución de problemas con enteros es el siguiente resultado. En cierto sentido, habla de cómo son las sucesiones monótonas y acotadas de enteros.

Teorema (principio del descenso infinito). No existen sucesiones estrictamente decrecientes e inferiormente acotadas de enteros.

De manera similar, no existen sucesiones estrictamente crecientes y superiormente acotadas de enteros.

Veamos un ejemplo de la Olimpiada Centroamericana de Matemáticas.

Problema. Aplicar un desliz a un entero positivo $n\geq 5$ consiste en cambiar a $n$ por $\frac{n+p^2}{p}$, con $p$ un divisor primo de $n$. Muestra que tras aplicar repetidamente deslices a un entero $n\geq 5$, siempre se llega a $5$.

Sugerencia pre-solución. Usa el principio de descenso infinito.

Solución. Si comenzamos con $n=5$, la única opción es pasar a $\frac{5+25}{5}=6$. Si comenzamos con $n=6$, ambos deslices (con $2$ ó $3$) nos llevan a $5$.

Veremos que a partir de cualquier entero $n\geq 7$, tras aplicar deslices siempre se llega a $5$.

Afirmamos lo siguiente:

  • Si $n$ es primo, sólo tiene un desliz que lo pasa a $n+1$.
  • Para $n\geq 7$ no primo, aplicar un desliz lo disminuye en al menos $2$.
  • Para $n\geq 5$, aplicar un desliz lo lleva a un número mayor o igual a $5$.

La primera afirmación es fácil de ver, pues si $n=p$, el único divisor primo que tiene es $p$ y así, el único desliz que tiene lo manda a $$\frac{p^2+p}{p}=p+1=n+1.$$

Para la segunda afirmación, necesitamos mostrar que si $n\geq 7$ no es primo y $p$ lo divide, entonces $$\frac{n+p^2}{p}\leq n-2.$$ Reescribiendo esta afirmación, necesitamos mostrar que $$np\geq p^2+n+2p.$$ Como $n$ no es primo, $n=pq$ con $q\geq 2$. Como $p$ es primo, $p\geq 2$.

Reescribiendo la desigualdad que queremos mostrar en términos de $p$ y $q$, y cancelando un factor $p$ de ambos lados, lo que necesitamos es $$pq\geq p+q+2.$$ restando $p+q-1$ de ambos lados y factorizando el lado izquierdo, esto es equivalente a $$(p-1)(q-1)\geq 3.$$

Hagamos un análisis de casos para los primos $p$ y $q$

  • Si $p=q=2$ entonces $n=4$, que no es un caso que nos interese.
  • Si $p=2$ y $q=3$, o $p=3$ y $q=2$, entonces $n=6$, pero para la segunda afirmación estamos suponiendo $n\geq 7$.
  • Así, $p\geq 3$ y $q\geq 3$, de modo que $(p-1)(q-1)\geq 4$, que implica la desigualdad que queremos.

Esto prueba la segunda afirmación.

La tercera afirmación se prueba notando que tras el desliz, un número se va a $\frac{n}{p}+p \geq 2\sqrt{n}\geq 2\sqrt{5}>4$, y como esta esta expresión es entera, se tiene $\frac{n}{p}+p\geq 5$.

Estamos listos para dar la prueba. Por la tercer afirmación, la sucesión siempre es $\geq 5$. Si acaso la sucesión crece, fue porque teníamos un primo $p$ que pasó a $p+1$. Pero entonces $p+1$ no es primo y al paso siguiente es menor o igual a $p-1$ por la segunda afirmación. Así, cada dos pasos, la sucesión decrece estrictamente, a menos que pase por $6$. Por el principio de descenso infinito, no es posible que siempre decrezca. Así, en algún momento pasa por $6$, y entonces al paso siguiente será $5$.

$\square$

Más problemas

Esta entrada es una extensión de las secciones 1, 2 y 3 del curso de sucesiones que impartí para los entrenadores de la Olimpiada Mexicana de Matemáticas. Puedes consultar las notas de este curso en el siguiente PDF, en donde hay más problemas de práctica:

Curso de SucesionesDescarga

Álgebra Lineal I: Ángulos, norma, distancia y desigualdad de Minkowski

Por Leonardo Ignacio Martínez Sandoval

4 respuestas

Introducción

Estamos listos para hablar de varias nociones geométricas como ángulo, norma, distancia y de la desigualdad de Minkowski. Antes de hacer eso, hagamos un breve repaso de qué hemos hecho en estas últimas entradas.

Primero, hablamos de formas bilineales y de su formas cuadráticas asociadas. Segundo, vimos cómo a través de la identidad de polarización podemos asignar una única forma bilineal simétrica a una forma cuadrática. Finalmente, en la última entrada nos enfocamos en las formas bilineales simétricas que cumplían cierta condición de positividad.

En esa misma entrada definimos producto interior, que simplemente es una forma bilineal simétrica y positiva definida. También definimos la norma de un vector en un espacio con producto interior $\langle \cdot, \cdot \rangle$, que era $$\Vert x \Vert = \sqrt{\langle x, x \rangle}.$$

Finalmente, en la entrada anterior probamos la siguiente versión general de la desigualdad de Cauchy-Schwarz:

Teorema (desigualdad de Cauchy-Schwarz). Sea $b:V\times V\to \mathbb{R}$ una forma bilineal simétrica y $q$ su forma cuadrática asociada.

  • Si $b$ es positiva, entonces para todo $x$ y $y$ en $V$ tenemos que $$b(x,y)^2\leq q(x)q(y).$$ Si $x$ y $y$ son linealmente dependientes, se da la igualdad.
  • Además, si $b$ es positiva definida y $x$ y $y$ son linealmente independientes, entonces la desigualdad es estricta.

Ángulos

Fijemos $V$ un espacio vectorial sobre los reales con producto interior. En la entrada anterior vimos que la desigualdad de Cauchy-Schwarz implica que para cualesquiera vectores $x$ y $y$ en $V$ tenemos que $$|\langle x, y \rangle| \leq \Vert x \Vert \cdot \Vert y \Vert.$$

Si $x$ y $y$ son vectores distintos de cero, podemos reescribir la desigualdad anterior como $$-1\leq \frac{\langle x, y \rangle}{\Vert x \Vert \cdot \Vert y \Vert}\leq 1.$$ Esto justifica la siguiente definición.

Definición. Sean $x$ y $y$ vectores no nulos. Definimos al ángulo entre $x$ y $y$ como el único ángulo $\theta$ en el intervalo $[0,\pi]$ tal que $$\cos \theta = \frac{\langle x, y \rangle}{\Vert x \Vert \cdot \Vert y \Vert}.$$

Observa que $\theta=\frac{\pi}{2}$ si y sólo si $\frac{\langle x, y \rangle}{\Vert x \Vert \cdot \Vert y \Vert}=0$. Esto ocurre si y sólo si $\langle x, y \rangle=0$. Este caso es particularmente importante, y por ello recibe una definición especial.

Definición. Decimos que $x$ y $y$ son ortogonales si $\langle x, y \rangle=0$.

Para empezar, veamos un ejemplo sencillo de ortogonalidad.

Ejemplo 1. Tomemos $\mathbb{R}^5$ con el producto interior canónico, es decir, el producto punto. Los vectores $u=(1,0,-4,0,5)$ y $v=(0,3,0,-2,0)$ tienen producto punto $$\langle u, v \rangle=1\cdot 0 + 0\cdot 3 + (-4)\cdot 0 + 0 \cdot (-2) + 5 \cdot 0=0,$$ así que son ortogonales.

$\triangle$

Ahora, veamos un ejemplo un poco más elaborado, del cálculo de un ángulo en un espacio vectorial de funciones.

Ejemplo 2. Anteriormente vimos que $\mathcal{C}[0,1]$ tiene un producto interior $$\langle f, g \rangle=\int_0^1 f(x)g(x)\, dx.$$ Calculemos el ángulo entre $f(x)=x^2$ y $g(x)=x^3$ con este producto interior. Primero, calculamos $\Vert f \Vert$ y $\Vert g \Vert$ como sigue
\begin{align*}
\Vert f \Vert^2 &= \int_0^1 x^4 \,dx = \frac{1}{5}\\
\Vert g \Vert^2 &= \int_0^1 x^6 \,dx = \frac{1}{7},
\end{align*}

de donde $\Vert f \Vert = \frac{1}{\sqrt{5}}$ y $\Vert g \Vert = \frac{1}{\sqrt{7}}$.

Luego, calculamos
\begin{align*}
\langle f,g \rangle &=\int_0^1 f(x)g(x) \, dx\\
&=\int_0^1 x^5 \, dx\\
&=\frac{1}{6}.
\end{align*}

Como esperaríamos por la desigualdad de Cauchy-Schwarz, tenemos la siguiente desigualdad:
\begin{align*}
\langle f,g \rangle &= \frac{1}{6}\leq \frac{1}{\sqrt{35}}=\Vert f \Vert \Vert g \Vert.
\end{align*}

El ángulo entre $f$ y $g$ es entonces
\begin{align*}
\theta &= \arccos\left(\frac{\langle f, g \rangle}{\Vert f \Vert \cdot \Vert g \Vert}\right)\\
&=\arccos\left(\frac{1/6}{1/\sqrt{35}}\right)\\
&=\arccos\left(\frac{\sqrt{35}}{6}\right).
\end{align*}

$\triangle$

Desigualdad de Minkowski

Hay una forma un poco distinta de escribir la desigualdad de Cauchy-Schwarz. La enunciamos a continuación.

Teorema (desigualdad de Minkowski). Sean $x$ y $y$ vectores de un espacio vectorial $V$ con una forma cuadrática positiva $q$. Entonces $$\sqrt{q(x)}+\sqrt{q(y)}\geq \sqrt{q(x+y)}.$$

Demostración. Sea $b$ la forma polar de $q$. Recordemos que $$q(x+y)=q(x)+2b(x,y)+q(y).$$

Como $q$ es forma cuadrática positiva, la desigualdad que queremos mostrar es equivalente a la siguiente desigualdad obtenida de elevar ambos lados al cuadrado:

\begin{align*}
q(x)+2\sqrt{q(x)q(y)}+q(y)&\geq q(x+y)\\
&=q(x)+2b(x,y)+q(y).
\end{align*}

Cancelando $q(x)+q(y)$ de ambos lados y dividiendo entre $2$, obtenemos la desigualdad equivalente
\begin{align*}
\sqrt{q(x)q(y)}\geq b(x,y).
\end{align*}

Si $b(x,y)<0$, esta desigualdad es claramente cierta. Si $b(x,y)\geq 0$, esta desigualdad es equivalente a la obtenida de elevarla al cuadrado, es decir, $$q(x)q(y)\geq b(x,y)^2,$$ que es precisamente la desigualdad de Cauchy-Schwarz.

$\square$

De producto interior a norma

Estamos listos para mostrar algunas propiedades importantes de la noción de norma que definimos para espacios vectoriales reales con producto interior.

Proposición. Sea $V$ un espacio vectorial sobre $\mathbb{R}$ con producto interior con norma asociada $\Vert \cdot \Vert$. Se cumple que

  1. $\Vert v \Vert \geq 0$ para todo $v$ en $V$, con igualdad si y sólo si $v=0$.
  2. $\Vert cv \Vert =|c|\Vert v \Vert$ para todo $v$ en $V$ y real $c$.
  3. (Desigualdad del triángulo) $\Vert v \Vert + \Vert w \Vert \geq \Vert v+w \Vert$ para todo par de vectores $v$ y $w$ en $V$.

Demostración. Sea $b$ el producto interior de $V$. El punto 1 se sigue de que $b$ es positiva definida. El punto 2 se sigue de que $b$ es bilineal, pues $b(cv,cv)=c^2b(v,v)$, de modo que $$\Vert cv \Vert = \sqrt{c^2} \Vert v \Vert =|c| \Vert v \Vert.$$ El punto 3 es la desigualdad de Minkowski.

$\square$

En general, si tenemos un espacio vectorial $V$ sobre los reales y una función $\Vert \cdot \Vert:V \to \mathbb{R}$ que satisface los puntos 1 a 3 de la proposición anterior, decimos que $\Vert \cdot \Vert$ es una norma para $V$. Hay algunas normas que no se pueden obtener a través de un producto interior.

Ejemplo. Consideremos $V=M_n(\mathbb{R})$. El producto de Frobenius de las matrices $A$ y $B$ está dado por $$\langle A,B\rangle = \text{tr}(^tA B).$$ Se puede mostrar que el producto de Frobenius es un producto interior. La norma de Frobenius es la norma inducida por este producto, es decir, $$\Vert A \Vert = \sqrt{\text{tr}(^tAA)}.$$

Por la desigualdad de Minkowski, tenemos que para cualesquiera dos matrices $A$ y $B$ tenemos que $$\sqrt{\text{tr}(^t(A+B)(A+B))}\leq \sqrt{\text{tr}(^tAA)} + \sqrt{\text{tr}(^tBB)}.$$

En particular, si tomamos a la identidad $I$, tenemos que su norma de Frobenius es $\sqrt{n}$. Esto muestra la siguiente desigualdad, válida para cualquier matriz $A$ en $M_n(\mathbb{R})$:

$$\sqrt{\text{tr}((^tA+I)(A+I))}\leq \sqrt{\text{tr}(^tAA)}+ \sqrt{n}.$$

$\triangle$

De norma a distancia

Podemos pensar a la norma de un vector $v$ como qué tan lejos está del vector $0$. También nos gustaría poder hablar de qué tan lejos están cualesquiera dos vectores de un espacio vectorial con producto interior. Por esta razón, introducimos la siguiente definición.

Definición. Sea $V$ un espacio vectorial sobre $\mathbb{R}$ con producto interior de norma $\Vert \cdot \Vert$. La distancia asociada a este producto interior es la función $d:V\times V\to \mathbb{R}$ tal que $d(x,y)=\Vert x-y\Vert.$ A $d(x,y)$ le llamamos la distancia entre $x$ y $y$.

El siguiente resultado se sigue de las propiedades de la norma de un producto interior. Su demostración queda como tarea moral.

Proposición. Si $V$ es un espacio vectorial sobre $\mathbb{R}$ con producto interior de distancia $d$, entonces:

  1. $d(x,y)\geq 0$ para todos $x$ y $y$ en $V$ y es igual a $0$ si y sólo si $x=y$.
  2. $d(x,y)=d(y,x)$ para todos $x$ y $y$ en $V$.
  3. $d(x,z)+d(z,y)\geq d(x,y)$ para todos $x$, $y$ y $z$ en $V$.

En general, si tenemos cualquier conjunto $X$ (no hace falta que sea un espacio vectorial), a una función $d$ que satisface los puntos 1 a 3 de la proposición anterior se le conoce como una métrica para $X$. Cualquier norma en un espacio vectorial $V$ (no sólo las de producto interior) induce una métrica en $V$. Sin embargo, hay métricas de espacios vectoriales que no vienen de una norma.

Más adelante…

Retomando conceptos ya definidos como la norma de un vector, en esta entrada vimos cómo encontrar el ángulo entre dos vectores no-nulos y se llegó a una forma natural de introducir la ortogonalidad entre dos vectores. Así mismo, se demostraron algunas propiedades de la norma asociada a un producto interior, siendo la última una forma distinta de expresar la desigualdad de Cauchy-Schwarz, usando la desigualdad de Minkowski. Finalmente, se definió el concepto de distancia entre dos vectores.

En entradas posteriores, usaremos estos conceptos para estudiar bases ortogonales, que tienen usos en conceptos matemáticos más avanzados como el análisis de Fourier o la teoría de polinomios ortogonales.

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.

  • Toma $\mathbb{R}^4$ con el producto interior canónico (producto punto). Determina la norma de $(3,4,0,1)$. Encuentra el ángulo entre los vectores $(1,0,2,5)$ y $(4,5,0,-3)$.
  • Muestra que el producto de Frobenius es un producto interior en $M_n(\mathbb{R})$.
  • Demuestra la proposición de propiedades de la distancia

Considera $V=\mathbb{R}_3[x]$ el espacio vectorial de polinomios con coeficientes reales y grado a lo más $3$. Definimos $$\langle p,q \rangle = \sum_{j=1}^5 p(j)q(j).$$

  • Muestra que $\langle \cdot, \cdot \rangle$ así definido es un producto interior.
  • Encuentra el ángulo entre los polinomios $1+x^2$ y $2x-3x^3$.
  • Para cada entero positivo $n$, determina la norma del polinomio $1+nx^3$.
  • Determina la distancia entre los polinomios $1$ y $1+x+x^2+x^3$.

Entradas relacionadas

Agradecimientos

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

Álgebra Superior II: Norma y distancia en los complejos

Por Leonardo Ignacio Martínez Sandoval

3 respuestas

Introducción

Ya definimos a $\mathbb{C}$ y sus operaciones. También definimos y dimos las propiedades de la conjugación compleja. Ahora hablaremos de la norma en los números complejos.

Definición. Dado el número complejo $w=a+bi$, su norma es $\sqrt{a^2+b^2}$. Denotamos a la norma de $w$ por $\Vert w \Vert$.

Ejemplo. La norma del complejo $\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{2}}i$ es $$\sqrt{\left(\frac{1}{\sqrt 2}\right)^2+ \left(\frac{1}{\sqrt 2}\right)^2}=\sqrt{\left(\frac{1}{2}+\frac{1}{2}\right)}=\sqrt{1}=1.$$ La norma del complejo $-3i$ es $$\sqrt{0^2+(-3)^2}=\sqrt{9}=3.$$

$\triangle$

Cuando pensamos a los números complejos como elementos del plano, identificando al complejo $a+bi$ con el punto $(a,b)$, la norma es una forma de medir qué tan alejado está del origen.

A partir de la noción de norma podemos definir la noción de distancia, que dice qué tan lejos están dos complejos entre sí.

Definición. Para dos números complejos $w$ y $z$ definimos la distancia entre $w$ y $z$ como la norma de $w-z$, es decir, $\Vert w-z\Vert$. La denotamos por $d(w, z)$

Propiedades básicas de la norma en los complejos

La norma en los complejos está relacionada con otras operaciones definidas como sigue:

Teorema 1. Sean $w$ y $z$ números complejos. Entonces:

  1. La norma es la raíz del producto de un complejo por su conjugado, es decir, $\Vert z \Vert = \sqrt{z\overline{z}}.$
  2. $\Vert z \Vert$ es un número real no negativo.
  3. $\Vert z \Vert = 0$ si y sólo si $z=0$.
  4. La norma es multiplicativa, es decir, $\Vert zw \Vert = \Vert z \Vert \Vert w \Vert$.

Demostración. Si $z=a+ib$, entonces $\overline{z}=a-ib$, y por lo tanto

\begin{align*}
\sqrt{z\overline{z}}&=\sqrt{a^2-(ib)^2}\\
&=\sqrt{a^2+b^2}\\
&=\Vert z \Vert.
\end{align*}

La norma de $z=a+ib$ es la suma del cuadrado de dos reales. Cada uno de ellos es no negativo, así que esa suma es no negativa. De este modo, al sacar raíz cuadrada obtenemos un número real y no negativo. Para que este número sea cero, necesitamos que $a^2=b^2=0$, es decir, que $a=b=0$, lo cual sucede justo cuando $z=0$.

Para mostrar la última propiedad, se pueden tomar dos números complejos explícitos y hacer las cuentas. Sin embargo, también podemos probarla usando la primer propiedad y la conmutatividad del producto, de números complejos, como sigue:

$$\Vert zw \Vert ^2= zw\overline{zw} = z\overline{z} w\overline{w}= \Vert z \Vert^2 \Vert w \Vert ^2.$$

Sacando raíz cuadrada de ambos lados obtenemos el resultado deseado.

$\square$

Ejercicios que usan las propiedades básicas

Veamos algunas formas en las que podemos usar las propiedades anteriores, de la norma, en los complejos.

Ejercicio 1. Muestra que $z$ y $\overline{z}$ tienen la misma norma.

Solución. Usando que $\overline{\overline{z}}=z$, la propiedad 1 del Teorema 1 y la conmutatividad del producto en $\mathbb{C}$ tenemos que $$\Vert \overline{z}\Vert = \sqrt{\overline{z}z}=\sqrt{z\overline{z}} = \Vert z \Vert.$$

$\triangle$

El siguiente es un corolario de la propiedad 4 del Teorema 1, que se puede mostrar usando inducción. La prueba de este corolario se deja como tarea moral.

Corolario. Para $z$ un complejo y $n$ un natural, se tiene que $$\Vert z^n \Vert = \Vert z \Vert ^n.$$

Ejercicio 2. Determina la norma del complejo $$\left(3+4i\right)^{20}.$$

Solución. Tomemos $u=3+4i$. El problema nos pide determinar $\Vert u^{20} \Vert$. Una forma de hacerlo es realizar primero la operación $u^{20}$, pero esto parece ser complicado. En vez de eso, usamos el Corolario anterior. Para ello, notamos que $$\Vert u \Vert = \sqrt{3^2+4^2}= \sqrt{25}=5.$$

De este forma, por el corolario, la norma que buscamos es $$\Vert u^{20} \Vert = \Vert u \Vert ^{20}= 5^{20}.$$

$\triangle$

Ejercicio 3. Sea $z$ un número complejo. Muestra que los siguientes números complejos tienen la misma norma: $$z, -z, iz, -iz.$$

Solución. Se sigue de la propiedad $4$ del Teorema 1 y de que $$\Vert -1 \Vert = \Vert i \Vert = \Vert -i \Vert = 1.$$

$\square$

Ejercicio 4. Muestra que para un número real, $r$, su norma compleja coincide con su valor absoluto.

Solución. Usando la propiedad 1 del Teorema 1 y que $\overline{r}=r$, tenemos que $$\Vert r \Vert = \sqrt{\overline{r}r}=\sqrt{r^2}=|r|.$$

$\square$

La desigualdad del triángulo

¿Cómo se comporta la norma con la suma de los complejos? Lo responderemos en esta sección. Pero antes, de pasar al teorema 2 que contiene la respuesta, veamos un pequeño resultado auxiliar.

Lema. Si $z$ es un número complejo, entonces $|\text{Re}(z)| \leq \Vert z \Vert$ y $|\text{Im}(z)|\leq \Vert z \Vert$. La primer igualdad se da si y sólo si $z$ es un número real y la segunda si y sólo si $z$ es un número imaginario puro, es decir, si su parte real es $0$.

Demostración. Tomemos $z=a+ib$. Tenemos que $a^2\leq a^2+b^2$, de modo que sacando raíces cuadradas tenemos que $$|\text{Re}(z)| = |a| = \sqrt{a^2}\leq \sqrt{a^2+b^2}=\Vert z \Vert.$$ La igualdad se da si y sólo si $b=0$, lo cual sucede si y sólo si $z$ es real.

$\square$

La demostración de la segunda parte es análoga, y queda como tarea moral.

Teorema 2 (desigualdad del triángulo). Para dos números complejos $w$ y $z$ se tiene que $$\Vert w+z \Vert \leq \Vert w \Vert + \Vert z \Vert.$$ La igualdad se da si y sólo si $w$ es un múltiplo real de $z$, es decir, si y sólo si existe un real $r$ tal que $w=rz$.

Demostración. Tenemos que:
\begin{align*}
\Vert w+z \Vert^2 &= (w+z)\overline{(w+z)}\\
&=(w\overline{w}+w\overline{z}+\overline{w}z+z\overline{z})\\
&=\Vert w \Vert^2 + 2\text{Re}(w\overline{z}) + \Vert z \Vert^2.
\end{align*}

Podemos continuar usando la desigualdad del Lema anterior (notemos que se obtiene la igualdad si y sólo si $w\overline{z}$ es real)

\begin{align*}
&\leq \Vert w \Vert^2 + 2\Vert w\overline{z}\Vert + \Vert z \Vert^2\\
&=\Vert w \Vert ^2 + 2 \Vert w \Vert \Vert z \Vert + \vert z \Vert^2\\
&=\left(\Vert w \Vert + \Vert z \Vert \right)^2.
\end{align*}

Esta cadena de desigualdades se resume a $$ \Vert w+z \Vert^2 \leq \left(\Vert w \Vert + \Vert z \Vert \right)^2, $$ de donde sacando raíz cuadrada en ambos lados, obtenemos lo deseado.

Como observamos durante la demostración, la igualdad se da si y sólo si $w\overline{z}$ es un número real, es decir, si y sólo si existe un real $s$ tal que $w\overline{z}=s$. Multiplicando por $z$ de ambos lados, obtenemos que $$w\Vert z \Vert^2 = sz.$$ Si $z=0$, entonces $w=0$ y por lo tanto $w$ es trivialmente un múltiplo real de $z$. Si $z\neq 0$, entonces $w=\frac{s}{\Vert z \Vert ^2}\cdot z$ también es un múltiplo real de $z$, con $r=\frac{s}{\Vert z \Vert ^2}$. Esto termina el análisis, de los casos, de la igualdad.

$\square$

Propiedades de la distancia

En la introducción definimos la distancia entre dos números complejos $w$ y $z$ como la norma de $w-z$, en símbolos, $d(w,z)=\Vert w-z \Vert$. Para formalizar ideas veamos la siguiente definición.

Definición. Sea $X$ un conjunto y $e: X\times X\rightarrow \mathbb{R}^{+}\cup \lbrace 0\rbrace$ una función, $e$ es una métrica en $X$ si, para todo $x$, $y$ y $z\in X$, satisface que:

  1. $e(x, y)\geq 0$.
  2. $e(x, y)=0$ si, y sólo si, $x=y$.
  3. $e(x, y)=e(y, x)$.
  4. $e(x, y)\leq e(x, z) + e(y, z)$.

Observa que a partir de los teoremas 1 y 2, la distancia $d$ cumple las propiedades de esta definición, por lo que decimos que $d$ es una métrica en $\mathbb{C}$. Así tenemos el siguiente teorema.

Teorema 3. Sean $w$ y $z$ dos números complejos cualesquiera y $d(w, z)=\vert\vert w- z\vert\vert$. Entonces $d$ es una métrica en $\mathbb{C}$.

Demostrar este teorema es sencillo a partir de lo que ya vimos, así que su demostración queda como tarea moral.

Más adelante…

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. Muestra la propiedad 4 del Teorema 1 usando de manera explícita las partes reales e imaginarias de los complejos $z$ y $w$.
  2. Demuestra el corolario de normas de potencias de complejos.
  3. Determina la norma del complejo $(12-5i)^{10}$.
  4. Determina la norma del complejo $(1+2i)(-3+4i)(5-6i)(-7-8i)$.
  5. Demuestra la segunda parte del Lema.
  6. Demuestra el Teorema 3.
  7. Sean $w=(3+4i)(5-i)$ y $z=(5-i)(4+2i)$. Determina $d(w,z)$.

Entradas relacionadas

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: Principio de inducción combinado con heurísticas

Por Leonardo Ignacio Martínez Sandoval

3 respuestas

Introducción

En esta entrada continuaremos con ejemplos de uso del principio de inducción en la resolución de problemas. Es una continuación de la entrada anterior. Como recordatorio, aquí está el principio de inducción en la forma en la que lo hemos estado usando:

Principio de inducción. Sea $P(n)$ una afirmación (o proposición o propiedad) que depende del número natural $n$. Si

  • la afirmación $P(a)$ es cierta y
  • la veracidad de la afirmación $P(n)$ implica la veracidad de la afirmación $P(n+1)$,

entonces la afirmación $P(n)$ es cierta para toda $n \geq a$.

Lo que nos interesa ahora es ver cómo el principio de inducción se mezcla con algunas de las heurísticas de resolución de problemas.

Inducción y trabajar hacia atrás

Lo que hemos hecho hasta ahora es lo siguiente. Tomamos un enunciado que depende de un entero $n$. Comenzamos probándolo para la base inductiva. Luego, suponemos la veracidad del enunciado para cierto entero $n$. A partir de ahí, intentamos conseguir la veracidad del enunciado para el entero $n+1$.

Como vimos cuando platicamos de trabajar hacia atrás, eso no siempre es lo más natural en la resolución de un problema. En algunas ocasiones nos conviene más empezar con el enunciado que queremos demostrar y mostrar que mediante pasos reversibles podemos llegar a algo cierto. Queremos aplicar esta idea para la demostración del paso inductivo.

Consideremos el siguiente ejemplo.

Problema. Demuestra que para todo entero no negativo $n$ se tiene que $$\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30}$$ es un número entero.

Solución. Tenemos que probar la afirmación para $n\geq 0$ entero. Procedemos por inducción sobre $n$. Si $n=0$, la expresión es igual a $0$, así que la afirmación es cierta. Supongamos entonces que
$$\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30}$$ es entero y consideremos la expresión
$$\frac{(n+1)^5}{5}+\frac{(n+1)^4}{2}+\frac{(n+1)^3}{3}-\frac{(n+1)}{30}.$$

Nuestro objetivo es mostrar que esta expresión es entera. Nos gustaría usar la hipótesis inductiva, así que queremos intentar encontrar dentro de esta expresión la expresión para $n$. Esto lo podemos hacer usando el binomio de Newton para abrir los binomios a potencias y luego agrupando. Tenemos que

\begin{align*}
\frac{(n+1)^5}{5}&=\frac{n^5+5n^4+10n^3+10n^2+5n+1}{5}\\
&=\frac{n^5}{5}+n^4+2n^3+2n^2+n+\frac{1}{5}\\
\frac{(n+1)^4}{2}&=\frac{n^4+4n^3+6n^2+4n+1}{2}\\
&=\frac{n^4}{4}+2n^3+3n^2+2n+\frac{1}{2}\\
\frac{(n+1)^3}{3}&=\frac{n^3+3n^2+3n+1}{3}\\&
=\frac{n^3}{3}+n^2+n+\frac{1}{3}\\
-\frac{n+1}{30}&=-\frac{n}{30}-\frac{1}{30}.
\end{align*}

Así, cuando hagamos la suma tenemos los términos
$$\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30},$$ cuya suma es entera por hipótesis inductiva, $$n^4+2n^3+2n^2+n+2n^3+3n^2+2n+n^2+n,$$ que es entero pues $n$ es entero y $\frac{1}{5}+\frac{1}{2}+\frac{1}{3}-\frac{1}{30}=1$, de modo que la suma total es suma de enteros y por lo tanto es un entero. Esto termina la prueba por inducción.

$\square$

Si no comenzábamos a manipular la expresión para $n+1$, hubiera sido muy difícil, sólo a partir de la de $n$, llegar a la de $n+1$.

Inducción y generalización

Una forma sencilla de combinar inducción con generalización es la siguiente:

  • Nos piden demostrar una afirmación para un natural muy específico.
  • En vez de eso, construimos un problema más general que funcione «para todos los naturales».
  • Resolvermos ese problema por inducción.

Veamos un ejemplo.

Problema. Muestra que $$\left(\frac{3+\sqrt{17}}{2}\right)^{2020}+
\left(\frac{3-\sqrt{17}}{2}\right)^{2020}$$ es un entero impar.

Solución. Sean $\alpha=\frac{3+\sqrt{17}}{2}$ y $\beta=\frac{3-\sqrt{17}}{2}$. Se pide mostrar que $\alpha^{2020}+\beta^{2020}$ es un entero impar. Mostraremos que, de hecho, $\alpha^n+\beta^n$ es un entero impar para todo entero $n\geq 1$. Vamos a proceder por inducción fuerte (hablaremos un poco más de eso más adelante).

El primer caso es $n=1$ y notemos que $\alpha^1+\beta^1=\alpha+\beta=3.$ Notemos también que $\alpha\beta=\frac{9-17}{4}=-2$, de modo que $\alpha^2+\beta^2=(\alpha+\beta)^2-2ab=9+4=13$, que también es impar. Supongamos ahora que sabemos que la afirmación es cierta para exponentes $n-1$ y $n$.

Consideremos el polinomio cuadrático $$(x-\alpha)(x-\beta)=x^2-(\alpha+\beta)x+\alpha\beta=x^2-3x-2.$$ Como $\alpha$ y $\beta$ son raíces, tenemos que $\alpha^2-3\alpha-2=0$ y $\beta^2-3\beta -2=0$. Multiplicando estas igualdades por $\alpha^{n-1}$ y $\beta^{n-1}$ respectivamente, sumando ambas igualdades obtenidas, y despejando $\alpha^{n+1}+\beta^{n+1}$ llegamos a $$\alpha^{n+1}+\beta^{n+1}=3(\alpha^n+\beta^n)+2(\alpha^{n-1}+\beta^{n-1}).$$

De aquí la conclusión inductiva es inmediata. Como la hipótesis inductiva es que el resultado es cierto para los exponentes $n$ y $n-1$, entonces en el lado derecho tenemos una suma de un entero impar con un entero par, que es un entero impar. Esto muestra que la afirmación es cierta para cuando los exponentes son $n+1$.

Para demostrar el problema original, basta con hacer la observación de que, en particular, $\alpha^{2020}+\beta^{2020}$ es un entero impar.

$\square$

Hay otra forma de combinar inducción con generalización, pero es un poco más sofisticada. Para explicarla, es mejor comenzar con un ejemplo.

Problema. Demuestra que para todo entero $n\geq 1$ se tiene que $$\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+\ldots + \frac{1}{n(n+1)} <1.$$

Antes de resolver el problema, intentemos hacer una solución «ingenua» que quiera usar inducción de manera directa. No hay ningún problema con hacer la base de inducción, pues para $n=1$ al lado izquierdo tenemos únicamente $\frac{1}{2}$ y al lado derecho $1$. Supongamos que el resultado es cierto para $n$, es decir, que $$\frac{1}{1\cdot 2}+\ldots + \frac{1}{n(n+1)} <1.$$

Llamémosle $M$ a la expresión del lado izquierdo. Lo que queremos probar ahora es que el resultado es cierto para $n+1$, es decir, que $M+\frac{1}{(n+1)(n+2)}<1$. Sabemos que $M<1$, pero ahora estamos sumando un término positivo adicional. Es posible que este término arruine la desigualdad, pues $M<1$ es una afirmación «muy débil». Veamos cómo darle la vuelta a esta dificultad.

Solución. Sea $P(n)$ la afirmación del problema. Consideremos la afirmación $Q(n)$ que dice que para todo entero $n\geq 1$ se tiene que
$$\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\ldots + \frac{1}{n(n+1)} =1-\frac{1}{n+1}.$$

Si logramos demostrar $Q(n)$, entonces $P(n)$ será cierta de manera inmediata, pues $1-\frac{1}{n+1}<1$. Vamos a demostrar $Q(n)$ por inducción.

Tenemos que $Q(1)$ es cierto pues en ambos lados de la igualdad queda $\frac{1}{2}$. Supongamos que $Q(n)$ es cierto. Usando esto, tenemos que
\begin{align*}
\frac{1}{1\cdot 2}+\ldots+\frac{1}{n(n+1)} + \frac{1}{(n+1)(n+2)} &=\left(1-\frac{1}{n+1}\right)+\frac{1}{(n+1)(n+2)}\\
&=1-\frac{(n+2)-1}{(n+1)(n+2)}\\
&=1-\frac{1}{n+2},
\end{align*}

es decir, que $Q(n+1)$ es cierto. Así, por inducción $Q(n)$ es cierto para todo entero $n$ y con eso $P(n)$ también.

$\square$

Lo que sucedió fue lo siguiente. Al hacer el paso inductivo, intentamos mostrar que $P(n)$ implica $P(n+1)$. Pero esto es imposible pues $P(n)$ «es muy débil», o bien «pierde información de todo lo que está pasando». Sin embargo, cuando consideramos la afirmación auxiliar $Q(n)$, resulta que esta «tiene más información». Aquí, esta información es «qué tal lejos está la expresión de $1$ «

La afirmación $Q(n)$ tiene tanta información, que ahora sí con ella se puede probar $Q(n+1)$. Se termina el problema usando que $Q(n)$ implica $P(n)$. Así, la estrategia fue la siguiente:

  • Se tiene una afirmación $P(n)$ que se quiere demostrar para todos los naturales. Hacer inducción no parece funcionar, pues $P(n)$ parece no ser suficiente para probar $P(n+1)$
  • Se considera entonces una afirmación $Q(n)$ más fuerte (que implique a $P(n)$), pero para la cual $Q(n)$ sí pueda probar $Q(n+1)$.
  • Se prueba $Q(n)$ por inducción, y se concluye que $P(n)$ es cierta.

Hay que ser cuidadosos. Parte del ingenio en usar esta estrategia consiste en poder identificar un balance en la generalización $Q(n)$ que necesitamos de modo que sí sirva para solucionar el problema original, pero que no sea demasiado ambiciosa como para que sea falsa.

Más ejemplos

Hay más ejemplos bastante elaborados del uso de estas ideas en Problem Solving Through Problems de Loren Larson, Secciones 2.1, 2.2, 2.3 y 2.4. Otro libro con muchos ejemplos interesantes es el Putnam and Beyond, de Gelca y Andreescu. También hay otros ejemplos de inducción en las siguientes entradas:

Un problema de probabilidad y escuchar música

Por Leonardo Ignacio Martínez Sandoval

4 respuestas

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 $[n-2\sqrt{n}, 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 $j\leq k < 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 $2n-1$.

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 $\{2n-k+1, 2n-k+2,\ldots,2n\}$ con la misma probabilidad, y respectivamente nos tomará $\{k-1, k-2,\ldots, 0\}$ pasos en llegar a $2n$, es decir, la cantidad de pasos que hacemos es una variable aleatoria uniforme discreta de media $(k-1)/2$.

Así, en total usamos $(2n/k) + (k-1)/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 $$\frac{2n}{k}+\frac{k-1}{2}=\frac{2n}{k}+\frac{k}{2}-\frac{1}{2} \geq 2\sqrt{n} – \frac{1}{2},$$ y que la igualdad se da si y sólo si $\frac{2n}{k}=\frac{k}{2}$, es decir, si y sólo si $k=2\sqrt{n}$. En este caso, la cantidad media de pasos que usamos es $2\sqrt{n}-\frac{1}{2}$.

Aquí arriba hicimos un poquito de trampa. En realidad $k=2\sqrt{n}$ tiene sentido para la estrategia sólo cuando $\sqrt{n}$ es un número entero. Sin embargo, por la convexidad de la función $
\frac{2n}{k}+\frac{k}{2}$ tenemos la garantía de que o bien $\lfloor
2\sqrt{n} \rfloor$ o bien $\lceil 2\sqrt{n} \rceil$ 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 $2\sqrt{n}$. 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: