[Math] Integer points on a hyperbola

diophantine equationsvieta-jumping

Why I'm here

I have the following problem in probability from a book:

You have a bag with red and white balls and you draw two balls without replacing. If the probability of drawing 2 white balls is exactly 50%, how many balls are in the bag?

Suppose x is the number of red balls and y is the number of white balls. I can figure out the smallest solutions by trying out small numbers: $(1,3)$ and $(6,15)$. But are there any others?

My Work

The probability of getting two white balls (call that e) is

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

Which gives me this quadratic equation:

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

The hyperbola described by the equation x^2+2xy-y^2-x+y=0

And any positive integer points on this curve should be solutions to the problem. All I need to do is to find the integer points.

First I had the idea that if I draw a line with rational slope from the first point, I should reach a second rational point in the hyperbola. If I connect the two points I found, I get a line with equation $y=12/5(x-1)+3$,
and because there are no integer solutions between (1,3) and (6,15), I want a line with higher slope. On the other hand, I can tell that the hyperbola has an asymptote $y=(1+\sqrt2)x+1/2$, so I want a line with a slope
below $1+\sqrt2$, or the second intersection will be in the wrong branch of the hyperbola.

I had a vague idea that continued fractions help with diophantine equations, so I decided to try using the convergents of $1+\sqrt2$ to get my rational points. They're guaranteed to be above $12/5$ and exactly half of them
will be below $1+\sqrt2$, so it's worth a try. These are the points I came up with:

(only every other slope will give a positive point)

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 |

And here is a surprise: all the numbers so far are integers! They all also satisfy the initial question, and every other convergent of $\sqrt2$ is giving me a new solution to the problem. I have tried other lines with rational slopes
(by averaging the slopes of two consecutive solutions) but so far, I can't find any other integer solution.

My Question

Are all (sub-) convergents of $\sqrt2$ going to give me an integer point in the positive part of the hyperbola?
Are there any other integer points in the positive part of the hyperbola?

I know that the general quadratic equation in integers was solved by Lagrange, but this method seems really different from what I'm doing here, it only uses the continued fraction to find the first solution
(so not all convergents produce a solution), and then produces a recursive function for the rest of them. Is there any relation here?

Also, if you'd be so kind, could you suggest some expository material around quadratic equations in integers?

Other Stack Exchange questions

The following questions have been helpful to me so far:

Best Answer

Added: a careful proof that all solutions arise in the way described below begins with the observation that a solution $(x,y),$ with $|x|+|y|$ large, has either $x \approx (\sqrt 2 - 1) y$ or $y \approx (1-\sqrt 2)x.$ In the first case, we find $(2x-y) \approx -(3 - \sqrt 8) y.$ In the second case, $x+2y \approx (3 - \sqrt 8) x.$ Note that $(3 - \sqrt 8) \approx 0.17.$ That is, any solution can be moved until, say, $|x|+|y| \leq 10$ and all solutions in that diamond can be found.

The method for linking up all integer solutions is usually called Vieta Jumping on this site. In the infamous contest questions where this was first used, the quadratic form was of the type $x^2 - kxy + y^2.$ As it happens, there is no difficulty working the same technique when the quadratic part is $x^2 \pm kxy - y^2.$ This is a special case of the automorphism group of a (binary) quadratic form. As the coefficients of $x^2$ and $y^2$ both have absolute value $1,$ it becomes unnecessary to complete any squares or explicitly consider any Pell equations. The curious might borrow Binary Quadratic Forms by Buchmann and Vollmer. My favorite is Binary Quadratic Forms by Duncan A. Buell.

All the integer points can be produced by alternating two mappings beginning at the origin. The result is a double spiral, counterclockwise going outward, or clockwise going inward back to the origin.

Given an integer point on the spiral $(x,y),$ the neighboring spiral point with the same $x$ value, joined by a vertical line segment, is $$ (x, 1+2x-y) $$

Given an integer point $(x,y),$ the neighboring spiral point with the same $y$ value, joined by a horizontal line segment, is $$ (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.

enter image description here

  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 ) $$

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

Related Question