Archivo de la etiqueta: heurísticas

Seminario de Resolución de Problemas: Bases numéricas y dígitos

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

Introducción

En las entradas anteriores de teoría de números hemos hablado acerca de divisibilidad, de aritmética modular y de factorización única en primos. En esta entrada vamos a hablar de propiedades que podemos deducir de ciertos números a partir de su dígitos.

Usualmente escribimos a los números en base $10$, usando los dígitos de $1$ a $9$. En realidad, esto es relativamente arbitrario. Podemos usar bases distintas de $10$ para expresar cualquier número de manera (casi) única. Conocer la expresión de un número en cierta base nos permite deducir propiedades algebraicas y de divisibilidad que nos ayuden a resolver problemas.

Expresión en una base arbitraria

Para cualquier base entera $b\geq 2$ que elijamos, cualquier número real se puede expresar de manera (casi) única en base $b$. La afirmación precisa es el siguiente resultado.

Teorema. Sea $r$ un número real y $b\geq 2$ un entero. Entonces, existen únicos enteros $A_0,A_1,\ldots, a_1,a_2,\ldots$ en $\{0,1,\ldots,b-1\}$ tales que $$r=\sum_{i=0}^\infty A_i b^i + \sum_{i=0}^{\infty} a_i 10^{-i}$$ y $a_i\neq b-1$ para una infinidad de $i$’s.

Para estos $a_i$ y $A_i$ escribimos $$r=(\ldots A_2A_1A_0.a_1a_2\ldots)_b,$$ en donde el subíndice indica la base que se está usando.

La condición de $a_i\neq b-1$ para una infinidad de $i’s$ está ahí para garantizar que la expresión sea única pues, por ejemplo, $1=\sum_{i=0}^\infty 9\cdot 10^{-i}=0.9999\ldots$, pero esa condición descarta la expresión de la derecha.

Si $b=2$, a esta expresión le llamamos la expresión binaria de $r$.

Ejemplo. La expresión binaria de $4/3$ es $(1.010101\ldots)_2$. ¿Por qué?

Multiplicar y dividir entre $10$ cuando tenemos números en base $10$ es sencillo: simplemente recorremos el punto decimal. Lo mismo sucede en cualquier base $b$.

Proposición. Cuando tenemos un número en base $b$ y multiplicamos por $b$, el «punto decimal» se recorre a la derecha. Cuando dividimos entre $b$ se recorre a la izquierda.

Problema. Determina si existe un real $x$ tal que $$\floor{x}+\floor{2x}+\floor{4x}+\floor{8x}= 2222.$$

Sugerencia pre-solución. Trabaja hacia atrás suponiendo que la ecuación sí tiene una solución para determinar cómo tiene que verse $x$. Usa la expresión binaria de $x$.

Solución. Tenemos que $r\geq \floor{r}$ para todo real $r$, de modo que si dicho número $x$ existe, se cumple $$17x\geq \floor{x}+\floor{2x}+\floor{4x}+\floor{8x} = 2222.$$ De aquí, $x\geq 2222/17 = 130.705\ldots\geq 130$. También, $r\leq \floor{r}+1$, de modo que si $x$ existe necesitamos $$17x\leq \floor{x}+\floor{2x}+\floor{4x}+\floor{8x} + 4 = 2226.$$

De aquí, $x\leq 2226/17 =130.94\leq 131$.

Esto nos dice que $x$ es un real entre $130$ y $131$. Escribámoslo como $130$ más una parte fraccional en base $2$, es decir, de la forma $x=130+(abcde\ldots)_2$. Multiplicar por $2$ simplemente recorre el punto decimal en base $2$ un lugar hacia la derecha, de modo que
\begin{align*}
2x&=260+(a.bcde\ldots)_2\\
4x&=520+(ab.cde\ldots)_2\\
8x&=1040+(abc.de\ldots)_2,
\end{align*} y por lo tanto
\begin{align*}
\floor{x}&=130\\
\floor{2x}&=260+(a)_2=260+a\\
\floor{4x}&=520+(ab)_2=520+2a+b\\
\floor{8x}&=1040+(abc)_2=1040+4a+2b+c.
\end{align*}

Concluimos entonces que la suma buscada es igual a $1950+7a+3b+c$. Si existe el número que queremos, la ecuación $$1950+7a+3b+c=2222$$ debe tener una solución con $a$, $b$ y $c$ iguales a $0$ o a $1$. Pero esto es imposible, pues incluso aunque los tres sean iguales a $1$, tenemos a lo más $1950+11=1961$. De esta forma, no existe la $x$ que buscamos.

$\square$

Bases y números racionales

Una sucesión infinita $\{a_1,a_2,\ldots,\}$ es preperiódica si existen enteros positivos $n$ y $d$ tales que $a_m=a_{m+d}$ para todo entero $m\geq n$. A $d$ se le llama un periodo de la sucesión, y decimos que $\{a_1,a_2,\ldots\}$ es periódica a partir de $a_n$.

Teorema. Sea $r$ un número real. Las siguientes tres afirmaciones son equivalentes:

  • $r$ es racional.
  • Para toda base $b$ la sucesión de dígitos después del punto $\{a_1,a_2,\ldots\}$ es preperiódica.
  • Para alguna base $b$ la sucesión de dígitos después del punto $\{a_1,a_2,\ldots\}$ es preperiódica.

Problema. Considera el número en binario $$r=(0.a_1a_2a_3\ldots)_2$$ en donde $a_i=0$ si $i$ es primo y $a_i=1$ si no. Determina si $r$ es un número racional o irracional.

Sugerencia pre-solución. Procede por contradicción, suponiendo que $r$ es racional.

Solución. Si $r$ fuera racional, la sucesión $\{a_1,a_2,\ldots\}$ sería preperiódica, de modo que existirían $n$ y $d$ tales que $a_{m+d}=a_m$ para todo $m\geq n$. Consideremos el bloque de $d$ dígitos $(a_na_{n+1}\ldots a_{n+d-1})_2$. Como el periodo de la sucesión es $d$, a partir de $a_n$ este bloque de dígitos se repite.

Los números

\begin{align*}
M&=n(2d+1)!+2,\\
M+1&=n(2d+1)!+3,\\
&\vdots\\
M+(2d-1)&=n(2d+1)!+(2d+1)
\end{align*}

son $2d$ números consecutivos mayores a $n$ y tales que ninguno de ellos es primo, pues el primero es divisible entre $2$, el segundo entre $3$, …, y el último entre $2d+1$. Esto muestra que el bloque de $d$ dígitos debe consistir de puros $1$’s, pues uno de los bloques del ciclo queda contenido en el bloque de $2d$ dígitos $(a_Ma_{M+1}\ldots a_{M+2d-1})_2$. Así, a partir de $a_n$ todos los dígitos son iguales a $1$.

Pero esto es imposible, pues quiere decir que todos los enteros mayores o iguales a $n$ no son primos. Esto contradice que hay una infinidad de números primos.

$\square$

Criterios de divisibilidad

Si sabemos cómo es la expresión de un número en una base, entonces a veces podemos decir cosas acerca de su divisibilidad o residuo al dividirse entre algunos enteros relacionados con la base. Cuando estamos trabajando módulo $10$ tenemos el siguiente resultado.

Proposición (criterios de divisibilidad base 10). Sea $n$ un entero positivo. En base $10$,

  • $n$ es congruente con el número formado por sus últimos $k$ dígitos módulo $10^k$, y por lo tanto también módulo $2^k$ y módulo $5^k$.
  • $n$ es congruente con la suma de sus dígitos módulo $9$, y por lo tanto también módulo $3$.
  • Agrupemos los dígitos de $n$ de derecha a izquierda en grupos de $j$ elementos, donde el último puede tener menos de $j$. Un número es congruente con la suma alternada (más, menos, más, etc) de estos grupos módulo $10^{j}+1$.

Demostrar estos criterios es sencillo. Por ejemplo, un número $(A_nA_{n-1}\ldots A_0)_{10}$ en base $10$ es igual a $$10^{n}A_n+10^{n-1}A_{n-1}+\ldots+10 A_1+ A_0.$$ Trabajando módulo $9$, todos los $10$ son $1$, así que $$n=10^nA_n+\ldots+A_0\equiv A_n + A_{n-1}+\ldots+A_0.$$

Como ejemplo del último criterio, considera el siguiente problema:

Problema. ¿Cuál es el residuo que queda al dividir $n=1512513514515$ entre $13$?

Sugerencia pre-solución. Usa el tercer criterio de divisibilidad base $10$ para $j=3$. Factoriza $1001$.

Solución. Vamos a estudiar al número módulo $1001$. Para esto, agrupamos los dígitos de tres en tres, de derecha a izquierda $$515, 514, 513, 512, 1$$ y hacemos la suma alternada $$515-514+513-512+1=3.$$ Por el tercer criterio de divisibilidad, tenemos que $n\equiv 3 \pmod{1001}$. Notemos que $1001=7\cdot 11 \cdot 13$, de modo que $n\equiv 3 \pmod{13}$. Así, el residuo al dividir $n$ entre $13$ es $3$.

$\square$

En general, tenemos lo siguiente.

Proposición (criterios de divisibilidad base $b$). Sea $n$ un entero positivo. En base $b$:

  • $n$ es congruente con el número formado por sus últimos $k$ dígitos módulo $b^k$, y por lo tanto también módulo $d^k$ para cualquier divisor $d$ de $b$.
  • $n$ es congruente con la suma de sus dígitos módulo $b-1$ (y por lo tanto también módulo cualquier divisor de $b-1$)
  • Agrupemos los dígitos de $n$ de derecha a izquierda en grupos de $j$ elementos, donde el último puede tener menos de $j$. Un número es congruente con la suma alternada (más, menos, más, etc) de estos grupos módulo $b^{j}+1$.

Problema. Considera los números del $1$ al $500$ (inclusive). ¿Cuántos de estos números tienen una cantidad impar de $1$’s en su expresión en base $3$? ¿Cuántos de estos números tienen una cantidad impar de $1$’s en su expresión en binario?

Sugerencia pre-solución. Haz casos pequeños para encontrar un patrón que te diga cuántos números del $1$ al $n$ tienen una cantidad impar de $1$’s en su expresión en base $2$ y $3$. Para demostrar el resultado para base $3$, usa criterios de divisibilidad generalizados. Para base $2$ usa paridad y aprovecha la simetría.

Solución. Un número en base $3$ es congruente con la suma de sus dígitos módulo $2$. En base $3$ el único dígito impar es el $1$. Así, un número en base $3$ es congruente a su cantidad de dígitos $1$ módulo $2$. De esta forma, $n$ tiene una cantidad impar de $1$’s si y sólo si es impar. Por lo tanto, hay $250$ números entre $1$ y $500$ que tienen una cantidad impar de $1$’s en su expresión en base $3$.

En base $1$ el patrón no es tan claro. Los primeros números son $1$, $10$, $11$, $100$, $101$, $110$, $111$. A veces cuando se cambia de cantidad de dígitos se cambia la paridad de $1$’s (como de $11$ a $100$) y a veces no (como de $111$ a $1000$). Haremos entonces un argumento de emparejamiento.

Notemos que cualquier número par $2n$ termina en $0$ en binario y que $2n+1$ tiene la misma expansión salvo el último dígito, que ahora es $1$.Así, a los números del $2$ al $499$ los podemos agrupar en parejas en donde en cada pareja los números tienen distinta paridad de $1$’s. De esta forma, aquí hay $498/2=249$ números con una cantidad impar de $1$’s. El $1$ tiene una cantidad impar de $1$’s. El $500$ en binario es $(111110100)_2$, que tiene una cantidad par de $1$’s. Así, hay $250$ números entre $1$ y $500$ con una cantidad impar de $1$’s en binario.

$\square$

Más ejemplos

Puedes ver más ejemplos del uso de esta teoría en la Sección 3.4 del libro Problem Solving through Problems de Loren Larson.

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:

Seminario de Resolución de Problemas: Principio de las Casillas

Por Fabian Ferrari

Deja un comentario

Introducción

Imaginemos que tenemos un botiquín con $9$ espacios para acomodar medicamentos. Si contamos con un total de $10$ medicamentos para acomodar en los $9$ espacios, es claro pensar que al menos uno de los $9$ espacios tendrá al menos $2$ medicamentos. Eso lo podemos deducir a partir de que no hay posibilidad de repartir los $10$ medicamentos de manera equitativa en los $9$ espacios, ya que tenemos más objetos que acomodar que lugares en donde distribuir.

Siguiendo el ejemplo anterior, podemos generalizar un poco. Si tuviésemos $n$ lugares en el botiquín y $n+1$ medicamentos, podemos concluir lo mismo: al menos en una casilla habría más de un medicamento.

El esquema propuesto anteriormente es un versión básica del principio de casillas. Si volvemos a nuestro problema inicial, con el botiquín con $9$ lugares disponibles, pero ahora tenemos un total de $19$ medicamentos, de igual manera, no podemos distribuir los medicamentos de manera equitativa en los nueve lugares, y ahora si lo pensamos con un poco más de detalle, podemos concluir que en alguna de las $9$ casillas deberían de haber al menos $3$ medicamentos. Esto surge en consecuencia de pensar que podemos distribuir de manera equitativa los $19$ medicamentos en los $9$ lugares, sin embargo si colocamos en cada lugar un total de $2$ medicamentos, tendríamos que hemos acomodado un total de $18$ ($9\times 2$) medicamentos, quedándonos $1$ medicamento por acomodar, el cual debería de ir en alguno de los lugares con $2$ medicamentos cada uno. Con esto concluimos que en alguno de los lugares del botiquín debe de haber al menos $3$ medicamentos.

Con lo anterior, enunciaremos el principio de casillas.

Principio de Casillas: Si se distribuyen al menos $nk+1$ elementos en $n$ lugares, se tiene que uno de esos lugares tiene al menos $k+1$ elementos.

Este principio puede ser de gran utilidad para la resolución de problemas en los cuales hay que exhibir la existencia de elementos que cumplen cierta propiedad.

Problemas

A continuación veremos ciertos problemas en los que se muestra que el principio de las casillas es una herramienta poderosa para su resolución.

Problema. Demuestre que si hay $n$ personas en una fiesta, entonces dos de ellos conocen la misma cantidad de personas (entre los presentes).

Solución. Supongamos que hay una persona $P$ que no conoce a ninguna de las $n-1$ personas restantes. Cada una de las personas en la fiesta conoce a un número de personas entre un rango de $0$ a $n-2$ (nadie puede conocer a los $n-1$ restantes pues nadie puede conocer a $P$). Ahora, aplicando el principio de casillas, relacionando a cada persona su número de conocidos, el cual varía de $0$ a $n-2$, tenemos que al menos dos personas deben de conocer el mismo número de personas.

De igual manera, si suponemos que toda persona conoce a alguien, tenemos que el número de conocidos de cada persona varía de $1$ a $n-1$. Aplicando de nueva cuenta el principio de casillas, al asociar a cada persona su número de conocidos, tenemos que al menos dos se repiten.

$\square$

Problema 2. Dado un conjunto de $n+1$ enteros positivos, todos ellos menores o iguales a $2n$, muestra que al menos un miembro del conjunto debe dividir a otro miembro del conjunto.

Solución. Sean $a_1, a_2, …, a_{n+1}$ dichos enteros positivos. Al factorizar la máxima potencia de dos que divide a cada uno de ellos, podemos escribir a cada número de la forma $a_i=2^{m_i}·b_i$ de tal forma que $b_i$ es un número impar mayor o igual que uno y $m_i$ es un entero no negativo. Consideramos a $B$ como el conjunto de todos los $b_i$´s $$B=\lbrace b_1, b_2, …, b_{n+1}\rbrace.$$

Tenemos que entre $1$ y $2n$ hay un total de $n$ números impares, así que en el conjunto $B$ debe de haber dos elementos que sean iguales entre sí. Supongamos que $b_i$ y $b_j$ son dichos elementos. Con ello, si $m_i\leq m_j$ entonces $a_i$ divide a $a_j$. Y si $m_i>m_j$ entonces $a_j$ divide a $a_i$.

$\square$

Problema 3. Dados los puntos A, B, C, D, E al interior de un cuadrado unitario, demuestra que al menos hay dos puntos cuya distancia es menor a $\frac{\sqrt{2}}{2}$.

Solución. Si dividimos el cuadrado en $4$ cuadrados iguales, tenemos que por el principio de casillas en al menos uno de los cuadrados debe de haber $2$ puntos. Sin perdida de generalidad, supongamos que  A y B son dichos puntos que quedan la interior de uno de estos cuadrados pequeños. Tenemos que le diagonal del cuadrado pequeño es $\frac{\sqrt{2}}{2}$, es por ello que cualesquiera dos puntos al interior del cuadrado pequeño estarán distanciados menos que $\frac{\sqrt{2}}{2}$.

$\square$

Problema 4. Prueba que una línea recta que no pasa por uno de los vértices de un triángulo, no puede cortar los tres lados del triángulo.

Solución. Tenemos que una recta divide al plano en dos regiones. Si tomamos estas regiones como «casillas» tenemos que en una de nuestras casillas hay al menos dos puntos del triángulo los cuales forman un segmento de recta que es uno de los lados del triángulo. Con esto tenemos que la recta no corta ese lado del triángulo.

$\square$

Puedes dejar dudas de la entrada o soluciones alternativas a algunos de estos problemas aquí abajo en los comentarios.

Más ejemplos

Puedes encontrar más ejemplos en la Sección 2.6 del Larson, o en la siguiente entrada que escribiremos al respecto.

Usa la paridad

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

HeuristicasLos números enteros pueden ser pares o impares, dependiendo de si son divisibles entre dos o no. Más aún, se van alternando uno y uno. Además, es muy sencillo saber cómo es la paridad de la suma de dos números o bien de su producto si sabes la paridad de esos números. Estas ideas pueden parecer muy básicas, pero ayudan en una gran cantidad de problemas y son una introducción a los invariantes.

Cuando en un problema observamos nada más la paridad, estamos cubriendo una gran cantidad de casos nada más analizando pocos. En estos videos vemos cómo se aplica la idea de paridad en varios problemas de tableros, juegos, álgebra y teoría de números.

Ir a los videos…

Busca una contradicción

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

HeuristicasTerminamos esta serie de técnicas de resolución de problemas con una de las técnicas más finas y más usadas en las matemáticas: las pruebas por contradicción.

La idea es la siguiente. Por un momento suponemos que lo que queremos demostrar es falso. Después trabajaremos haciendo todo lo demás correctamente. La idea es llegar a una contradicción con las hipótesis del problema, o bien a algo que sabemos que es imposible. De esta forma, sabemos que debe haber un error en la demostración de eso imposible. Y como lo único que hicimos mal fue suponer que lo original era falso, debemos tener que en realidad es verdadero.

En estos videos veremos varios ejemplos de este argumento para acostumbrarnos. Es súper útil pensar en estos argumentos casi automáticamente.

Ir a los videos…