Putnam Competition 2016 B.2 "¡Subamos el nivel!"
La William Lowell Putnam Competition, o Olimpiada Putnam, es una competición anual de matemáticas de Norteamérica, en la cual participan miles de estudiantes de universidades de los Estados Unidos y Canadá. Es famosa por ser la competición más prestigiosa de matemáticas a nivel de grado en el mundo, y a su vez la más difícil, y por ello es fuente de los problemas más bellos cada año desde 1927. Además ha sido de los primeros grandes éxitos de prestigiosos matemáticos y físicos conocidos y estudiados hoy en día, como nuestro admirado Richard Feynman, que la ganó en 1939.
El premio es sobre todo económico dependiendo de la posición, con premio tanto para la universidad (hasta 25000 dólares) como para el estudiante (hasta 2500 dólares), además de una beca para el año siguiente en su universidad y demás privilegios. Además, uno de los cinco primeros recibirá una beca de 12000 dólares para estudiar en Harvard. Nada mal, ¿verdad?. Lo malo es que la nota media suele ser de 8-10... sobre 120.
Esta es una de las 12 preguntas de 2016, en concreto la B2, respondida correctamente por 94 de los 187 mejores participantes. Nadie de ellos la dejó en blanco, supongo que por lo divertido que parece desde el principio:
Definamos un número como "semicuadrado" como aquel número que es un cuadrado perfecto (su raíz cuadrada es un numero entero) o que está a una distancia igual a un cuadrado perfecto del cuadrado perfecto más cercano. Por ejemplo, 2016 es "semicuadrado" porque su cuadrado más cercano es 2025 y 2025 - 2016 = 9, cuadrado perfecto. Del 1 al 10, por ejemplo, sólo el 6 y el 7 no son "semicuadrados".
Para cualquier entero positivo N, sea S(N) el número de "semicuadrados" desde 1 hasta N, inclusive. Encuantra las constantes positivas α y β que cumplen:
$\lim _{ N\rightarrow \infty }{ \frac { S(N) }{ { N }^{ \alpha }}} =\quad \beta $
o demuestra que no existen tales constantes.
De nuevo se resolverá de una forma que no requiere casi de conocimientos avanzados de matemáticas y si hay alguno se explicará brevemente y no será complejo. De todos modos animo a todos a intentarlo por su cuenta.
Primero tratemos de averiguar la cantidad de números al rededor de cada cuadrado perfecto que están más cerca de este que de el próximo o el anterior. Para ello empezamos con la distancia entre cuadrados.
$\left[ { n }^{ 2 }-{ (n-1) }^{ 2 }\quad ,\quad { (n+1) }^{ 2 }-{ n }^{ 2 } \right] =\left[ 2n-1\quad ,\quad 2n+1 \right] $
y ahora la cantidad deseada, sabiendo que esta será siempre equitativa y exacta con la de los cuadrados congruentes (algo fácilmente deducible de las distancias entre cuadrados descritas) , pues la distancia entre ellos (resta) es siempre impar y la cantidad de números entre ellos es, por ende, par. Para ello restaremos 1 (que corresponde al mismo cuadrado) y dividiremos entre 2.
$\left[ 2n-1\quad ,\quad 2n+1 \right] \quad \longrightarrow \quad \left[ \frac { 2n-1-1 }{ 2 } \quad ,\quad \frac { 2n-1+1 }{ 2 } \right] =\left[ n-1\quad ,\quad n \right] \quad \longrightarrow \quad \left[ { n }^{ 2 }-n+1\quad ,\quad { n }^{ 2 }+n \right] $
siendo la última representación la más formal y exacta en su simbología, pues muestra la posición en la que empieza y en la que acaba el intervalo.
Ahora el siguiente paso es definir S(N), usando para ello un sencillo sumatorio. Pero antes hay que definir una cierta función extrañamente poco conocida quizá por la falta de necesidad al aplicarlo al mundo real. Me refiero a las funciones suelo y techo $\left\lfloor x \right\rfloor \left\lceil x \right\rceil$ que modifican un número de forma parecida al redondeo y el truncamiento. La función techo nos devuelve el entero igual o mayor más próximo a x. La función suelo, que es la que vamos a usar, devuelve el entero igual o menor más próximo a x. Quizá ya lo hayáis deducido, en el caso de números reales positivos la función suelo es lo mismo que truncar, pero al definir algo hay que ser rigurosos.
Si a partir de aquí intentáis seguir por vuestra cuenta os daréis cuenta pronto de la necesidad de esta función aquí.
Procedamos a deducir de la forma más sencilla S(N): la cantidad de "semicuadrados" dentro del intervalo entre dos cuadrados es igual a la raíz de tal intervalo truncada. Por ejemplo, si la distancia es mayor que 4 o igual entonces habrán mínimo 2 "semicuadrados", al igual que si esta distancia es 5, 6, 7 u 8 ($\left\lfloor \sqrt [2]{5} \right\rfloor \left\lfloor \sqrt [2] {6} \right\rfloor ,\left\lfloor \sqrt [2] {7} \right\rfloor ,\left\lfloor \sqrt [2] {8} \right\rfloor \quad =\quad 2$). Por supuesto tenemos esa cantidad duplicada, pues repetimos que el intervalo de cantidad de números inferior de un cuadrado y el superior del siguiente cuadrado son iguales. Y añadimos el mismo cuadrado, es decir, se sumará uno cada vez que se aplique el sumatorio. Por lo pronto tenemos:
$\sum _{ ?? }^{??}{ (2\left\lfloor \sqrt [ 2 ]{ n-1 } \right\rfloor } +1) + \quad ?? $
Muchas incógnitas por resolver. Pero no dejemos que eso nos asuste. El intervalo inferior claramente será 1 pero ¿y el superior? Si tenemos dentro del sumatorio n, que es la raíz de un supuesto cuadrado perfecto, entonces tiene sentido que "simulemos" tener estas raíces, porque lo que queremos es que se cuenten todos los n cuyo cuadrado es menor que N, y para ello usaremos la función suelo de la raíz de N ($\left\lfloor \sqrt [ 2 ]{ N }\right\rfloor$)
Ahora la único que nos falta es averiguar la cantidad de cuadrados perfectos desde N hasta el primer cuadrado perfecto menor que este. Tengamos en cuanta que hasta ahora sólo estábamos viendo intervalos entre cuadrados perfectos, no entre números "normales". Para averiguar esta razón usamos el mismo mecanismo que con "la cantidad de números semicuadrados en el intervalo entre cuadrados", es decir, la función suelo de la raíz de la distancia entre N y el cuadrado más cercano.
Así completamos S(N):
$\sum _{ n=1 }^{ \left\lfloor \sqrt [ 2 ]{ N } \right\rfloor }{ (2\left\lfloor \sqrt [ 2 ]{ n-1 } \right\rfloor } +1)\quad +\quad \left\lfloor \sqrt [ 2 ]{ N-\left\lfloor \sqrt [ 2 ]{ N } \right\rfloor } \right\rfloor $
$=\quad 2\sum _{ n=1 }^{ \left\lfloor \sqrt [ 2 ]{ N } \right\rfloor }{ (\left\lfloor \sqrt [ 2 ]{ n-1 } \right\rfloor ) } \quad +\quad \left\lfloor \sqrt [ 2 ]{ N } \right\rfloor \quad +\quad \left\lfloor \sqrt [ 2 ]{ N-\left\lfloor \sqrt [ 2 ]{ N } \right\rfloor } \right\rfloor $
Nos queda resolver el límite y el sumatorio. Y sí, he dicho bien el orden. Pues no es lo mismo un sumatorio infinito que uno finito, ¿verdad? Atentos ahora, que de primeras pocos estaréis de acuerdo: vemos un limite infinito en un intervalo de 1 a $ \left\lfloor \sqrt [ 2 ]{ N } \right\rfloor$ y es nos suena a ni más ni menos que a integral definida (y por supuesto $\left\lfloor \sqrt [ 2 ]{ \infty } \right\rfloor =\infty$). Sin olvidar que tendremos que multiplicar por dos el resultado de la integral, pasamos a resolverla y después hallaremos el límite:
$\int _{ 1 }^{ \left\lfloor \sqrt [ 2 ]{ N } \right\rfloor }{ \left\lfloor \sqrt [ 2 ]{ n-1 } \right\rfloor }$ $=\quad { \left\lfloor { { (n-1) }^{ \frac { 3 }{ 2 } }\frac { 2 }{ 3 } } \right\rfloor }_{ 1 }^{ \left\lfloor \sqrt [ 2 ]{ N } \right\rfloor }$=$\left\lfloor { (\left\lfloor \sqrt [ 2 ]{ N } \right\rfloor -1) }^{ \frac { 3 }{ 2 } }\frac { 2 }{ 3 } \right\rfloor \quad \longrightarrow$ $\lim _{ N\rightarrow \infty }{ \left\lfloor { (\left\lfloor \sqrt [ 2 ]{ N } \right\rfloor -1) }^{ \frac { 3 }{ 2 } }\frac { 2 }{ 3 } \right\rfloor}$ $=\left\lfloor {{ (\left\lfloor \sqrt [ 2 ]{ N } \right\rfloor ) }^{ \frac { 3 }{ 2 } }\frac { 2 }{ 3 } } \right\rfloor =\left\lfloor { (\sqrt [ 2 ]{ N } ) }^{ \frac { 3 }{ 2 } }\frac { 2 }{ 3 } \right\rfloor =$ ${ N }^{ \frac { 3 }{ 4 } }\frac { 2 }{ 3 } $
Y sólo queda el último paso:
$\lim _{ N\rightarrow \infty }{ \frac { N^{ \frac { 3 }{ 4 } }\frac { 4 }{ 3 } }{ { N }^{ \alpha } } } =\quad \beta$
La solución es entonces: $\alpha \quad =\quad \frac { 3 }{ 4 } \quad \quad \quad \beta \quad =\quad \frac { 4 }{ 3 }$
Realmente habría sido miserable por mi parte que no tuviera solución, este problema merece una.
Una rápida puntualización: esta no es la forma "oficial" de resolver el problema. La solución indicada en la web de la Putnam llega al mismo resultado a partir de otro procedimiento en mi opinión más complejo y más largo de compartir. El resultado final es el mismo de ambas formas, y os animo a ojear la solución que se muestra.
https://kskedlaya.org/putnam-archive/
De nuevo muchas gracias por leer y sentidos libres de escribir cualquier sugerencia o corrección que se os ocurra en los comentarios. Hasta la próxima.
El premio es sobre todo económico dependiendo de la posición, con premio tanto para la universidad (hasta 25000 dólares) como para el estudiante (hasta 2500 dólares), además de una beca para el año siguiente en su universidad y demás privilegios. Además, uno de los cinco primeros recibirá una beca de 12000 dólares para estudiar en Harvard. Nada mal, ¿verdad?. Lo malo es que la nota media suele ser de 8-10... sobre 120.
Esta es una de las 12 preguntas de 2016, en concreto la B2, respondida correctamente por 94 de los 187 mejores participantes. Nadie de ellos la dejó en blanco, supongo que por lo divertido que parece desde el principio:
Definamos un número como "semicuadrado" como aquel número que es un cuadrado perfecto (su raíz cuadrada es un numero entero) o que está a una distancia igual a un cuadrado perfecto del cuadrado perfecto más cercano. Por ejemplo, 2016 es "semicuadrado" porque su cuadrado más cercano es 2025 y 2025 - 2016 = 9, cuadrado perfecto. Del 1 al 10, por ejemplo, sólo el 6 y el 7 no son "semicuadrados".
Para cualquier entero positivo N, sea S(N) el número de "semicuadrados" desde 1 hasta N, inclusive. Encuantra las constantes positivas α y β que cumplen:
$\lim _{ N\rightarrow \infty }{ \frac { S(N) }{ { N }^{ \alpha }}} =\quad \beta $
o demuestra que no existen tales constantes.
De nuevo se resolverá de una forma que no requiere casi de conocimientos avanzados de matemáticas y si hay alguno se explicará brevemente y no será complejo. De todos modos animo a todos a intentarlo por su cuenta.
Primero tratemos de averiguar la cantidad de números al rededor de cada cuadrado perfecto que están más cerca de este que de el próximo o el anterior. Para ello empezamos con la distancia entre cuadrados.
$\left[ { n }^{ 2 }-{ (n-1) }^{ 2 }\quad ,\quad { (n+1) }^{ 2 }-{ n }^{ 2 } \right] =\left[ 2n-1\quad ,\quad 2n+1 \right] $
y ahora la cantidad deseada, sabiendo que esta será siempre equitativa y exacta con la de los cuadrados congruentes (algo fácilmente deducible de las distancias entre cuadrados descritas) , pues la distancia entre ellos (resta) es siempre impar y la cantidad de números entre ellos es, por ende, par. Para ello restaremos 1 (que corresponde al mismo cuadrado) y dividiremos entre 2.
$\left[ 2n-1\quad ,\quad 2n+1 \right] \quad \longrightarrow \quad \left[ \frac { 2n-1-1 }{ 2 } \quad ,\quad \frac { 2n-1+1 }{ 2 } \right] =\left[ n-1\quad ,\quad n \right] \quad \longrightarrow \quad \left[ { n }^{ 2 }-n+1\quad ,\quad { n }^{ 2 }+n \right] $
siendo la última representación la más formal y exacta en su simbología, pues muestra la posición en la que empieza y en la que acaba el intervalo.
Ahora el siguiente paso es definir S(N), usando para ello un sencillo sumatorio. Pero antes hay que definir una cierta función extrañamente poco conocida quizá por la falta de necesidad al aplicarlo al mundo real. Me refiero a las funciones suelo y techo $\left\lfloor x \right\rfloor \left\lceil x \right\rceil$ que modifican un número de forma parecida al redondeo y el truncamiento. La función techo nos devuelve el entero igual o mayor más próximo a x. La función suelo, que es la que vamos a usar, devuelve el entero igual o menor más próximo a x. Quizá ya lo hayáis deducido, en el caso de números reales positivos la función suelo es lo mismo que truncar, pero al definir algo hay que ser rigurosos.
Si a partir de aquí intentáis seguir por vuestra cuenta os daréis cuenta pronto de la necesidad de esta función aquí.
Procedamos a deducir de la forma más sencilla S(N): la cantidad de "semicuadrados" dentro del intervalo entre dos cuadrados es igual a la raíz de tal intervalo truncada. Por ejemplo, si la distancia es mayor que 4 o igual entonces habrán mínimo 2 "semicuadrados", al igual que si esta distancia es 5, 6, 7 u 8 ($\left\lfloor \sqrt [2]{5} \right\rfloor \left\lfloor \sqrt [2] {6} \right\rfloor ,\left\lfloor \sqrt [2] {7} \right\rfloor ,\left\lfloor \sqrt [2] {8} \right\rfloor \quad =\quad 2$). Por supuesto tenemos esa cantidad duplicada, pues repetimos que el intervalo de cantidad de números inferior de un cuadrado y el superior del siguiente cuadrado son iguales. Y añadimos el mismo cuadrado, es decir, se sumará uno cada vez que se aplique el sumatorio. Por lo pronto tenemos:
$\sum _{ ?? }^{??}{ (2\left\lfloor \sqrt [ 2 ]{ n-1 } \right\rfloor } +1) + \quad ?? $
Muchas incógnitas por resolver. Pero no dejemos que eso nos asuste. El intervalo inferior claramente será 1 pero ¿y el superior? Si tenemos dentro del sumatorio n, que es la raíz de un supuesto cuadrado perfecto, entonces tiene sentido que "simulemos" tener estas raíces, porque lo que queremos es que se cuenten todos los n cuyo cuadrado es menor que N, y para ello usaremos la función suelo de la raíz de N ($\left\lfloor \sqrt [ 2 ]{ N }\right\rfloor$)
Ahora la único que nos falta es averiguar la cantidad de cuadrados perfectos desde N hasta el primer cuadrado perfecto menor que este. Tengamos en cuanta que hasta ahora sólo estábamos viendo intervalos entre cuadrados perfectos, no entre números "normales". Para averiguar esta razón usamos el mismo mecanismo que con "la cantidad de números semicuadrados en el intervalo entre cuadrados", es decir, la función suelo de la raíz de la distancia entre N y el cuadrado más cercano.
Así completamos S(N):
$\sum _{ n=1 }^{ \left\lfloor \sqrt [ 2 ]{ N } \right\rfloor }{ (2\left\lfloor \sqrt [ 2 ]{ n-1 } \right\rfloor } +1)\quad +\quad \left\lfloor \sqrt [ 2 ]{ N-\left\lfloor \sqrt [ 2 ]{ N } \right\rfloor } \right\rfloor $
$=\quad 2\sum _{ n=1 }^{ \left\lfloor \sqrt [ 2 ]{ N } \right\rfloor }{ (\left\lfloor \sqrt [ 2 ]{ n-1 } \right\rfloor ) } \quad +\quad \left\lfloor \sqrt [ 2 ]{ N } \right\rfloor \quad +\quad \left\lfloor \sqrt [ 2 ]{ N-\left\lfloor \sqrt [ 2 ]{ N } \right\rfloor } \right\rfloor $
Nos queda resolver el límite y el sumatorio. Y sí, he dicho bien el orden. Pues no es lo mismo un sumatorio infinito que uno finito, ¿verdad? Atentos ahora, que de primeras pocos estaréis de acuerdo: vemos un limite infinito en un intervalo de 1 a $ \left\lfloor \sqrt [ 2 ]{ N } \right\rfloor$ y es nos suena a ni más ni menos que a integral definida (y por supuesto $\left\lfloor \sqrt [ 2 ]{ \infty } \right\rfloor =\infty$). Sin olvidar que tendremos que multiplicar por dos el resultado de la integral, pasamos a resolverla y después hallaremos el límite:
$\int _{ 1 }^{ \left\lfloor \sqrt [ 2 ]{ N } \right\rfloor }{ \left\lfloor \sqrt [ 2 ]{ n-1 } \right\rfloor }$ $=\quad { \left\lfloor { { (n-1) }^{ \frac { 3 }{ 2 } }\frac { 2 }{ 3 } } \right\rfloor }_{ 1 }^{ \left\lfloor \sqrt [ 2 ]{ N } \right\rfloor }$=$\left\lfloor { (\left\lfloor \sqrt [ 2 ]{ N } \right\rfloor -1) }^{ \frac { 3 }{ 2 } }\frac { 2 }{ 3 } \right\rfloor \quad \longrightarrow$ $\lim _{ N\rightarrow \infty }{ \left\lfloor { (\left\lfloor \sqrt [ 2 ]{ N } \right\rfloor -1) }^{ \frac { 3 }{ 2 } }\frac { 2 }{ 3 } \right\rfloor}$ $=\left\lfloor {{ (\left\lfloor \sqrt [ 2 ]{ N } \right\rfloor ) }^{ \frac { 3 }{ 2 } }\frac { 2 }{ 3 } } \right\rfloor =\left\lfloor { (\sqrt [ 2 ]{ N } ) }^{ \frac { 3 }{ 2 } }\frac { 2 }{ 3 } \right\rfloor =$ ${ N }^{ \frac { 3 }{ 4 } }\frac { 2 }{ 3 } $
Y sólo queda el último paso:
$\lim _{ N\rightarrow \infty }{ \frac { N^{ \frac { 3 }{ 4 } }\frac { 4 }{ 3 } }{ { N }^{ \alpha } } } =\quad \beta$
La solución es entonces: $\alpha \quad =\quad \frac { 3 }{ 4 } \quad \quad \quad \beta \quad =\quad \frac { 4 }{ 3 }$
Realmente habría sido miserable por mi parte que no tuviera solución, este problema merece una.
Una rápida puntualización: esta no es la forma "oficial" de resolver el problema. La solución indicada en la web de la Putnam llega al mismo resultado a partir de otro procedimiento en mi opinión más complejo y más largo de compartir. El resultado final es el mismo de ambas formas, y os animo a ojear la solución que se muestra.
https://kskedlaya.org/putnam-archive/
De nuevo muchas gracias por leer y sentidos libres de escribir cualquier sugerencia o corrección que se os ocurra en los comentarios. Hasta la próxima.
Comentarios
Publicar un comentario