Puntos enteros en una hipérbola

Question

¿Por qué estoy aquí

Tengo el siguiente problema en la probabilidad de un libro:

Usted tiene una bolsa con el rojo y el blanco bolas y sacar dos bolas sin sustitución. Si la probabilidad de sacar 2 bolas blancas es exactamente el 50%, ¿cuántas pelotas hay en la bolsa?

Supongamos que x es el número de bolas rojas y y es el número de bolas blancas. Puedo averiguar los más pequeños de soluciones de probar pequeños números: $(1,3)$$(6,15)$. Pero hay otros?

Mi Trabajo

La probabilidad de obtener dos bolas blancas (llamada que e) es

$\mathbb{P}(e)=\frac{1}{2}=\frac{y}{x+y}\cdot\frac{y-1}{x+y-1}$

Lo que me da esta ecuación cuadrática:

$x^2+2xy-y^2-x+y=0$

Y cualquier entero positivo de los puntos de esta curva debe ser la solución al problema. Todo lo que necesitas hacer es encontrar el número entero de puntos.

Primero tuve la idea de que si se me dibuja una línea con rational pendiente desde el primer punto, debo llegar a una segunda racional punto de la hipérbola. Si puedo conectar los dos puntos que he encontrado, tengo una línea con la ecuación de $y=12/5(x-1)+3$, y porque no hay ningún número entero de soluciones entre (1,3) y (6,15), quiero una línea con mayor pendiente. Por otro lado, puedo decir que la hipérbola tiene una asíntota $y=(1+\sqrt2)x+1/2$, por lo que quiero una línea con una pendiente a continuación $1+\sqrt2$, o la segunda intersección será en el mal de la rama de la hipérbola.

Yo tenía una vaga idea de que las fracciones continuas ayudar con diophantine ecuaciones, por lo que me decidí a probar el uso de la convergents de $1+\sqrt2$ a conseguir mis puntos racionales. Que están garantizados para estar por encima de $12/5$ y exactamente la mitad de ellos estarán por debajo de $1+\sqrt2$, por lo que vale la pena intentarlo. Estos son los puntos que se me ocurrió:

(sólo pendiente le doy un punto positivo)

slope      | x      | y      | 
-----------+--------+--------+
1+5/7      | 6      | 15     |
1+12/17    | -35    | -84    |
1+29/41    | 204    | 493    |
1+70/99    | -1189  | -2870  |
1+169/239  | 6930   | 16731  |
1+408/577  | -40391 | -97512 |
1+985/1393 | 235416 | 568345 |

Y aquí está la sorpresa: todos los números son enteros! Todos ellos cumplen también con la pregunta inicial, y todos los otros convergente de $\sqrt2$ me está dando una nueva solución para el problema. Lo he intentado con otras líneas con rational pendientes (por el promedio de las pendientes de dos días consecutivos de soluciones), pero hasta ahora, no soy capaz de encontrar cualquier otro entero solución.

Mi Pregunta

Son todas las (sub-) convergents de $\sqrt2$ me va a dar un número entero de punto en la parte positiva de la hipérbola? ¿Hay algún otro número entero de puntos en la parte positiva de la hipérbola?

Sé que el general de la ecuación cuadrática en números enteros fue resuelto por Lagrange, pero este método parece muy diferente de lo que yo estoy haciendo aquí, sólo utiliza la continuación de la fracción para encontrar la primera solución (por lo que no todos convergents producir una solución), y luego produce una función recursiva para el resto de ellos. ¿Hay alguna relación aquí?

También, si usted sería tan amable, podría sugerir algún expositiva de material alrededor de las ecuaciones cuadráticas en números enteros?

Otros de Intercambio de la Pila preguntas

Las siguientes preguntas han sido de gran ayuda para mí hasta ahora:

• Cómo resolver homogénea en la formas cuadráticas en números enteros?
• Convergents como soluciones de la ecuación de Pell

Answer 1

Añadido: una cuidadosa prueba de que todas las soluciones surgen de la manera descrita a continuación empieza con la observación de que una solución de $(x,y),$ $|x|+|y|$ grandes, ha $x \approx (\sqrt 2 - 1) y$ o $y \approx (1-\sqrt 2)x.$ En el primer caso, nos encontramos con $(2x-y) \approx -(3 - \sqrt 8) y.$ En el segundo caso, $x+2y \approx (3 - \sqrt 8) x.$ tenga en cuenta que $(3 - \sqrt 8) \approx 0.17.$ es decir, la solución puede ser movido hasta, digamos, $|x|+|y| \leq 10$ y todas las soluciones en que los diamantes se pueden encontrar.

El método para la vinculación de todos los enteros soluciones es por lo general llamado Vieta Saltar en este sitio. En el famoso concurso de preguntas donde esta fue utilizado por primera vez, la forma cuadrática fue el tipo de $x^2 - kxy + y^2.$ Como es el caso, no hay ninguna dificultad para trabajar la misma técnica cuando el cuadrática parte es $x^2 \pm kxy - y^2.$ Este es un caso especial de la automorphism grupo de un (binario) de la forma cuadrática. Como los coeficientes de $x^2$ $y^2$ ambos tienen valor absoluto $1,$ se convierte en innecesario para completar cualquier plazas o considerar explícitamente cualquier ecuaciones de Pell. La curiosidad puede pedir prestado Binario Formas Cuadráticas por Buchmann y Vollmer. Mi favorito es el Binario Forma Cuadráticas por Duncan A. Buell.

Todos los enteros puntos puede ser producido por la alternancia de dos asignaciones de inicio en el origen. El resultado es una doble espiral, hacia la izquierda que va hacia fuera, o hacia la derecha va hacia el interior de vuelta al origen.

Dado un entero punto en la espiral $(x,y),$ de los vecinos de punta en espiral con el mismo $x$ valor, unidos por una línea vertical segmento, es $$ (x, 1+2x-y) $$

Given an integer point $(x,y),$ the neighboring spiral point with the same $$ y valor, unidos por una línea horizontal del segmento, es $$ (1-x-2y, y) $$

If you use on of these mapping twice in a row, you go back to where you started; this is why we alternate.

  int x,y;

  x = 1189;  y = 2871;
   cout << " $$  ( " << x << ", " << y << " ) $$ " << endl;
  while ( abs(x) < 10000  && abs(y) < 10000)
  {
    y = 1 + 2 * x - y;
    cout << " $$  ( " << x << ", " << y << " ) $$ " << endl;
    x = 1 - x - 2 * y;
    cout << " $$  ( " << x << ", " << y << " ) $$ " << endl;
  }

Note that this , well, path, moves in on one spiral arm then back out on the other; they really make up a single path.

$$ ( 1189, 2871 ) $$ $$ ( 1189, -492 ) $$ $$ ( -204, -492 ) $$ $$ ( -204, 85 ) $$ $$ ( 35, 85 ) $$ $$ ( 35, -14 ) $$ $$ ( -6, -14 ) $$ $$ ( -6, 3 ) $$ $$ ( 1, 3 ) $$ $$ ( 1, 0 ) $$ $$ ( 0, 0 ) $$ $$ ( 0, 1 ) $$ $$ ( -1, 1 ) $$ $$ ( -1, -2 ) $$ $$ ( 6, -2 ) $$ $$ ( 6, 15 ) $$ $$ ( -35, 15 ) $$ $$ ( -35, -84 ) $$ $$ ( 204, -84 ) $$ $$ ( 204, 493 ) $$ $$ ( -1189, 493 ) $$ $$ ( -1189, -2870 ) $$ $$ ( 6930, -2870 ) $$ $$ ( 6930, 16731 ) $$

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Moving outward on the black spiral, which contains (1,3)

  mpz_class x,y;

  x = 1;  y = 0;


   cout << " $$  ( " << x << ", " << y << " ) $$ " << endl;
  while ( abs(x) < 2000000000  && abs(y) < 2000000000)
  {
    y = 1 + 2 * x - y;
    cout << " $$  ( " << x << ", " << y << " ) $$ " << endl;
    x = 1 - x - 2 * y;
    cout << " $$  ( " << x << ", " << y << " ) $$ " << endl;
  }

$$ ( 1, 0 ) $$ $$ ( 1, 3 ) $$ $$ ( -6, 3 ) $$ $$ ( -6, -14 ) $$ $$ ( 35, -14 ) $$ $$ ( 35, 85 ) $$ $$ ( -204, 85 ) $$ $$ ( -204, -492 ) $$ $$ ( 1189, -492 ) $$ $$ ( 1189, 2871 ) $$ $$ ( -6930, 2871 ) $$ $$ ( -6930, -16730 ) $$ $$ ( 40391, -16730 ) $$ $$ ( 40391, 97513 ) $$ $$ ( -235416, 97513 ) $$ $$ ( -235416, -568344 ) $$ $$ ( 1372105, -568344 ) $$ $$ ( 1372105, 3312555 ) $$ $$ ( -7997214, 3312555 ) $$ $$ ( -7997214, -19306982 ) $$ $$ ( 46611179, -19306982 ) $$ $$ ( 46611179, 112529341 ) $$ $$ ( -271669860, 112529341 ) $$ $$ ( -271669860, -655869060 ) $$ $$ ( 1583407981, -655869060 ) $$ $$ ( 1583407981, 3822685023 ) $$ $$ ( -9228778026, 3822685023 ) $$

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Moving outward on the purple spiral, which contains (6,15)

  mpz_class x,y;

  x = 0;  y = 0;


   cout << " $$  ( " << x << ", " << y << " ) $$ " << endl;
  while ( abs(x) < 2000000000  && abs(y) < 2000000000)
  {
    y = 1 + 2 * x - y;
    cout << " $$  ( " << x << ", " << y << " ) $$ " << endl;
    x = 1 - x - 2 * y;
    cout << " $$  ( " << x << ", " << y << " ) $$ " << endl;
  }

$$ ( 0, 0 ) $$ $$ ( 0, 1 ) $$ $$ ( -1, 1 ) $$ $$ ( -1, -2 ) $$ $$ ( 6, -2 ) $$ $$ ( 6, 15 ) $$ $$ ( -35, 15 ) $$ $$ ( -35, -84 ) $$ $$ ( 204, -84 ) $$ $$ ( 204, 493 ) $$ $$ ( -1189, 493 ) $$ $$ ( -1189, -2870 ) $$ $$ ( 6930, -2870 ) $$ $$ ( 6930, 16731 ) $$ $$ ( -40391, 16731 ) $$ $$ ( -40391, -97512 ) $$ $$ ( 235416, -97512 ) $$ $$ ( 235416, 568345 ) $$ $$ ( -1372105, 568345 ) $$ $$ ( -1372105, -3312554 ) $$ $$ ( 7997214, -3312554 ) $$ $$ ( 7997214, 19306983 ) $$ $$ ( -46611179, 19306983 ) $$ $$ ( -46611179, -112529340 ) $$ $$ ( 271669860, -112529340 ) $$ $$ ( 271669860, 655869061 ) $$ $$ ( -1583407981, 655869061 ) $$ $$ ( -1583407981, -3822685022 ) $$ $$ ( 9228778026, -3822685022 ) $$

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Answer 2

Sé que el general de la ecuación cuadrática en números enteros fue resuelto por Lagrange, pero este método parece muy diferente de lo que yo estoy haciendo aquí, sólo utiliza la continuación de la fracción para encontrar la primera solución (por lo que no todos convergents producir una solución), y luego produce un función recursiva para el resto de ellos.

Me gusta Dario Alpern la calculadora en línea.

Introduzca los coeficientes y pulse "mostrar los pasos". Se da una buena explicación acerca de cómo se resuelve la ecuación.

Parece ser que el citado método:

$x^2 + 2 ⁢x⁢y - y^2 - x + y = 0$

El discriminante es $b^2− 4⁢a⁢c = 8$

Deje $D$ ser el discriminante. Aplicamos la transformación de Legendre $Dx = X + \alpha$, $Dy = Y + \beta$, y obtenemos:

$\alpha = 2⁢c⁢d - b⁢e = 0$

$\beta = 2⁢a⁢e - b⁢d = 4$

$X^2 + 2 X⁢Y - 1 = -16 \quad (1)$

donde el lado derecho es igual a $−D (a⁢e^2− b⁢e⁢d + e⁢d^2 + f⁢D)$

Vamos a tener que resolver varios cuadrática de congruencias. Para ello hemos de tener en cuenta el módulo y encontrar la solución modulo de los poderes de los factores primos. Entonces, combinar, por medio del Chino Teorema Del Resto.

Los diferentes módulos son divisores de la mano derecha, por lo que sólo tiene que el factor de una vez.

$-16 = −2^4$

La búsqueda de soluciones a $X$ $Y$ coprime.

Tenemos que resolver: $T^2 + 2 T - 1 \equiv 0 \pmod {-16 = −2^4}$

No hay soluciones modulo $2^4$, por lo que el sistema modular de la ecuación no tiene alguna solución.

Deje $X' = 2⁢X$$Y' = 2⁢Y$. La búsqueda de soluciones a $X'$ $Y'$ coprime.

A partir de la ecuación de $(1)$ obtenemos $X'^2 + 2 X'⁢Y' - 1 = -16 / 2^2 = -4$

Tenemos que resolver: $T^2 + 2 T - 1 \equiv 0 \pmod{-4 = −2^2}$

No hay soluciones modulo $2^2$, por lo que el sistema modular de la ecuación no tiene alguna solución.

Deje $X' = 4⁢X$$Y' = 4⁢Y$. La búsqueda de soluciones a $X'$ $Y'$ coprime.

A partir de la ecuación de $(1)$ obtenemos $X'^2 + 2 X'⁢Y' - 1 = -16 / 4^2 = -1$

Tenemos que resolver: $T^2 + 2 T - 1 \equiv 0 \pmod{ -1 = −1}$

$T = 0$

La transformación de $X' = k \quad (2)$ conversos $X'^2 + 2 X'⁢Y' - 1 = -1$ $P⁢Y'^2 + Q⁢Y'k + R⁢ k^2 = 1\quad (3)$ donde: $P = (a⁢T^2 + b⁢T + c) / n = 1$, $Q = −(2⁢a⁢T + b) = -2$, $R = a⁢n = -1$

La continuación de la fracción de expansión de $(Q + \sqrt{D / 4}) / R = (-1 +\sqrt{ 2}) / 1$ es:
$0+ // 2// \quad (4)$

Solución de $(3)$ se encuentra usando el convergente $Y' / (−k) = 1 / 0$ $(4)$

De $(2)$: $X' = 0$, $Y' = 1$

$X = 0$, $Y = 4$

$X + \alpha = 0$, $Y + \beta = 8$

Dividiendo estos números por $D = 8$:

$x = 0$
$y = 1$

$X = 0$, $Y = -4$

$X + \alpha= 0$, $Y + \beta = 0$

Dividiendo estos números por $D = 8$:

$x = 0$
$y = 0$

La continuación de la fracción de expansión de $(−Q +\sqrt{ D / 4}) / (−R) = (1 + \sqrt{2}) / (-1)$ es: $-3+ // 1, 1, 2// \quad (5)$

Solución de $(3)$ se encuentra usando el convergente $Y' / (−k) = 1 / -2$ $(5)$

De $(2)$: $X' = -2$, $Y' = 1$

$X = -8$, $Y = 4$

$X + \alpha = -8$, $Y + \beta = 8$

Dividiendo estos números por $D = 8$:

$x = -1$
$y = 1$

$X = 8$, $Y = -4$

$X + \alpha = 8$, $Y + \beta = 0$

Dividiendo estos números por $D = 8$:

$x = 1$
$y = 0$

$\fbox{$\fbox{$x = 0 \\ y = 1$}$}$

$\fbox{$\fbox{$x = 0 \\ y = 0$}$}$

Recursiva soluciones:

$x_{n+1} = x_n + 2 ⁢y_n - 1\\y_{n+1} = 2 ⁢x_n + 5 ⁢y_n - 2$

y también:

$x_{n+1} = 5 ⁢x_n - 2 ⁢y_n + 1\\y_{n+1} = - 2 ⁢x_n + y_n$

Escrito por Dario Alpern. Actualizado por última vez el 25 de julio de 2018.

Answer 3

Si usted sigue el procedimiento sugerido en la aceptó responder en su primer enlace, la ecuación se convierte en $X^2-8Y^2=8,$ y, a continuación, puede escribir $V=2Y$ conseguir $X^2-2V^2=8,$, de modo que usted obtenga todas las soluciones mirando convergents a $\sqrt2$. Por supuesto, el procedimiento implica el establecimiento $Y=2x+2y-1$$X=8y-4,$, por lo que no es inmediato que la solución integral para el $X,V$ conducirá a soluciones integrales de $x,y,$, pero la inversa es claramente cierto. Dado sus resultados numéricos, yo apostaría que siempre consigue integral de la $x,y,$, y esperar que sea fácil de mostrar.

Answer 4

Lo siento, no una respuesta, pero demasiado para un comentario. Me quedé observando cómo la fuerza bruta C solución confirma los valores que has publicado, pero los negativos son inusuales.

Mi programa de pruebas para la condición de $2W(W−1)=B(B−1)$ donde $B=R+W$.

Publicado estos resultados

Rojo Blanco
1 3
6 15
-35 -84
204 493
-1189 -2870
6930 16731
-40391 -97512
235416 568345

Los resultados que tengo son

Rojo Blanco
1 3
6 15
35 85
204 493
1189 2871
6930 16731
40391 97513
235416 568345

La parte interesante es que cuando se tienen valores negativos, tengo el mismo los valores positivos, pero el blanco es 1 mayor que su valor absoluto.

Este es el código:

#include <stdio.h>

#define MAXB    568346

int main()
{
    long long B, R, W;

    for(R = 1; R <= MAXB; R++) {
        for(W = 1; W <= MAXB; W++) {
            B = R + W;
            if(2 * W * (W - 1) == B * (B - 1)) {
                printf("R=%lld W=%lld\n", R, W);
            }
        }
    }
}