Author 
Topic: (xyz)^24yz=1 Solution tree (Read 4242 times) 

Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948

Consider the equation x^{2} + y^{2} + z^{2}  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 27^{th}, 2008, 9:27pm by Eigenray » 
IP Logged 



TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001


Re: (xyz)^24yz=1 Solution tree
« Reply #1 on: Jun 29^{th}, 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: (xyz)^24yz=1 Solution tree
« Reply #2 on: Jun 29^{th}, 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: (xyz)^24yz=1 Solution tree
« Reply #3 on: Jun 29^{th}, 2008, 8:20am » 
Quote Modify

on Jun 29^{th}, 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: (xyz)^24yz=1 Solution tree
« Reply #4 on: Jun 29^{th}, 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: (xyz)^24yz=1 Solution tree
« Reply #5 on: Jun 29^{th}, 2008, 9:02am » 
Quote Modify

on Jun 29^{th}, 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: (xyz)^24yz=1 Solution tree
« Reply #6 on: Jun 30^{th}, 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: (xyz)^24yz=1 Solution tree
« Reply #7 on: Jun 30^{th}, 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. 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.

« Last Edit: Jun 30^{th}, 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: (xyz)^24yz=1 Solution tree
« Reply #8 on: Jun 30^{th}, 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 29^{th}, 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: (xyz)^24yz=1 Solution tree
« Reply #9 on: Jul 8^{th}, 2008, 7:14am » 
Quote Modify

on Jun 29^{th}, 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 29^{th}, 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: (xyz)^24yz=1 Solution tree
« Reply #10 on: Jul 8^{th}, 2008, 1:20pm » 
Quote Modify

on Jul 8^{th}, 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: (xyz)^24yz=1 Solution tree
« Reply #11 on: Aug 7^{th}, 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 



