Reply
Thread Tools Display Modes
#1
Old 10-20-2014, 10:58 AM
Guest
Join Date: Feb 2004
Posts: 804
Why can't Wolframalpha solve this equation?

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
Old 10-20-2014, 11:17 AM
Guest
Join Date: Apr 2007
Posts: 10,519
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.

Last edited by Indistinguishable; 10-20-2014 at 11:21 AM.
#3
Old 10-20-2014, 11:25 AM
Guest
Join Date: Apr 2007
Posts: 10,519
Quote:
Originally Posted by Reyemile View Post
I kept getting non-integer solutions for every variety of the question I plugged in:
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
Old 10-20-2014, 11:44 AM
Guest
Join Date: Feb 2004
Posts: 804
Quote:
Originally Posted by Indistinguishable View Post
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.
Ah, that's probably it.
#5
Old 10-20-2014, 01:47 PM
Guest
Join Date: Apr 2007
Posts: 10,519
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.

Last edited by Indistinguishable; 10-20-2014 at 01:49 PM. Reason: Typing in short breaks inbetween jury duty. Explanation to come later. Read up on "negative Pell's equation" if you like.
#6
Old 10-20-2014, 01:59 PM
Guest
Join Date: Apr 2007
Posts: 10,519
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
Old 10-20-2014, 03:51 PM
Guest
Join Date: Apr 2007
Posts: 10,519
Quote:
Originally Posted by Indistinguishable View Post
Incidentally, a much cleaner way of expressing the solution than Wolfram Alpha spits out is this: consider plus or minus (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 and sign.
Missing words reinstated in bold.

Last edited by Indistinguishable; 10-20-2014 at 03:51 PM.
#8
Old 10-20-2014, 05:06 PM
Charter Member
Join Date: Mar 2000
Location: Between pole and tropic
Posts: 7,544
Quote:
Originally Posted by Indistinguishable
Typing in short breaks in between jury duty.
Ah, I see. I hope you've taken this to heart.
#9
Old 10-20-2014, 08:10 PM
Guest
Join Date: May 2009
Location: I'm down here!
Posts: 2,215
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
Old 10-20-2014, 09:44 PM
Member
Join Date: Jun 2009
Location: Here
Posts: 11,566
Quote:
Originally Posted by KarlGauss View Post
Ah, I see. I hope you've taken this to heart.
Great find. Never knew of it.

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

I smell Joyce-bait...
#11
Old 10-20-2014, 09:52 PM
Charter Member
Join Date: Oct 2001
Location: New London, CT
Posts: 3,749
Quote:
Originally Posted by Reyemile View Post
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?)
Say hi to Will Shortz for me if they choose you I'll do the same on your behalf.
#12
Old 10-20-2014, 10:29 PM
Guest
Join Date: Apr 2007
Posts: 10,519
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)2 - (1/2)2 = ((2x - 1)2 - 1)/22. So setting b to 2x - 1 and a to 2y - 1, our problem reduces to finding odd solutions to (b2 - 1)/(a2 - 1) = 1/2, which is to say, to a2 - 2b2 = -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 J2 = -1, we'll say J2 = 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 a2 - 2b2 = -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
  • A) there is a "minimal" nontrivial (i.e., not just 1) Reyemile natural of norm 1,
  • B) every Reyemile natural of norm 1 is a nonfractional power of this minimal value, and
  • C) the minimal Reyemile integer of norm 1 is precisely the square of the similarly minimal Reyemile integer of norm -1.

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 n2 = mk 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 n2 = m2, by uniqueness of square roots up to sign, by the usual reasoning for uniqueness of square roots (if C2 = D2, 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)k (1 + sqrt(2))k 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...

Last edited by Indistinguishable; 10-20-2014 at 10:34 PM. Reason: I've avoided explicitly invoking hyperbolic angles, but perhaps I should have.
#13
Old 10-20-2014, 10:44 PM
Guest
Join Date: Apr 2007
Posts: 10,519
Quote:
Originally Posted by Indistinguishable View Post
Finally, since I said such a thing before, I'll pedantically address how a value of the form plus or minus (1 + J)k or just as well (1 + sqrt(2))k allows for the sign and the k to be uniquely recovered.
Missing words reinstated in bold.
#14
Old 10-20-2014, 10:54 PM
Guest
Join Date: Apr 2007
Posts: 10,519
Quote:
Originally Posted by Indistinguishable View Post
Note that finding integer solutions to a2 - 2b2 = -1 is equivalent to finding Reyemile integers whose norm is -1.
Quote:
Now for the converse: Why are those the only Reyemile integers of norm -1, up to negation?
Quote:
B) is by the observation that (up to negation) every Reyemile number of norm 1 is some (in general, possibly fractional) 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, which is to say, every angle is some multiple of every other nontrivial angle; we are just dealing with hyperbolic rather than ordinary trigonometry now). And this power better be nonfractional if the "modulus" is to be minimal.
More words I should have written...

Last edited by Indistinguishable; 10-20-2014 at 10:58 PM. Reason: Any further mistakes will live on forever...
#15
Old 10-21-2014, 09:13 AM
Guest
Join Date: Feb 2004
Posts: 804
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
Old 10-21-2014, 09:22 AM
And Full Contact Origami
SDSAB
Join Date: Dec 1999
Location: Northern Virginia
Posts: 54,974
Quote:
Originally Posted by Indistinguishable View Post
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).
Hilbert's Tenth Problem.
#17
Old 10-22-2014, 04:09 AM
Guest
Join Date: Apr 2007
Posts: 10,519
With the benefit of reflection, here's how I might prefer to present things:

As before, the problem transforms to finding integer solutions to a2 - 2b2 = -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.
  • 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.

  • Lemma 2: There is a smallest p > 1 such that (p, 1/p) is a lattice point. Let us call this lattice point m.
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 * mk for integer k.
  • Lemma 3: There is at least one lattice point n of norm -1.
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 m2. Thus, the latter are either precisely the even or precisely the odd powers of m.
  • Lemma 4: m0 is not the square of a lattice point of norm -1.
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:
  • Proof of Lemma 4: m0 = (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)]).

  • 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.

    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.

  • 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]
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.]

Last edited by Indistinguishable; 10-22-2014 at 04:13 AM. Reason: Nothing's ever perfect...
#18
Old 01-14-2015, 02:10 PM
Guest
Join Date: Apr 2007
Posts: 10,519
Speaking of nothing being perfect, I meant "Reyemile" rather than "Reyelian" at the end...
#19
Old 01-15-2015, 07:30 PM
Charter Member
Join Date: Sep 2003
Location: Southeast Florida USA
Posts: 20,255
Quote:
Originally Posted by Indistinguishable View Post
Speaking of nothing being perfect, I meant "Reyemile" rather than "Reyelian" at the end...
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?
#20
Old 01-15-2015, 10:18 PM
BANNED
Join Date: Jan 2015
Posts: 320
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?
#21
Old 01-15-2015, 11:07 PM
Guest
Join Date: Apr 2007
Posts: 10,519
Quote:
Originally Posted by LSLGuy View Post
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?
I believe you've gotten your cults mixed up. The Raelians were the ones who claimed to have cloned a human baby.
#22
Old 01-15-2015, 11:09 PM
Guest
Join Date: Apr 2007
Posts: 10,519
Quote:
Originally Posted by vomit_comet View Post
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?
This seems rather simple. You need to pull out 3 socks (2 could be different colors, but 3 guarantees some color doubles up).
#23
Old 01-16-2015, 12:00 AM
BANNED
Join Date: Jan 2015
Posts: 320
Quote:
Originally Posted by Indistinguishable View Post
This seems rather simple. You need to pull out 3 socks (2 could be different colors, but 3 guarantees some color doubles up).
It is indeed that simple.
#24
Old 01-16-2015, 03:55 PM
Member
Join Date: Jun 2009
Location: Here
Posts: 11,566
Quote:
Originally Posted by Indistinguishable View Post
Speaking of nothing being perfect, I meant "Reyemile" rather than "Reyelian" at the end...
Man, you spent one year and three months going over your proof.

Also, I'd like to nominate you for the Stranger on a Train award for best/longest/most thorough posting on a technical subject.

Seems like you'd be a more well-known contender, but there are fewer math heads here than everyone and his brother who talk about rockets and stuff.
#25
Old 01-17-2015, 01:18 AM
rsa rsa is offline
Guest
Join Date: Sep 2001
Posts: 2,108
When I use Yahoo search for "Reyemile number" I get this thread as the first hit and then a bunch of results for dice and magic cards and also one for "persistent genital arousal disorder."
#26
Old 01-17-2015, 02:26 AM
Guest
Join Date: Apr 2007
Posts: 10,519
Quote:
Originally Posted by Leo Bloom View Post
Man, you spent one year and three months going over your proof.
Just three months, I'm afraid...

Quote:
Also, I'd like to nominate you for the Stranger on a Train award for best/longest/most thorough posting on a technical subject.
Aw, thanks. (Unless this was dependent on the full fifteen month presumption! )

Quote:
Originally Posted by rsa View Post
When I use Yahoo search for "Reyemile number" I get this thread as the first hit and then a bunch of results for dice and magic cards and also one for "persistent genital arousal disorder."
"Reyemile number" is not a standard term; I named it in this thread after the OP. If you seek standard names for such things, the system of "Reyemile numbers" is isomorphic to what are called the split-complex numbers, while the "Reyemile integers" comprise the quadratic integer ring Z[sqrt(2)].

Last edited by Indistinguishable; 01-17-2015 at 02:29 AM.
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Forum Jump


All times are GMT -5. The time now is 12:43 AM.

Copyright © 2017
Best Topics: oxygen high seminal piece man from nantucket murder in antarctica nickelodeon's definition 1973 belmont squeaky belt dones back pills sabotage word origin rich mans family memento ending visable bra microwavable soup presidents lump fat singer turler watches miami beach boac ernest mayhand cassandra peterson boobs range rover buying fat on steak gatorade green drinking vanilla extract potassium cyanide pills bonobo dick superduper windows define goat rope i twist quasi socialist chewing wheat hebe jewish hershey highway sulcular irrigation joanna cameron today what does bistro mean in italian amazon out of stock how long ball peen hammer uses susanna hoffs walk like an egyptian pre brush rinse vs mouthwash what does fhr mean on a scratch ticket what do arabs wear why is the dmv so slow cat ate all the weed stuck out to me synonym sulfamethoxazole/trimethoprim and alcohol shaved head with receding hairline how many days do you work in a year sell fur coat nyc velveting chicken baking soda problems with seiko solar watches red black typewriter ribbon mixing an acid and a base dry feet at night my light switch does not have a ground wire putting out candle with fingers why do my breasts point outward 4 wire phone cord irish wolfhound chihuahua mix how to make a doctors appointment for the first time where do djs get their acapellas did columbus know he was not in india what to do for a stiff neck that won't go away hot pan cold oil what did maureen o'hara say to john wayne why do deer run out in front of cars nighthawk 2000 carbon monoxide detector manual legends of hollywood stamps series