Why can't Wolframalpha solve this equation?

Factual Questions
1

I was trying to solve a brainteaser (If two students are selected at random from a class, the odds that both have blue eyes is exactly 50-50. How many students are in the class?). I kept getting non-integer solutions for every variety of the question I plugged in:

(X choose 2)/(y choose 2) = 1/2
(x(x-1))/(y(y-1))= 1/2
(x^2-x)/(y^2-y)=1/2 integer solutions

Yet the solution is simple (3 out of 4 children in the class have blue eyes; plug into any of the above equations to see they work).

What made it impossible for Wolframalpha to find the integer solution? Is this question way more computationally difficult than it looks? Am I entering something wrong? Or did I just stumble across a bug?

2

When I enter in any of your examples, Wolfram Alpha does give a (complicated) formula yielding all the integer solutions, of which there are more than just one. For example, another solution would be x = 15, y = 21.

The one thing that occasionally happens which is odd is that, in addition to giving this formula, Wolfram Alpha also sometimes says something like “Example integer solution: False”. I don’t know what the deal with that is. But it does also give the correct answer under “Integer solutions:”.

Incidentally, before someone else points it out, the question of whether a polynomial equation has any integer solutions is, in general, not algorithmically decidable (this is Matiyasevich’s theorem). However, that result needn’t concern us in this particular case; just because this particular problem happens to be manifestly part of one class of problems for which there is no general algorithm doesn’t mean it is not also manifestly part of some other class of problems for which there is such an algorithm.

3

What may be throwing you is that the formula listed under “Integer solutions:” involves a number of terms which are not, in themselves, integers (in particular, sqrt(2)). But it is designed so that the result will always be an integer nonetheless.

4

Ah, that’s probably it.

5

Incidentally, a much cleaner way of expressing the solution than Wolfram Alpha spits out is this: consider (1 + sqrt(2))^k for odd k. This will be of the form a + b * sqrt(2) for odd a and b. Take x to be (b + 1)/2 and y to be (a + 1)/2. This will always be a solution, and conversely, each solution will be of this form for a unique k.

6

Put another way, given one solution (x, y), the next solution will be (3x + 2y - 2, 4x + 3y - 3). [And conversely, the previous solution will be (3x - 2y, 3y - 4x + 1)]

7

Missing words reinstated in bold.

8

Ah, I see. I hope you’ve taken this to heart.

9

This is where I struggle sometimes, I knew the answer just by reading it by for the life of me the math above hurts…

10

Great find. Never knew of it.

I’ll spare you (for now :)) how this is interwoven in Finnegans Wake.

I smell Joyce-bait…

11

Say hi to Will Shortz for me if they choose you — I’ll do the same on your behalf.

12

Alas, you may not care for what’s coming next, sisu…

I’ll note that you probably knew that 3 out of 4 was one answer, but didn’t realize the full space of other possible answers (e.g., 15 out of 21 is also a solution, as noted before, and there are infinitely many other possibilities). I’ll also note that, while the math I’m about to write may look complicated, I believe it is genuinely, underneath the jargon (and, with my apologies, I will originally write this with some heavy jargon, for the benefit of those it would efficiently communicate to), quite simple. And to that end, if you or anyone else have any difficulty understanding any part of it, I’d be happy to explain it more clearly. I don’t think there’s anything in here that an interested high schooler couldn’t grasp, though it’s understandable that most wouldn’t immediately without appropriate background experience.

Alright, here’s the aforepromised explanation of the aforementioned solution:

First, consider x(x - 1). By completing the square, this is as good as (x - 1/2)[sup]2[/sup] - (1/2)[sup]2[/sup] = ((2x - 1)[sup]2[/sup] - 1)/2[sup]2[/sup]. So setting b to 2x - 1 and a to 2y - 1, our problem reduces to finding odd solutions to (b[sup]2[/sup] - 1)/(a[sup]2[/sup] - 1) = 1/2, which is to say, to a[sup]2[/sup] - 2b[sup]2[/sup] = -1.

For convenience, we may as well note at this point that any integer solutions to this equation will be odd (if a were even, the left side would be even; if a were odd and b were even, the left side would be 1 mod 4).

Now I’m going to introduce what I’ll call Reyemile numbers. Reyemile numbers are analogous to complex numbers, in that they are numbers of the form a + b * J for ordinary numbers a and b, and a special number J, and add, subtract, and multiply in the expected way, given a special rule for how to square J. But instead of that special rule being J[sup]2[/sup] = -1, we’ll say J[sup]2[/sup] = 2 (the only reason I am writing “J” instead of “sqrt(2)” is because I want to think of a = sqrt(2), b = 0 as a different value from a = 0, b = 1. But for the most part, a and b will be integers and this won’t matter…). By Reyemile integers, I’ll mean Reyemile numbers where a and b are integers, and by Reyemile naturals, I’ll mean Reyemile integers where a and b are nonnegative.

Also analogously to complex numbers, we’ll say that the “conjugate” of a + b * J is a - b * J. And let’s say the “norm” of a number is what you get when you multiply it by its conjugate.

Note that finding solutions to a[sup]2[/sup] - 2b[sup]2[/sup] = -1 is equivalent to finding Reyemile integers whose norm is -1. (Expand out the definitions and see for yourself!)

It’s easy to see that conjugation, and thus the norm operator, “distributes over” products (in exactly the same way as with, for example, the complex numbers). Thus, if we were to find any Reyemile number of norm -1, all its odd powers would be as well (note that the inverse of such a number would simply be the negation of its conjugate; i.e., the result of negating a while keeping b unchanged).

Mindless search quickly finds that a = 1, b = 1 is the smallest nonnegative integer solution. Thus, all odd powers of 1 + J have norm -1.

[I’m basically happy with the exposition of everything so far. From hereon out, less so…]

Now for the converse: Why are those the only Reyemile integers, up to negation?

Well, note that multiplication/division by any particular value of norm -1 puts values of norm -1 in correspondence with values of norm 1. So what is to be shown is that every Reyemile integers of norm 1 is an even power of 1 + J, up to negation. Put another way, that every Reyemile natural of norm 1 is an even power of 1 + J.

Or, put yet another way, that
[ul]
[li]A) there is a “minimal” nontrivial (i.e., not just 1) Reyemile natural of norm 1,[/li][li]B) every Reyemile natural of norm 1 is a nonfractional power of this minimal value, and[/li][li]C) the minimal Reyemile integer of norm 1 is precisely the square of the similarly minimal Reyemile integer of norm -1.[/li][/ul]

A) is trivial, given that there is any such Reyemile natural; the discrete context is such that we could have mindlessly searched for this in just the same way we mindlessly searched for and found 1 + J.

B) is by the observation that (up to negation) every Reyemile number of norm 1 is some power of every other nontrivial Reyemile number of norm 1 (in just the same way that every rotation is some power of every other nontrivial rotation; we are just dealing with hyperbolic rather than ordinary trigonometry now). And this power better be nonfractional if the “modulus” is to be minimal.

C), finally, is by noting that once we’ve established that there is some minimal m such that the Reyemile naturals of norm 1 are precisely the powers of m, and there is similarly some minimal n for norm -1, we must have that n[sup]2[/sup] = m[sup]k[/sup] for some k. Since n could be divided by m to heart’s content but is minimal, k must be either 1 or 2. And we can’t have n[sup]2[/sup] = m[sup]2[/sup], by uniqueness of square roots up to sign, by the usual reasoning for uniqueness of square roots (if C[sup]2[/sup] = D[sup]2[/sup], then (C + D)(C - D) = 0, which means one of those factors has norm zero. To finish off, we do have to invoke one nontrivial fact, which is that the only Reyemile integer of norm zero is zero itself; this observation is equivalent to the irrationality of sqrt(2))

Finally, since I said such a thing before, I’ll pedantically address how a value of the form plus or minus (1 + J)[sup]k[/sup] (1 + sqrt(2))[sup]k[/sup] allows for the sign and the k to be uniquely recovered. This is equivalent to the fact that no positive power of 1 + sqrt(2) is plus or minus 1, which follows from |1 + sqrt(2)| in the ordinary sense not being 1.

There. Phew. Clear as mud, but it’s all there as a first draft…

13

Missing words reinstated in bold.

14

More words I should have written…

15

I’ll have to go through this over the weekend, no way I have enough time from work. Stll, thanks for the amazing work!

16

Hilbert’s Tenth Problem. :slight_smile:

17

With the benefit of reflection, here’s how I might prefer to present things:

As before, the problem transforms to finding integer solutions to a[sup]2[/sup] - 2b[sup]2[/sup] = -1. That is, we want integer solutions to (a + sqrt(2)b)(a - sqrt(2)b) = -1.

In general, given a pair (p, q), let us refer to the product p * q as its “norm”, and the reflection (q, p) as its “conjugate”. Also, let’s call such a pair a “lattice point” if it has integer coordinates in the basis consisting of (1, 1) and (+sqrt(2), -sqrt(2)).

Thus, our task is to find lattice points of norm -1.

We may speak of arithmetic with such pairs, by which I mean doing everything component-wise.

Observe that the lattice points are closed under negation, conjugation, and multiplication [the latter follows from the observations that (1, 1) is the multiplicative identity and (+sqrt(2), -sqrt(2) squares to a lattice point]. Furthermore, observe that the norm operator “distributes over” products [the norm of a product of pairs is the product of their individual norms, as either way, we just get the product of all the individual coordinates], and is invariant under conjugation. Finally, observe that lattice points of norm 1 or -1 have lattice point reciprocals of the same norm (in the former case, given by conjugation, and in the latter case, by negated conjugation).

Thus, the lattice points of norm -1 are closed under multiplication by lattice points of norm 1, and conversely, given any two lattice points of norm -1, their ratio is a unique lattice point of norm 1. Accordingly, once we find any specific lattice point of norm -1, understanding the lattice points of norm -1 in general is equivalent to understanding the lattice points of norm 1.

So, let’s first classify the lattice points of norm 1.

These are particular pairs of the form (p, 1/p), closed under negation, multiplication, and conjugation (which amounts to reciprocation for these); in other words, they are given by particular values for log(|p|), closed under addition and negation.

[ul]
[li]Lemma 1 [all lemmas to be demonstrated below]: Whenever you’re interested in a collection of values which is closed under addition and negation, if it contains a smallest positive value, then it consists of precisely the integer multiples of this smallest value.[/li][li]Lemma 2: There is a smallest p > 1 such that (p, 1/p) is a lattice point. Let us call this lattice point m.[/li][/ul]
Putting those two together, we find that that the lattice points of norm 1 are precisely the integer powers of m and their negations.

All we need to do now is to find a particular lattice point n of norm -1; then we will know that the lattice points of norm -1 in general are plus or minus n * m[sup]k[/sup] for integer k.

[ul]
[li]Lemma 3: There is at least one lattice point n of norm -1.[/li][/ul]
Note that the squares of the lattice points of norm -1 are particular lattice points of norm 1; as the former (up to negation) comprise a geometric sequence with ratio m, the latter comprise a geometric sequence with ratio m[sup]2[/sup]. Thus, the latter are either precisely the even or precisely the odd powers of m.

[ul]
[li]Lemma 4: m[sup]0[/sup] is not the square of a lattice point of norm -1.[/li][/ul]
Thus, the squares of the lattice points of norm -1 are precisely the odd powers of m. Accordingly, n can be chosen, without loss of generality, to be a square root of m. More specifically, as a lattice point of norm -1, n’s two coordinates will have opposing sign; we may choose for n to be specifically to (positive, negative) square root of m.

We can conclude that the lattice points of norm -1 are precisely the odd powers of n and their negations, with the even powers instead leading to the lattice points of norm 1. [Note, as a result, that n must be (p, -1/p) for the smallest p > 1 such that this is a lattice point]

Now let us demonstrate our lemmas and, along the way, calculate n. I’ll do them in reverse order:

[ul]
[li]Proof of Lemma 4: m[sup]0[/sup] = (1, 1) has precisely two square roots of norm -1: (+1, -1) and its negation. These are quickly seen not to be lattice points (by the fact that sqrt(2) is not a reciprocal integer [note, in case you’d like to generalize this argument, that this is actually a slightly weaker requirement than irrationality of sqrt(2)]).[/li][li]Proof of Lemmas 2 and 3 and the calculation of n together: Consider the equation (p, q) = a * (1, 1) + b * (+sqrt(2), -sqrt(2)). Note that under any fixed constraint p * q = c for nonzero c, any one of the values p, q, a, or b determines each of the other values in a monotonic fashion. Accordingly, asking for one of these to fall on a particular side of a particular value is equivalent to asking for any other to fall on the corresponding side of the corresponding value. Thus, when restricting attention to lattice points (where a and b are integers), if there is any solution where p > 1, there is one with minimal p.[/li]
Thus, lemmas 2 and 3 are established as soon as we demonstrate the existence of values of norm 1 and -1, respectively. The latter existence entails the former existence by squaring, so let’s just delve in and calculate the suitably minimal n to be done with it:

By quick mindless search, we find that a = 1 (and thus b = 1, p = 1 + sqrt(2), q = 1 - sqrt(2)) is the value of norm -1 with minimal p > 1.
[li]Proof of Lemma 1: Suppose given a collection of values closed under addition and negation. This means, given any v and positive m in the collection, that v mod m (as in, the unique value in [0, m) from which v differs by an integer multiple of m) is also in the collection. If m is the smallest positive element of the collection, than each v mod m can only be zero, and thus the collection consists of precisely the integer multiples of m. [Extremely pedantic note, only for benefit of me: I am taking the “values” here to live within an Archimedean group, such as the reals] [/li][/ul]
Q.E.D.

[This argument is essentially the same as the one previously given. These pairs are just “Reyelian numbers” in another guise, with (+sqrt(2), -sqrt(2)) as J, and the lattice points as the Reyelian integers. But I think this presentation is, potentially, much friendlier/less intimidating, while still touching on the generalities I refuse to abandon.]

18

Speaking of nothing being perfect, I meant “Reyemile” rather than “Reyelian” at the end…

19

Weren’t the Reyelian’s the aliens who were supposed to rescue the Heaven’s Gate cultists during their group suicide event a few years ago? :slight_smile:

20

If your sock drawer is full of loose socks, consisting of 12 blue socks and 6 black socks and they are not stuffed together into pairs, the are random and loose - like I like my women… you are tired, it’s early and your bedroom light is burnt out, you can only go into the room once to grab socks because you are late and have no time to fool around. You can go into the living room to put your socks on but how many socks do you need to pull out of the drawer to ensure that you will have a complete pair when you return to the living room to put them on?