domingo, 17 de noviembre de 2013

Desigualdad diofántica

Enunciado

En este caso es fundamental el hecho de que todos los números que aparecen son enteros, ya que no se cumple con números reales, por ejemplo.

Tenemos que ab = n2 + 1, y a > b. Pongamos un ejemplo, si n = 7, podemos hacer que a = 10 y b = 5, así 10*5 = 72 + 1. Bien, pues en ese caso, a - b = 5, que es igual que √(4*7 - 3) = √25 = 5 en ese caso. Pero a veces, es incluso menor, como por ejemplo, si n = 8, y a y b pueden ser 13 y 5. En ese caso, a - b vale 8, mientras que √(4n - 3) vale √29, y este número es claramente inferior.

Puede parecer un resultado intrascendente, pero es una característica muy interesante de los números de la forma n2 + 1, entre los que se sospecha que existen numerosos números primos, pero no se sabe con certeza (cuarto problema de Landau). Además, lo que probamos es que si existe una factorización en dos factores, la diferencia entre el mayor y el segundo es mayor que un cierto valor que depende de n y que, por lo tanto, va creciendo.

En este problema se trata de jugar con las expresiones a - b y √(4n - 3), para tratar de compararlas. Puesto que ambas son expresiones positivas, podemos elevarlas al cuadrado y mantendrán sus tamaños relativos, quedando a2 + b2 - 2ab y 4n - 3 respectivamente.

Usando ahora que ab es igual a n2 + 1, podemos sumar a ambas expresiones esta igualdad dos veces y tenemos las dos expresiones transformadas en a2 + b2 y 2n2 + 4n - 1. Tal y como quedan no sirven para nada, pero si repetimos el proceso, obtenemos que las expresiones se transforman en a2 + b2 + 2ab y 4n2 + 4n - n, que son ambos cuadrados perfectos, es decir, (a + b)2 y (2n + 1)2.

Bastaría entonces si pudiésemos comparar a + b a 2n + 1 y resultase ser mayor.

De la desigualdad entre las medias aritméticas y geométricas, sabemos que (a + b)/2 ≥ √(ab), por lo que a + b será mayor o igual que 2√(n^2 + 1), y, puesto que el segundo número es algo mayor que 2n, la desigualdad es estricta. De esta forma, sabemos que a + b es mayor que 2n, y, puesto que entre los enteros hay al menos una unidad, sabemos que a + b ≥ 2n + 1.

Para llegar de nuevo a la desigualdad inicial, basta seguir el proceso al revés. Como a + b ≥ 2n + 1, y ambos son positivos, elevando al cuadrado, tenemos que (a + b)2 ≥ (2n + 1)2, y desarrollando, eso indica que a2 + b2 + 2ab ≥ 4n2 + 4n - n. Restando a ambas expresiones, respectivamente, la igualdad ab = n2 + 1 cuatro veces, tenemos que a2 + b2 - 2ab ≥ 4n - 3, que es equivalente a (a - b)2 ≥ 4n - 3. Tomando de ambas expresiones su raíz cuadrada positiva, tenemos la desigualdad que pretendemos probar, que a - b ≥ √(4n - 3).

¿cuándo se da la igualdad? Es necesario que 4n - 3 sea un cuadrado perfecto, es decir, que 4n = u2 + 3 (observa que basta que u sea impar para que se pueda conseguir un n válido), y además, ab = n2 + 1 y a + b = 2n + 1. Tratando estas tres igualdades como un sistema de ecuaciones en las que u juega el papel de parámetro, tenemos que (con un poco más de trabajo, claro) que a = (u2 + 2u + 5)/4 y que b = (u2 - 2u + 5)/4. Por ejemplo, si tomamos u = 5, n = 7, a = 10, b = 5, que es el caso que ya conocíamos, y si u = 7, n = 13, a = 17, b = 10.

sábado, 9 de noviembre de 2013

Segmentos sin cortar

Enunciado

Este problema es muy interesante.

Usa de forma bastante repetitiva una fórmula que nos dice cuántos segmentos se pueden trazar entre N puntos. Son, exactamente N*(N-1)/2, ya que cada uno de ellos lo podemos unir con todos los restantes, y así contaremos cada segmento dos veces, ya que tiene dos extremos cada segmento.

En realidad, si corta segmentos de los que se forman entre todos los puntos que hemos seleccionado, eso significa que esos 60 segmentos tienen un extremo a cada lado de la recta, y es suficiente decidir cuántos puntos hay en cada uno de los dos lados para contar cuántos segmentos no son cortados por la recta.

El caso más sencillo es que sólo haya un punto a un lado de la recta, por lo que habrá 60 exactamente al otro, pues la recta corta exactamente a 60 segmentos. Por lo tanto, no habrá más segmentos en el lado "solitario", pero habrá 60*59/2 = 1770 segmentos en el otro lado, así que habrá estos 1770 segmentos que no cortará la recta.

Otro caso diferente es que haya 2 puntos en el lado menos poblado, y entonces habrá 30 en el otro, evidentemente, ya que son 60 los segmentos que pasan entre ellos por la recta. Eso hará que haya un segmento en el lado de los 2 puntos, y 30*29/2 = 435 en el otro lado. En total, 436 segmentos que no cortan la recta.

En el tercer caso, habrá 3 y 20 puntos, y el número de segmentos que no cortan será 3 + 20*19/2 = 193.

En el cuarto, habrá 4 y 15 puntos, lo que lleva a 4*3/2 + 15*14/2 = 6 + 105 = 111 segmentos.

En el quinto caso, habrá 5 y 12 puntos respectivamente, lo que nos lleva a 5*4/2 + 12*11/2 = 10 + 66 = 76 segmentos que no cortan.

En el sexto caso, habrá 6 y 10 puntos respectivamente, de forma que hay 6*5/2 + 10*9/2 = 15 + 45 = 60 segmentos que no se cortan (casualmente, los mismos que sí que cortan).

Y ya no hay más casos, porque 7, 8 y 9 son números que no dividen a 60, por lo que no puede ser que esté esa cantidad de puntos a un lado, pues no conseguiremos 60 segmentos que pasen sobre la recta.

Por tanto, las respuestas posibles serían, como dice nuestro anónimo visitante, 60, 76, 111, 193, 436 y 1770.