wu :: forums - Print Page


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

        riddles >> hard >> Non-integer colouring
        
(Message started by: JocK on May 24^th, 2006, 2:55pm)

Title: Non-integer colouring
Post by JocK on May 24^th, 2006, 2:55pm

(Inspired by http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1148278845)

Imagine an infinite square grid of points. The distance between nearest neighbour points is unity. And imagine that you are provided with an unlimited supply of 'anti-Diophantine markers'. If you place such a marker at a certain gridpoint, that gridpoint as well as all gridpoints that are a non-integer distance away from the marker get coloured.

Question 1: if you can place the markers at any gridpoint, how many markers do you need to colour the whole grid?

Question 2: if you are constraint to place the markers [edit]on gridpoints[/edit] such that their mutual distances are all integer, how many markers do you need to colour the whole grid?

Title: Re: Non-integer colouring
Post by SMQ on May 24^th, 2006, 6:41pm

Well, let's start with the obvious. :)

In one dimension, you need aleph-null markers either way: one covering each integer.

In two dimensions, the points left uncovered by a marker at (0,0) are exactly the legs of the pythagorean triples.
http://mathworld.wolfram.com/images/eps-gif/PythagoreanTriples_1000.gif
(image credit: Mathworld (http://mathworld.wolfram.com/PythagoreanTriple.html))

So far, that's all I have. ;)

--SMQ

Title: Re: Non-integer colouring
Post by Barukh on May 25^th, 2006, 1:13am

Interesting...

I think 2 markers placed at points (0, 0) and (-1, -1) will suffice. All we need is to show that the following system of Diophantine equations has no solutions:

x² + y² = m²,
(x+1)² + (y+1)² = n²
Indeed, subtracting the first from the second, we get:

2(x+y+1) = n² - m²,
which means n-m >= 2. Therefore, 2(x+y+1) >= 4m+4, or x+y >= 2m+1. This is a contradiction, since x < m and y < m.

Even simpler: two markers (0, 0), (-1, 0) satisfy the conditions of the second question.

Makes sense?

Title: Re: Non-integer colouring
Post by Sjoerd Job Postmus on May 25^th, 2006, 3:49am

on 05/25/06 at 01:13:43, Barukh wrote:

Even simpler: two markers (0, 0), (-1, 0) satisfy the conditions of the second question.

Makes sense?

(0,0), (-1,0):
Is (-2,0) covered? It's integer distance from (0,0) and integer distance from (-1,0) too... so it's not coloured.

Ok, the 0,0 and -1, -1:
The point (-4,3) is still uncovered! Proof:

0 - -4 = 4
3 - 0 = 3
Squared, summed, and sqrooted: 5
So marker (0,0) doesn't cover it.
What about marker (-1,-1)
-1 - -4 = 3
3 - -1 = 4
Again, leaving distance 5. So our grid isn;t coloured.

Title: Re: Non-integer colouring
Post by Barukh on May 25^th, 2006, 6:14am

Your analysis is correct, Sjoerd. My argument is flawed... :-/

Title: Re: Non-integer colouring
Post by SMQ on May 25^th, 2006, 7:00am

[edit]I missed part of SJP's analysis -- he disproved (0,0) and (-1,-1) but not (0,0) and (-1,0) right? If (0,0) and (-1,0) leave any points uncolored axcept the x-axis, disregard all the below... ???[/edit]

OK, then I think we can answer question 1 in the plane: two markers cannot be sufficient. WOLG consider markers at (0,0) and (x,y): at least points (x,0) and (0,y) (the axis crossings) will remain uncolored. Certainly, though, by Barukh's analysis, markers at (0,0), (1,0), and (0,1) are sufficient to color the plane: the first two markers color all points except the x-axis and the third marker colors the entire x-axis.

That still leaves Q2 open, as the distance from (1,0) to (0,1) is non-integral, although we know from the axis-crossing argument that at least three markers are required. It also still leaves both questions open in higher dimensions -- the axis-crossing argument doesn't hold in higher dimensions.

--SMQ

Title: Re: Non-integer colouring
Post by Sjoerd Job Postmus on May 25^th, 2006, 9:47am

Let's denote our three markers M1, M2 and M3 - since, by our axes-crossing-theorem/argument, we need at least 3 markers...

They must all be integral distance from eachother...
Without loss of generality, we can position our marker first on M1 = (0,0).
The second markers will be on:
M2 = (p,q)
M3 = (r,s)

Yielding:
p^2 + q^2 = n^2
r^2 + s^2 = m^2
and
(p-r)^2 + (q-s)^2 = o^2
p^2 - 2pr + r^2 + q^2 - 2qs + s^2 = o^2

Substracting m^2 and n^2
-2pr - 2qs = o^2 - n^2 - m^2

2 * (-pr - qs) = o^2 - n^2 - m^2
0 or 2 of these are even... We know all numbers are integer, so -pr and -qs will be an even, or an odd number. Twice that, will be even.
o^2 - n^2 - m^2 = even
If three of these were odd:
odd + odd + odd ?= even... NO!
Or one of these:
even + even + odd ?= even... NO!
So two or none must be odd.

But, where to place these? I assume a pythagorean triplet would work... but would it...

Let's take
M1 = (0,0)
M2 = (4,0)
M3 = (4,3)
Just for kicks...

It won't work... (0,3) isn't covered. Would covering that one, be sufficient? I don't know.

Who knows, help us all, and give us the answer!
---
Edit: Anyhow, I think for Q2, the answer is 4... why, I dunno, because 3 wouldn't be enough

Title: Re: Non-integer colouring
Post by Barukh on May 27^th, 2006, 9:24am

Question 2 doesn't state expicitly that markers can be placed only at grid points. But I assume this is the case?

Title: Re: Non-integer colouring
Post by Sjoerd Job Postmus on May 27^th, 2006, 11:18am

on 05/27/06 at 09:24:46, Barukh wrote:

Question 2 doesn't state expicitly that markers can be placed only at grid points. But I assume this is the case?

I assume this is the case. What would be your solution if this isn't true?

Ok... yet another thing...

Let us consider the grid, and the integer-distance-marker-problem.

Let's think of three markers, M1, M2 and M3

Let's consider the mid-point of any of the sides, call it S - without a reason

find angle M1,S,M3, and distance S,M3...
Now, on the line through S and M3, mark another marker, the same distance away from S, but on the other side, obviously it is on a grid point. But, now our question is: Is the distance from M3 to M3' integer?

I can't proof it yet... but I don't have enough time!

Let us consider, WOLG, M1 = (0,0), if your solution doesn't have a marker there, move it to there!
M2 = (a,b)
M3 = (c,d)

Midpoint S will be: (.5a, .5b)
Let's flip M3 in M2...

((-(c - .5a) + .5a), (-(d - .5b) + .5b))

Which makes:
M3' = ((-c + a), (-d + b))

Distance?

M3 - M3'

sqrt((c - (-c + a))^2 + (d - (-d + b))^2)

Let's see...

sqrt{(2c - a)^2 + (2d - b)^2}

Now, is this value an element from N? I don't know...

But we already know that
sqrt{(c-a)^2 + (d-b)^2} is from N
sqrt{a^2 + b^2} is from N
sqrt{c^2 + d^2} is from N

Now, ((-c + a), (-d + b)) must be of integer distance from M1 and M2..., because, in reality, all we did was take the triangle, and rotate it 180 degrees in midpoint S ;)...

So...
sqrt{(-c+a)^2 + (-d + b)^2} is from N

sqrt{((-c+a)-a)^2 + ((-d+b)-b)^2} would mean
sqrt{(-c)^2 + (-d)^2} is from N, wich is a duh-statement.

I'll continue it when I have pencil and paper near me... (read: Not Now!)

Title: Re: Non-integer colouring
Post by JocK on May 27^th, 2006, 12:02pm

on 05/27/06 at 09:24:46, Barukh wrote:

Question 2 doesn't state expicitly that markers can be placed only at grid points. But I assume this is the case?

Sure it is! (Edited the problem statement to make this explicit.)

Title: Re: Non-integer colouring
Post by Barukh on May 28^th, 2006, 6:32am

on 05/25/06 at 09:47:46, Sjoerd Job Postmus wrote:

Let's take
M1 = (0,0)
M2 = (4,0)
M3 = (4,3)
Just for kicks...

It won't work... (0,3) isn't covered. Would covering that one, be sufficient? I don't know.

Who knows, help us all, and give us the answer!

Sjoerd, I think your 4-point configuration is sufficient. Here’s what I came with.

First, I took 2 points (0,0) and (4,0) and tried to identify all other points that are at integer distances from this pair. This means to solve a pair of quadratic Diophantine equations (QDE):

x² + y² = m²,
(x-4)² + y² = n²

It is immediately clear that m-n should be even. Several cases need to be considered (I won’t make the same mistake again!):

1. m = n. This yields the unique solution on an x-axis: (2,0).
2. |m – n| = 4. This yields an infinite number of solutions (m, 0) on x-axis.
3. |m – n| = 2. This is the most interesting case. Combining all three equations together, I got m = |2x-3|, and plugging this into the first equation, finally:
-3x² + y² + 12x – 9 = 0.
Now, there is a standard way to solve such QDE (there is even a nice online solver (http://www.alpertron.com.ar/QUAD.HTM)). In this particular case, there are two basic solutions (1, 0), (4, 3) that generate two infinite families of solutions according to the following recurrent formula:
x_k+1 = 2x_k - y_k – 2,
y_k+1 = -3x_k + 2y_k + 6.
I immediately noticed that the first family – except two solutions - consists of solutions in the 2nd quadrant only, while the second family similarly consists almost of solution in the the 4th quadrant.

Next, I took another pair of points - (0,0), (0,3) – and made the same derivation. The QDE to solve this time was
x² - 8y² + 24y – 16 = 0,
which again has two basic solutions (0, 1), (0, 2) and two iterative families:
x_k+1 = 3x_k + 8y_k – 12,
y_k+1 = x_k + 3y_k - 3.
Now, these families generate solutions in the 1st and 3rd quadrants, except a few cases on the axes.

Conclusion: the only point not on the axes at the integer distance from the triple (0,0), (4,0), (0,3) is the point (4,3). This point is at the irrational distance from the points (-4,0) and (0,-3). Therefore, the four points mentioned by Sjoerd colour the whole plane.

If I didn’t make any mistake, I’m sure an easier demonstration must exist.

:-/

Title: Re: Non-integer colouring
Post by Sjoerd Job Postmus on May 28^th, 2006, 7:14am

Woah! This is way above my head... hope I'll be able to do such math one-day too...

So, we know there's one solution.

I also suggest that: Any Primitive Pythagoras Triplet, plus the point obtained by rotating the right angle around the midpoint of the hypothenusa(sp?) will yield another valid solution.

So: Let's have Primitive Pyth.Triplet: (a,b,c), then
(0,0)
(a,0)
(a,b)
(0,b)

Yields a valid solution.

Iff this is true, then
(0+n,0+m)
(a+n,0+m)
(a+n,b+m)
(0+n,b+m)
is also a valid solution.
n and m being whole integer values, that are not related to those mentioned in Barukh's proof.

Do I need to get you more stuff to proof? :P j/k... I'm just the trial-and-error bloke, and the rest of you are more into the rigorous proof thing...
Me too, actually, but my math isn't good enough to do it for this hard stuff.

Thanks! Now I need to either find a failure in your proof using: There exists a value for which it doesn't work, thingy... or wait for someone else to go through your proof step-by-step, and find that it's correct. I think it is, though... makes sense.

Title: Re: Non-integer colouring
Post by JocK on May 28^th, 2006, 7:31am

on 05/28/06 at 06:32:00, Barukh wrote:

Sjoerd, I think your 4-point configuration is sufficient.

Well done guys.

Is a 4-point configuration also necessary? :P ;)

Title: Re: Non-integer colouring
Post by Barukh on May 28^th, 2006, 10:46am

on 05/28/06 at 07:14:22, Sjoerd Job Postmus wrote:

Thanks! Now I need to either find a failure in your proof using: There exists a value for which it doesn't work, thingy... or wait for someone else to go through your proof step-by-step, and find that it's correct. I think it is, though... makes sense.

Unfortunately, my above argument is broken: I just realized that in the first case when (x_n, y_n) is a solution, so is (x_n, -y_n), and likewise in the second case. So, both cases generate solutions in every quadrant.

Fortunately, the result is still valid: the argument may be repaired by considering the ratios of x_n/y_n in both cases.

This is intimately related to continued fractions. I remember Icarus once or twice posted a method of solving such recurrences.

Title: Re: Non-integer colouring
Post by Icarus on May 28^th, 2006, 11:41am

The method I have posted solves homogenous linear recurrences with constant coefficients. Unfortunately, your recurrence is not homogenous.

Title: Re: Non-integer colouring
Post by Sjoerd Job Postmus on May 28^th, 2006, 1:13pm

Well... let me ask something. because we just have a rectangle, if there is any problem(non-coloured item), we have 4, 8, 12, etc problems.

Let's say (x,y) isn't coloured. Then, I say... (4-x,y) isn't coloured, (x,3-y) isn't coloured, and (4-x,3-x) isn't coloured. See why?

So, we can actually ignore the solutions in other quadrants then the first, because those are just copies.

Maybe this helps a bit more?

Title: Re: Non-integer colouring
Post by Eigenray on May 29^th, 2006, 8:15pm

on 05/28/06 at 06:32:00, Barukh wrote:

If I didn’t make any mistake, I’m sure an easier demonstration must exist.

You don't need to solve the QDEs separately -- two hyperbolas intersect in 4 points.

By the triangle inequality, and parity, (x,y) satisfies one of the following 5*4 pairs of equations:
r₁ = |(x, y)| - |(x-4, y)| = 0, +/-2, +/-4,
r₂ = |(x, y)| - |(x, y-3)| = +/-1, +/-3.

r₁=0 or +/-4 means y=0. Since (3,4,5) is the only Pythagorean triple with a 3, x=+/-4, but (-4,0) is no good, and (4,0) is taken.
Similarly, r₂=+/-3 means x=0; (3,4,5) is also the only triple with a 4, so again y=+/-3 is no good.
(r₁,r₂)=(2,1) implies (x,y)=(4,3), which we have.
(r₁,r₂)=(+/-2, -/+1) implies (via Mathematica, i.e., a finite calculation but I'm lazy) that (x,y) = (4(10+/-3[sqrt]6), 27-/+8[sqrt]6)/23, no good.
Finally, (r₁,r₂)=(-2,-1) implies (x,y) = (20, 21)/23, no good.

In fact this argument shows that if infinitely many points in the plane have mutual distances all integral, then they are all collinear (specifically, given any non-degenerate triangle, there are only finitely many places for the other points). Hence we can start with any Pythagorean triple and mark uncolored points all willy-nilly, and it'll only take a finite number of markers. But:

Question 3: For any N, find N non-collinear markers, on gridpoints, with mutual distances all integral, which do not color the whole grid.

Title: Re: Non-integer colouring
Post by JocK on May 30^th, 2006, 12:12pm

Guys, I'm gonne give you a BIG helping hand here:

[hide]3[/hide] markers at integer distance suffice to colour all gridpoints ... :o

Try it! ;D

Title: Re: Non-integer colouring
Post by Eigenray on May 30^th, 2006, 8:25pm

on 05/30/06 at 12:12:00, JocK wrote:

[hide]3[/hide] markers at integer distance suffice to colour all gridpoints ... :o

And all this time I've been trying to prove they don't...

Any lattice triangle has rational area K (in fact 2K is an integer by Pick's theorem). Hence if the sides a,b,c are integers, it's [link=http://mathworld.wolfram.com/HeronianTriangle.html]Heronian[/link]. (in fact, by Hero's formula, (a+b+c)⁴ = 4(2K)² = 0 mod 2, so a+b+c is even, and then 2K is even, hence K is an integer). (It's worth noting that given an integral lattice triangle, there will be lots of rational points a rational distance from all three vertices (e.g., the base of each altitude).)

For a Heronian triangle with sides lengths (a,b,c) to color all lattice points, it must not be a right triangle, and no side may be parallel to an axis. In particular, each of a,b,c must be the hypotenuse of some Pythagorean triple, but (a,b,c) itself can't be Pythagorean.

Take a Heronian triple (a,b,c). For each way of writing a²=u²+v², with u,v>0, there are two rational points (p,q) a distance b from (0,0), and c from (u,v). If (p,q) is integral, and p != 0,u and q != 0,v, then for each |i|<a, |j|<b, with i=a, j=b mod 2, check for integral points (x,y) satisfying
|(x,y)| - |(x-u,y-v)| = i,
|(x,y)| - |(x-p,y-q)| = j.
If there are no such (x,y) other than the 3 vertices, congratulations.

Using this [link=http://cis.csuohio.edu/~somos/tritab.html]list[/link] of primitive Heronian triangles with sides < 300, I checked all 2080 Heronian triangles with sides < 300. Assuming my program is correct, none of them work.

Title: Re: Non-integer colouring
Post by Eigenray on Jul 30^th, 2007, 3:12am

on 05/30/06 at 12:12:00, JocK wrote:

[hide]3[/hide] markers at integer distance suffice to colour all gridpoints ... :o

Anyone have any thoughts on this?

Title: Re: Non-integer colouring
Post by SMQ on Jul 30^th, 2007, 1:52pm

on 07/30/07 at 03:12:28, Eigenray wrote:

Anyone have any thoughts on this?

From your above, in the case where a (or b) is even, and so i (or j) can be 0, is |(x,y)| - |(x-u,y-v)| = 0 (or |(x,y)| - |(x-p,y-q)| = 0) sufficient to establish that |(x,y)| is an integer? If not, is it within the realm of possibility that one or more solutions could have been missed by your program because it found an erroneous disqualifying point (x,y) where |(x,y)| - |(x-u,y-v)| = 0 but |(x,y)| is not an integer? Assuming your program is otherwise correct and the bounds sufficient, that's the only potential loophole I can find...

--SMQ

Title: Re: Non-integer colouring
Post by Eigenray on Jul 30^th, 2007, 11:58pm

That's a good point, but it turns out (empirically, no proof) that |(x,y)| is always an integer. The only possible exception would be if both i=j=0, so (x,y) is the intersection of the bisectors from (0,0) to (u,v) and (p,q), which works out to

{ x, y }= { [v(p²+q²)-q(u²+v²)]/[2(pv-qu)], [u(p²+q²)-p(u²+v²)]/[2(qu-pv)] }

But you agree with the rest of the reasoning? I use Mathematica's Rest@OrderedSumOfSquaresRepresentations[2,a²] to find the possibilities for (u,v) [WLOG, u > v > 0; Rest drops the first term which is (a,0)]. For each (u,v), I find

(p,q) = t/a (u,v) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif h/a (-v,u), where t=(a²+b²-c²)/(2a), h = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{b²-t²}.

h is the altitude from side a, so is rational because of Heronity. If (p,q) is integral, and not on the same row or column as (0,0) or (u,v), I look for a 4-th point (x,y). The expression for x,y in terms of u,v,p,q,i,j is nasty, but in all cases I've found such a point, and checked to make sure there were no false positives.

The tricky part seems to be generating the Heronian triplets to test: this [link=http://mathworld.wolfram.com/HeronianTriangle.html]parameterization[/link] doesn't produce primitive triplets, only one from each similarity class, and the gcd can be arbitrarily large. I don't actually know a good way to produce all triplets with max side < M. And it's not enough to just consider primitive triplets, since the property we're looking for depends on the embedding. For example, the smallest multiple of (5,5,6) which can be embedded in a lattice with no side parallel to an axis is 13*(5,5,6).

Title: Re: Non-integer colouring
Post by Barukh on Jul 31^st, 2007, 6:02am

on 07/30/07 at 23:58:30, Eigenray wrote:

But you agree with the rest of the reasoning?

I think I need an explanation how does the 4th point prove anything.

Title: Re: Non-integer colouring
Post by SMQ on Jul 31^st, 2007, 7:38am

on 07/30/07 at 23:58:30, Eigenray wrote:

But you agree with the rest of the reasoning?

I do. To restate, just to be sure I'm understanding: consider any three lattice points at mutually-integer distances, and the triangle they form:

1) The area of any triangle with verteces on the lattice points is clearly integer or half-integer (construct the rectangular bounding-box with sides parallel to the lattice axes, subtract the areas of the at-most-three right triangles outside the original triangle).

2) Any triangle with integer side lengths and integer or half-integer area is, by definition, Heronian.

3) For any right triangle, a fourth point at the remaining corner of a rectangle created by rotating a copy of the triangle 180 degrees and joining the hypotenuses is clearly at an integer distance from all three original points (and therefore not colored by any of the three original points).

4) For any triangle with a side parallel to one of the lattice axes, the lattice point at the base of the altitude to that side will clearly be at an integer distance from all three original points (unless the parallel side is a leg of a right triangle, in which case observation (3) applies instead).

5) WLOG, Let the verteces of the triangle be at coordinates (0,0), (u,v) and (p,q) where p, q, u and v are all integers, u and v are positive, and |(u,v)|, |(p,q)|, and |(u-p),(v-q)| are integers. By parity and the triangle inequality, any point (x,y) at an integer distance from all three points of the triangle will be at an intersection of the hyperbolas given by |(x,y)| - |(x-u,y-v)| = +/- i and |(x,y)| - |(x-p,y-q)| = +/- j for some 0 < i <|(u,v)|, i = |(u,v)| mod 2, 0 < j <|(p,q)|, j = |(p,q)| mod 2.

6) If any such (x,y) coincides with a lattice point and is not a vertex of the original triangle then none of the three original points colors (x,y) and so together they do not constitute a solution.

Quote:

The tricky part seems to be generating the Heronian triplets to test

Although the fact that the triangles are Heronian is interesting, I'm not sure it's helpful. What if instead of generating Heronian triples, you generate Pythagorean triples? Generating all Pythagorean triples up to some max side < M is fairly straightforward. Then, given Pythagorean triples (u,v,a) and (s,t,b) check the up-to-eight possible points (p,q) = { (s,t), (s,-t), (-s,t), (-s,-t), (t,s), (t,-s), (-t,s), (-t,-s) }, p <> u, q <> v for integer distance to (u,v), then search for (x,y) as before for any that form non-degenerate, non-right triangles with (0,0).

--SMQ

Title: Re: Non-integer colouring
Post by Barukh on Jul 31^st, 2007, 10:31am

Aha! I think I've got it! The intersection of two hyperbolas! Thanks, SMQ. BTW:

on 07/31/07 at 07:38:57, SMQ wrote:

By parity and the triangle inequality, any point (x,y) at an integer distance from all three points of the triangle will be at an intersection of the hyperbolas given by (x² + y²) - [(x-u)² + (y-v)²] = i² and (x² + y²) - [(x-p)² + (y-q)²] = j² for some 0 < i <|(u,v)|, i = |(u,v)| mod 2, 0 < j <|(p,q)|, j = |(p,q)| mod 2.

these are not exactly hyperbolas. ;)

Eigenray, how do compute this intersection? Again using Mathematica?

Title: Re: Non-integer colouring
Post by SMQ on Jul 31^st, 2007, 11:03am

on 07/31/07 at 10:31:43, Barukh wrote:

these are not exactly hyperbolas. ;)

No? ???

Each is the locus of points (x,y) where the difference of the distances to two fixed points, (0, 0) and either (u, v) or (p, q), is a constant, either i or j. I thought that was the definition of a hyperbola (http://mathworld.wolfram.com/Hyperbola.html).

Edit: Oops! I'm an idiot. You mean you can't square an equation by just squaring each of the terms... dang it. I'm sure that wasn't Eigenray's mistake (his version has it right). Fixed, now. :-[

--SMQ

Title: Re: Non-integer colouring
Post by Eigenray on Jul 31^st, 2007, 2:42pm

on 07/31/07 at 07:38:57, SMQ wrote:

To restate, just to be sure I'm understanding:

Yes, exactly. Thanks for summarizing.

Quote:

Although the fact that the triangles are Heronian is interesting, I'm not sure it's helpful. What if instead of generating Heronian triples, you generate Pythagorean triples?

That'll work, I guess. But for example, with M=300, there are 209 Pythagorean triples, meaning 21945 possible triangles to check, 557 of which are integral, with the third side also no more than 300. On the other hand, using a list of 991 primitive Heronian triplets, there are 2080 non-primitive triplets; I try to embed 1037 of them, and end up with 582 distinct embeddings. I'm not sure where the discrepancy lies, but in both cases there are 517 congruence classes of triangles embedded.

[Heuristically, I'd guess that there are ~ 1/(2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif) M log M Pythagorean triples with hypotenuse < M, but I don't know how many pairs of triples give an integral triangle (and each triangle takes O(M²) to find a 4th point).]

I haven't really been trying to optimize my program; it's still written in Mathematica.

Quote:

Eigenray, how do compute this intersection? Again using Mathematica?

I used Mathematica's Solve to find (x,y) as a function of u,v,p,q,i,j, and copy and pasted that expression (rather long, but of the form f+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifg, where f,g are rational functions) into the code, but right now it still resorts to the Solve function when the denominator of the expression vanishes. The relevant discriminant here that needs to be a perfect square is

(a²-i²)(b²-j²)[(p-u)² + (q-v)² - (i-j)²]

but I haven't thought too much about why that is.

Perhaps I should try to contact Jock and ask for a bound on the triangle. If it's big, I'd probably need to rewrite the program in C for speed.

Title: Re: Non-integer colouring
Post by SMQ on Jul 31^st, 2007, 7:47pm

on 07/31/07 at 14:42:21, Eigenray wrote:

Could you post that expression? I have a C++ program already for generating Pythagorean triples and checking for the appropriate triangles, but I don't have access to Mathematica (not worth the price tag just for solving riddles... ;)), and working it through by hand is a bit, shall we say, daunting...

--SMQ

Title: Re: Non-integer colouring
Post by Eigenray on Jul 31^st, 2007, 9:20pm

on 07/31/07 at 19:47:47, SMQ wrote:

Could you post that expression?

I'm sorry to say I've never discovered how to copy formulas out of Mathematica in a readable way. I just want the sequence of characters I would type to get it! I tried copy as plain text, formated text, text, mathml, CForm, FortranForm, TexForm, and sed'ing, but I think it's easier to just attach the picture. It should probably be simplified by hand some more too (Mathematica can be kinda dumb sometimes).

SOLVE[u,v,p,q,i,j] finds (x,y) as described when ip \neq ju (this condition seems to be sufficient, but no guarantees). The second solution, SOLVE[...][2], is the same as the first except changing the sign of the radicals in x,y.

If j=ip/u, then use the second formula. Again, the second solution is the same except for the sign of the radical (note that the y value remains unchanged).

I've never needed to, but if j=ip/u, and |i|=|u|, then you can use the third one (apparently the second solution is independent of the sign of i, which doesn't seem quite right, but I guess it doesn't matter if the (x,y) it finds isn't the one you were looking for).

Quote:

but I don't have access to Mathematica (not worth the price tag just for solving riddles... ;))

Does anyone buy it with real (i.e., not grant or corporate) money? I always use it to play around with stuff because it's so high level, but I've noticed from Project Euler that it's not uncommon for an equivalent C program to be 100 times faster. (But then, I've learned it through trial and error so I don't really know how to do things efficiently with it.)

Title: Re: Non-integer colouring
Post by Barukh on Aug 1^st, 2007, 3:57am

Isn't there an easier way to solve this system of DEs?

Maybe, Dave Rusin knows? ;)

Title: Re: Non-integer colouring
Post by SMQ on Aug 1^st, 2007, 8:41am

Assuming my program is working, after eliminating all 2526 candidates with a _{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif} b < c, b _{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif} 578, the triple/triangle a = 197 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif(28²+195²), b = 579 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif(285²+504²), c = 676 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif((504-28)²+(285+195)²) appears to be a solution! :o

(I'm certain that the program is finding all candidate triangles with a _{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif} b < c, b _{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif} N, and that the points (x,y) it's finding truely are an integer distance from all of (0,0), (u,v) and (p,q). I'm less certain that it didn't miss an (x,y) for the apparent solution.)

--SMQ

Title: Re: Non-integer colouring
Post by Barukh on Aug 1^st, 2007, 9:53am

:o :o :o!

Awesome, SMQ!

Did you use the formulas in the last row of Eigenray's post?

Title: Re: Non-integer colouring
Post by SMQ on Aug 1^st, 2007, 11:07am

I'm afraid it may be a false positive. :(

It looks like the denominator of the "big" equations can also go to 0 when iq = jv, and if those cases were ever to generate the only disqualifying point(s) for a candidate triangle, my program would erroneously flag it as a solution...

Eigenray, do you have/can you generate formulas for iq = jv (and presumably for iq = jv with |i| = |v|)?

Thanks.

on 07/31/07 at 21:20:09, Eigenray wrote:

I'm sorry to say I've never discovered how to copy formulas out of Mathematica in a readable way.

My Mathematica skills are more-than-a-bit rusty, but if memory serves, if you run the kernel directly, and not through the workbook frontend, do you still get a text-based interface?

--SMQ

Title: Re: Non-integer colouring
Post by Eigenray on Aug 1^st, 2007, 4:42pm

on 08/01/07 at 08:41:13, SMQ wrote:

Sorry, but SOLVE[195, 28, -285, 504, -197, 205] gives me the solution {-26520, -3808}. And the denominator is 37581796560, not zero.

on 08/01/07 at 11:07:25, SMQ wrote:

It looks like the denominator of the "big" equations can also go to 0 when iq = jv,

Substituting j=iq/v into the big equation, the only thing in the denominator that could possibly be 0 is v²-i². Setting i=v, j=q, I get

X = [q u^2 - p^2 v]/[2(qu-pv)],
Y = [(pu(p-u))^2 - (q u^2 - p^2 v)^2] / [4pu(p-u)(qu-pv)],

and the same result when i=-v, j=-q.

Quote:

My Mathematica skills are more-than-a-bit rusty, but if memory serves, if you run the kernel directly, and not through the workbook frontend, do you still get a text-based interface?

Yes, with ascii-art output. So all the exponents appear a row above, and yabb eats half the spaces, so you can't tell what goes with what. I'm sure there's a way to turn that off though. Or I could do it in Maple. Copying from there, the last formula shows up as
{x = 1/2*(u^2*q-v*p^2)/(u*q-v*p), y = 1/4*(u^2*q-p*u^2-v*p^2+p^2*u)*(u^2*q+p*u^2-p^2*u-v*p^2) / (u*p*(u-p)*(u*q-v*p))}.

Title: Re: Non-integer colouring
Post by SMQ on Aug 1^st, 2007, 7:40pm

on 08/01/07 at 16:42:26, Eigenray wrote:

Sorry, but SOLVE[195, 28, -285, 504, -197, 205] gives me the solution {-26520, -3808}.

Hmm, there must be a memory issue or something with my prog. If I run just that set it finds it no problem, but if I let it run all the way up to it it's missed... strange.

--SMQ

Title: Re: Non-integer colouring
Post by SMQ on Aug 2^nd, 2007, 9:06am

Fixed my program. In the last half-hour it's now searched all http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/a.gif _{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif} http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/b.gif < http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/c.gif for http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/b.gif to well-over 8000 without finding any solutions. What's more, the average per-candidate-triangle time to find a single disqualifying point seems to be getting smaller as the size of the triangles considered grows, perhaps because the number of Pythagorean triples with a given hypotenuse trends generally upward with larger hypotenuses.

If a solution exists, it doesn't look like a computer search is likely to find it. On the one hand, that's reasonably to be expected of a "hard" problem around here. On the other hand, given the apparent ease with which a computer search can disqualify every candidate, I think it's more likely that JocK was either misinformed or mistaken...

(edit: a faster version has now checked all http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/b.gif < somewhat over 21000 with similar results, and is still going steadily along...)

(edit 2: just past 33,000 before running out of memory, with no solution and no change in average behavior.)

--SMQ

Title: Re: Non-integer colouring
Post by Eigenray on Aug 3^rd, 2007, 4:05pm

I received an email from JocK that (a,b,c)=[hide](505, 1803, 2066)[/hide] works! My program has confirmed this, with the points (0,0), [hide](377, 336) and (-1653, 720)[/hide]. What does your program give?

Edit: Googling for that triplet turns up [link=http://arxiv.org/pdf/math/0511705]this[/link].

Title: Re: Non-integer colouring
Post by Barukh on Aug 4^th, 2007, 3:43am

on 08/03/07 at 16:05:46, Eigenray wrote:

Edit: Googling for that triplet turns up [link=http://arxiv.org/pdf/math/0511705]this[/link].

Well, now we know that what JocK asked for, is called an Erdos-Diophantine triangle.

The paper treats exactly that problem in section 2.2. Note that they don't describe the way they solve the 2 hyperbolas intersection system.

It is probably not a bad idea to ask the authors? ???

Title: Re: Non-integer colouring
Post by JocK on Aug 4^th, 2007, 6:23am

Hi folks, long time no see...

Nice to see some of the problems I posted here still keep some of you busy! :)

http://en.wikipedia.org/wiki/Erd%C5%91s-Diophantine_Graph

Busy with some other projects, but might be visiting this forum again in the near future.

Cheers,

JocK

Title: Re: Non-integer colouring
Post by Barukh on Aug 4^th, 2007, 6:53am

on 08/04/07 at 06:23:36, JocK wrote:

Busy with some other projects, but might be visiting this forum again in the near future. Cheers,

JocK

Please come! We really miss you here! :)

Title: Re: Non-integer colouring
Post by SMQ on Aug 4^th, 2007, 9:11am

on 08/03/07 at 16:05:46, Eigenray wrote:

What does your program give?

If you must know, my program gives (210123, -91523) as a disqualifying point, which is clearly a load of hooey as it's not even Pythagorean. I swear, one of these days I'm going to learn to program a computer. :-[

Once I fixed my program -- the problem was in checking for perfect squares in numbers > 32-bits -- it now reports that as a solution.

--SMQ

Title: Re: Non-integer colouring
Post by Eigenray on Aug 4^th, 2007, 11:26pm

on 08/04/07 at 03:43:48, Barukh wrote:

The paper treats exactly that problem in section 2.2. Note that they don't describe the way they solve the 2 hyperbolas intersection system.

It is probably not a bad idea to ask the authors?

This isn't too bad, just a bit tedious. Squaring

|(x,y)| - i = |(x-u,y-v)|
|(x,y)| - j = |(x-p,y-q)|

we get

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{x²+y²} = [2(ux + vy) + i² - a²]/(2i)
= [2(px + qy) + j² - b²)/(2j),

so if iq http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gifjv, then

y = 1/[2(iq-jv)] [ i(b²-j²) - j(a²-i²) +2(ju - ip)x ],

and substituting this back gives a quadratic in x. And if iq=jv, then ip http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gifju (or else (p,q) and (u,v) would be collinear), and we can solve for x in terms of y.

Title: Re: Non-integer colouring
Post by SMQ on Aug 6^th, 2007, 8:01am

Eigenray, can you confirm that (0,0), (1204, 1653), (3360, -2907) with sides of 2045, 4443 and 5044 is a solution? My now-apparently-working program returns this as the first solution with a side > 5000 (and therefore not given in the above paper).

Thanks.

Edit: the next few triangles appear to be (0, 0), (44, 240), (-240, -4797) with sides 244, 4803 and 5045 and (0, 0), (407, 624), (4437, -2640) with sides 745, 5163 and 5186. The first "new" triangle found by my program (the one having the least middle side) was (0, 0), (228, 3245), (-3120, -2035) with sides 3253, 3725 and 6252, found in only about 10 minutes on a Pentuim 4.

--SMQ

Title: Re: Non-integer colouring
Post by Eigenray on Aug 6^th, 2007, 9:07am

Yes, I can confirm those four triangles.