wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> (x-y-z)^2-4yz=1 Solution tree
        
(Message started by: Eigenray on Jun 27^th, 2008, 6:46pm)

Title: (x-y-z)^2-4yz=1 Solution tree
Post by Eigenray on Jun 27^th, 2008, 6:46pm

Consider the equation
x² + y² + z² - 2yz - 2xz - 2xy = 1,
with x,y,z integers. Since this equation is symmetric in x,y,z, think of a solution only as the set {x,y,z}.

The diagram below shows part of an infinite binary tree. Each vertex corresponds to a solution, given by the labels of the three regions it borders.

Show that every solution appears in the tree, at a vertex unique up to reflection about the edge between the two 0s.

How many regions have the label n?

Title: Re: (x-y-z)^2-4yz=1 Solution tree
Post by TenaliRaman on Jun 29^th, 2008, 3:12am

I am bit stuck on the first part. I thought of doing it via contradiction.

However, all one could get from that is,
If there is a solution that does not appear in this tree, then using that solution you can build another infinite binary tree. Again, each of those vertex will be a solution and they each would be distinct from the solutions given in the above tree.

Am I going in the right direction?

-- AI

Title: Re: (x-y-z)^2-4yz=1 Solution tree
Post by Eigenray on Jun 29^th, 2008, 5:00am

Well, how would you find out if, e.g., {1576239, 4126648, 10803704} is in this tree?

Title: Re: (x-y-z)^2-4yz=1 Solution tree
Post by TenaliRaman on Jun 29^th, 2008, 8:20am

on 06/29/08 at 05:00:32, Eigenray wrote:

Well, how would you find out if, e.g., {1576239, 4126648, 10803704} is in this tree?

Trace its path back to root ?!

-- AI

Title: Re: (x-y-z)^2-4yz=1 Solution tree
Post by Eigenray on Jun 29^th, 2008, 8:50am

And what happens when you get to the root?

(It's not really a root; the tree continues infinitely in all directions, and in general there won't be a canonical way to single out one vertex. But that's a story for another day.)

Title: Re: (x-y-z)^2-4yz=1 Solution tree
Post by TenaliRaman on Jun 29^th, 2008, 9:02am

on 06/29/08 at 08:50:55, Eigenray wrote:

And what happens when you get to the root?

I would have gotten back {1, 0, 0} from {1576239, 4126648, 10803704}.

For e.g. we could go from {15,6,2} to {6,2,1} to {2,1,0} to {1,0,0}.

Not sure what you are getting at. I am probably missing something very obvious here.

-- AI

Title: Re: (x-y-z)^2-4yz=1 Solution tree
Post by Aryabhatta on Jun 30^th, 2008, 12:42am

The below might help, though I am unclear as to what is exactly being asked. The term "region" is confusing...

[hide]

Pick any integer m.

Find integers y,z such that yz = m(m+1)

(Basically, factorize m(m+1))

For this y and z, we can select 2 values for x which satisfy the equation of the problem.

Any solution to original equation will be found this way, so we won't be missing any solutions.

[/hide]

Title: Re: (x-y-z)^2-4yz=1 Solution tree
Post by TenaliRaman on Jun 30^th, 2008, 1:20am

I am not sure how to exactly define region. But you can sure make infinitely long trees by the following process.

Start with the solution,
{1, 0, 0}
create a new solution,
{x, 1, 0}
compute x, which comes out to 2,
{2, 1, 0}
create a new solution,
{x, 2, 1}
compute x again, which comes out to 6,
{6, 2, 1}

Similarly, you can start with {0, 1, 0} and {0, 0, 1} and what eigenray shows in his diagram is the representation of these numbers.

-- AI
P.S. -> It is pretty straightforward to show that every x that you obtain will be an integer.

Title: Re: (x-y-z)^2-4yz=1 Solution tree
Post by Eigenray on Jun 30^th, 2008, 3:58am

Yes that's the idea. Part of the problem is to figure out what I mean. ;)

If we label the vertices with solutions, then two adjacent vertices have a pair of values in common, which we can use to label the edge between them. Then two adjacent edges have one value in common, and we use that value to label the region that touches both edges.

The regions are basically components of the complement of the tree, but I suppose that depends on how it's drawn. Basically, each edge is the border between two regions, and it also touches two more regions at its ends.

But you should try drawing more of the tree to get a feel for what's going on.

on 06/29/08 at 09:02:57, TenaliRaman wrote:

I would have gotten back {1, 0, 0}

Exactly. But why?

Title: Re: (x-y-z)^2-4yz=1 Solution tree
Post by Eigenray on Jul 8^th, 2008, 7:14am

on 06/29/08 at 03:12:38, TenaliRaman wrote:

If there is a solution that does not appear in this tree, then using that solution you can build another infinite binary tree. Again, each of those vertex will be a solution and they each would be distinct from the solutions given in the above tree.

on 06/29/08 at 08:20:30, TenaliRaman wrote:

Trace its path back to root ?!

Suppose you have some solution. It lies in some tree. How would you define the root of that tree? And then, [hide]how many possible roots are there[/hide]?

Title: Re: (x-y-z)^2-4yz=1 Solution tree
Post by TenaliRaman on Jul 8^th, 2008, 1:20pm

on 07/08/08 at 07:14:45, Eigenray wrote:

Suppose you have some solution. It lies in some tree. How would you define the root of that tree?

I will define the smallest triplet in the tree to be the root.

Quote:

And then, [hide]how many possible roots are there[/hide]?

Yeah, been thinking about that. No prominent progress in this direction yet. [hide]Been trying to show that the smallest triplet achievable in any of those tree is {0, 0, 1} (or one of its permutation)[/hide]

-- AI
P.S. -> Sorry for not following up on this thread, been tied by work lately. Hope to catch up on this problem soon.

Title: Re: (x-y-z)^2-4yz=1 Solution tree
Post by Eigenray on Aug 7^th, 2008, 9:37am

You may find [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1214032409]this thread[/link] helpful. This problem was actually inspired by that one: I started with the answer and then came up with the question. And then realized that it generalizes to [hide]find all binary quadratic forms of a given discriminant[/hide], and thereby compute [hide]class numbers of imaginary quadratic number fields, and narrow class numbers of real quadratic number fields[/hide]!