wu :: forums « wu :: forums - (x-y-z)^2-4yz=1 Solution tree » Welcome, Guest. Please Login or Register. Apr 23rd, 2024, 7:08pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    medium (Moderators: Icarus, towr, Grimbal, william wu, SMQ, Eigenray, ThudnBlunder)    (x-y-z)^2-4yz=1 Solution tree « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: (x-y-z)^2-4yz=1 Solution tree  (Read 4254 times)
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 (x-y-z)^2-4yz=1 Solution tree   solutiontree.gif « on: Jun 27th, 2008, 6:46pm » Quote Modify

Consider the equation
x2 + y2 + z2 - 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?
 « Last Edit: Jun 27th, 2008, 9:27pm by Eigenray » IP Logged

TenaliRaman
Uberpuzzler

I am no special. I am only passionately curious.

Gender:
Posts: 1001
 Re: (x-y-z)^2-4yz=1 Solution tree   « Reply #1 on: Jun 29th, 2008, 3:12am » Quote Modify

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
 IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: (x-y-z)^2-4yz=1 Solution tree   « Reply #2 on: Jun 29th, 2008, 5:00am » Quote Modify

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

I am no special. I am only passionately curious.

Gender:
Posts: 1001
 Re: (x-y-z)^2-4yz=1 Solution tree   « Reply #3 on: Jun 29th, 2008, 8:20am » Quote Modify

on Jun 29th, 2008, 5:00am, 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
 IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: (x-y-z)^2-4yz=1 Solution tree   « Reply #4 on: Jun 29th, 2008, 8:50am » Quote Modify

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.)
 IP Logged
TenaliRaman
Uberpuzzler

I am no special. I am only passionately curious.

Gender:
Posts: 1001
 Re: (x-y-z)^2-4yz=1 Solution tree   « Reply #5 on: Jun 29th, 2008, 9:02am » Quote Modify

on Jun 29th, 2008, 8:50am, 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
 IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
Aryabhatta
Uberpuzzler

Gender:
Posts: 1321
 Re: (x-y-z)^2-4yz=1 Solution tree   « Reply #6 on: Jun 30th, 2008, 12:42am » Quote Modify

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

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.

 IP Logged
TenaliRaman
Uberpuzzler

I am no special. I am only passionately curious.

Gender:
Posts: 1001
 Re: (x-y-z)^2-4yz=1 Solution tree   « Reply #7 on: Jun 30th, 2008, 1:20am » Quote Modify

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

{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.
 « Last Edit: Jun 30th, 2008, 1:21am by TenaliRaman » IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: (x-y-z)^2-4yz=1 Solution tree   « Reply #8 on: Jun 30th, 2008, 3:58am » Quote Modify

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 Jun 29th, 2008, 9:02am, TenaliRaman wrote:
 I would have gotten back {1, 0, 0}

Exactly.  But why?
 IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: (x-y-z)^2-4yz=1 Solution tree   « Reply #9 on: Jul 8th, 2008, 7:14am » Quote Modify

on Jun 29th, 2008, 3:12am, 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 Jun 29th, 2008, 8:20am, 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, how many possible roots are there?
 IP Logged
TenaliRaman
Uberpuzzler

I am no special. I am only passionately curious.

Gender:
Posts: 1001
 Re: (x-y-z)^2-4yz=1 Solution tree   « Reply #10 on: Jul 8th, 2008, 1:20pm » Quote Modify

on Jul 8th, 2008, 7:14am, 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, how many possible roots are there?

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

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

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: (x-y-z)^2-4yz=1 Solution tree   « Reply #11 on: Aug 7th, 2008, 9:37am » Quote Modify

You may find this thread 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 find all binary quadratic forms of a given discriminant, and thereby compute class numbers of imaginary quadratic number fields, and narrow class numbers of real quadratic number fields!
 IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board