Life In 19x19
http://www.lifein19x19.com/

math problem (easy), algo problem (dunno if easy)
http://www.lifein19x19.com/viewtopic.php?f=8&t=12093		 Page 1 of 2
Author:  perceval [ Sat Jul 25, 2015 5:56 am ]
Post subject:  math problem (easy), algo problem (dunno if easy)
I couldnt sleep last night, and a question poped into my head:

Can you place 3 stones on a goban ( on goban intersections of course) so that the resulting triangle is equilateral ? (Lets assume the goban is infinite); Either give an example or a proof its impossible

When a question like that pops up i can only go to sleep after i solved it, so now i thought i would spread the joy.


Now the algo part:
Given a triangle with sides of length a, b and c, lets call the quantity E(a,b,c)= ((a-b)2+(a-c)2+(b-c)2)/(abc)2/3 the equilateralness of the triangle. E(a,a,a)= 0 in the case of an equilateral triangle.

Question: given a goban of size NxN, find an efficient algorithm to find the triangle with summits on the goban intersection minimizing E );

The obvious algo tries all triangles in complexity O(N6), can you find better ? for now i have nothing, i wonder if there is a smart way of enhancing a starting triangle
Author:  RBerenguel [ Sat Jul 25, 2015 6:09 am ]
Post subject:  Re: math problem (easy), algo problem (dunno if easy)
Equivalent: are there equilateral triangles in \mathbb{Z}^2?

Since I'm a mathematician and thus, lazy: http://math.stackexchange.com/questions ... ice-points
Author:  HermanHiddema [ Sat Jul 25, 2015 6:26 am ]
Post subject:  Re: math problem (easy), algo problem (dunno if easy)
perceval wrote:
Now the algo part:
Given a triangle with sides of length a, b and c, lets call the quantity E(a,b,c)= ((a-b)2+(a-c)2+(b-c)2)/(abc)2/3 the equilateralness of the triangle. E(a,a,a)= 0 in the case of an equilateral triangle.

Question: given a goban of size NxN, find an efficient algorithm to find the triangle with summits on the goban intersection minimizing E );

The obvious algo tries all triangles in complexity O(N6), can you find better ? for now i have nothing, i wonder if there is a smart way of enhancing a starting triangle


It seem to me that, given a line segment a-b, there is no need to try every other possible point as a third point, as it is easy to find the point closest to the third point of an exact equilateral triangle containing a-b (there are two, but there equilateralness is identical by symmetry) so then the algorithm would be O(n4). Note that it is possible the third point is not inside the NxN part of the grid, but in that case we can ignore it, as there will always be better triangles (not containing a-b) inside the grid
Author:  gowan [ Sat Jul 25, 2015 7:53 am ]
Post subject:  Re: math problem (easy), algo problem (dunno if easy)
RBerenguel wrote:
Equivalent: are there equilateral triangles in \mathbb{Z}^2?

Since I'm a mathematician and thus, lazy: http://math.stackexchange.com/questions ... ice-points


The original poster specified equi-distance intersections on a goban. On my go boards the grid is not made up of square cells, rather rectangular cells. That makes the question not equivalent to finding equilateral triangles in the integer lattice.

It seems that the observation that tan(pi/3) is not rational would solve the problem on a non-square lattice with vertices at rational points.
Author:  DrStraw [ Sat Jul 25, 2015 8:00 am ]
Post subject:  Re: math problem (easy), algo problem (dunno if easy)
Well, it is certainly impossible if one side is parallel to the edge of the board because the height to base ratio is irrational, and that is not possible on a go board. There may be a way such that no side is parallel to the edge but that would require more thought. I suspect the answer is that it is not possible.
Author:  RBerenguel [ Sat Jul 25, 2015 8:15 am ]
Post subject:  Re: math problem (easy), algo problem (dunno if easy)
gowan wrote:
RBerenguel wrote:
Equivalent: are there equilateral triangles in \mathbb{Z}^2?

Since I'm a mathematician and thus, lazy: http://math.stackexchange.com/questions ... ice-points


The original poster specified equi-distance intersections on a goban. On my go boards the grid is not made up of square cells, rather rectangular cells. That makes the question not equivalent to finding equilateral triangles in the integer lattice.

It seems that the observation that tan(pi/3) is not rational would solve the problem on a non-square lattice with vertices at rational points.


Yes, forgot there is a small difference making it non-squarish. It's probably equivalent, though, but would need more thought to prove it.
Author:  HermanHiddema [ Sat Jul 25, 2015 9:31 am ]
Post subject:  Re: math problem (easy), algo problem (dunno if easy)
HermanHiddema wrote:
perceval wrote:
Now the algo part:
Given a triangle with sides of length a, b and c, lets call the quantity E(a,b,c)= ((a-b)2+(a-c)2+(b-c)2)/(abc)2/3 the equilateralness of the triangle. E(a,a,a)= 0 in the case of an equilateral triangle.

Question: given a goban of size NxN, find an efficient algorithm to find the triangle with summits on the goban intersection minimizing E );

The obvious algo tries all triangles in complexity O(N6), can you find better ? for now i have nothing, i wonder if there is a smart way of enhancing a starting triangle


It seem to me that, given a line segment a-b, there is no need to try every other possible point as a third point, as it is easy to find the point closest to the third point of an exact equilateral triangle containing a-b (there are two, but there equilateralness is identical by symmetry) so then the algorithm would be O(n4). Note that it is possible the third point is not inside the NxN part of the grid, but in that case we can ignore it, as there will always be better triangles (not containing a-b) inside the grid


Ok, some further thought on the algorithm!

First off, it is easy to see that any such triangle can always be translated so that one of it's corners is exactly in the corner. Second, given the geometry of the triangle, it is easy to see that at least one of the sides originating from that corner will be no further than 15° from the edge. So I would say: take point 1 as the corner, then for any point 2 that is within a wedge 15° wide from the edge, calculate the third point. So only point 2 varies, and only within a small subset of the whole board (less than 14%) giving a complexity of O(n2)
Author:  DrStraw [ Sat Jul 25, 2015 10:55 am ]
Post subject:  Re: math problem (easy), algo problem (dunno if easy)
DrStraw wrote:
Well, it is certainly impossible if one side is parallel to the edge of the board because the height to base ratio is irrational, and that is not possible on a go board. There may be a way such that no side is parallel to the edge but that would require more thought. I suspect the answer is that it is not possible.


This was an interesting exercise as I was mowing the lawn.

Okay, so extending this idea. As was pointed out, we can assume one vertex is the lower left corner and place another at the x-y point. However, in terms of rectangular coordinates the point will be (x,ky) where k is the stretch factor. From the definition of the size of the board we know that k must be a rational number.

Now set the angle between the edge and the side of the triangle to be A. The polar coordinates of this point are (rcosA, rsinA), where r^2 = x^2 + (ky)^2

To find the other vertex we rotate this through 60 degrees and the new point is (rcos(A+60) , rsin(A+60). These coordinates must be a point on the board and so must also be (m,kn) for some integers m and n. So:

rcos(A+60) = rcosA.cos60 - rsinA.sin60 = rcosA . 1/2 - rsinA . sqrt(3)/2 = x/2 - sqrt(3).ky/2

We now have
x/2 - sqrt(3).ky/2 = m
2(x-2m)/ky = sqrt(3)
x,y and m are inetegers and k is rational so we have expresses sqrt(3) as a rational number. This is a contradition, so m cannot be an integer. Likewise for n.

So as long as the stretch ratio between the sides is rational the equilateral triangle cannot exist.
Author:  Knotwilg [ Sat Jul 25, 2015 12:56 pm ]
Post subject:  Re: math problem (easy), algo problem (dunno if easy)
DrStraw wrote:
From the definition of the size of the board we know that k must be a rational number.


Really? Why would two arbitrary measurements have a rational fraction? Is Q complete after all?
Author:  RBerenguel [ Sat Jul 25, 2015 1:14 pm ]
Post subject:  Re: math problem (easy), algo problem (dunno if easy)
Knotwilg wrote:
DrStraw wrote:
From the definition of the size of the board we know that k must be a rational number.


Really? Why would two arbitrary measurements have a rational fraction? Is Q complete after all?


In the real-world measuring-world there are no irrationals in a ruler, since you can only measure up to a certain precision
Author:  DrStraw [ Sat Jul 25, 2015 1:21 pm ]
Post subject:  Re: math problem (easy), algo problem (dunno if easy)
Knotwilg wrote:
DrStraw wrote:
From the definition of the size of the board we know that k must be a rational number.


Really? Why would two arbitrary measurements have a rational fraction? Is Q complete after all?


I don't recall the exact dimensions, which is why I did not quote them, but the official board size has specific dimensions which are expressed in units which satisfy this condition.

EDIT: http://senseis.xmp.net/?EquipmentDimensions shows that the ratio between the sides should be 15/14, so this would be the value of k.
Author:  DrStraw [ Sat Jul 25, 2015 1:23 pm ]
Post subject:  Re: math problem (easy), algo problem (dunno if easy)
RBerenguel wrote:
Knotwilg wrote:
DrStraw wrote:
From the definition of the size of the board we know that k must be a rational number.


Really? Why would two arbitrary measurements have a rational fraction? Is Q complete after all?


In the real-world measuring-world there are no irrationals in a ruler, since you can only measure up to a certain precision


This is not really a valid argument because if we apply it to our equilateral triangle then we no longer have irrational length sides and so my proof is invalid.
Author:  Mike Novack [ Sat Jul 25, 2015 2:26 pm ]
Post subject:  Re: math problem (easy), algo problem (dunno if easy)
I must be missing something about this discussion of irrational side length.

a) Besides "rulers" or any other kind of physical measurement having no place in the realm of mathematics, there would be no need to measure the length of the sides of the triangle. Can simply calculate based upon the intersections and the grid dimensions.

b) Why not irrational side lengths? For the moment, assume that the grid is unit size squares (the argument isn't going to change if rectangular).

1) Consider the line segment beginning at a1 and ending at d3. It's length would be rational, 5 (over four, up three, would be a 3:4:5 triangle)
2) Consider the line segment beginning at a1 and ending at b2. It's length would be the irrational, square root of 2.

Remember folks, nothing about this problem specified that any side of this triangle had to be parallel to an edge of the goban.
Author:  Knotwilg [ Sat Jul 25, 2015 3:06 pm ]
Post subject:  Re: math problem (easy), algo problem (dunno if easy)
RBerenguel wrote:
Knotwilg wrote:
DrStraw wrote:
From the definition of the size of the board we know that k must be a rational number.


Really? Why would two arbitrary measurements have a rational fraction? Is Q complete after all?


In the real-world measuring-world there are no irrationals in a ruler, since you can only measure up to a certain precision


In the real-world measuring-world you don't know whether a certain fraction is rational or irrational.
Author:  phillip1882 [ Sat Jul 25, 2015 3:12 pm ]
Post subject:  Re: math problem (easy), algo problem (dunno if easy)
consider the following pic. for there to be an equilateral triangle, the 3rd point can only possibly be in one of six places to make two sides equal.
either down 4 more and either left or right 2, or right or left four and up or down two. all of these fail. in general, you will always have the third side the wrong length. though i don't see an efficient way to prove it.

Attachments:
gotriangle.png
gotriangle.png [ 3.94 KiB | Viewed 10386 times ]
Author:  DrStraw [ Sat Jul 25, 2015 3:31 pm ]
Post subject:  Re: math problem (easy), algo problem (dunno if easy)
phillip1882 wrote:
consider the following pic. for there to be an equilateral triangle, the 3rd point can only possibly be in one of six places to make two sides equal.
either down 4 more and either left or right 2, or right or left four and up or down two. all of these fail. in general, you will always have the third side the wrong length. though i don't see an efficient way to prove it.


I just did prove it, in my post above. Also, there are only two other places the third point can be.
Author:  perceval [ Sun Jul 26, 2015 2:22 am ]
Post subject:  Re: math problem (easy), algo problem (dunno if easy)
Funny how the discussion went in places i did not think about.
My question was, indeed, about integer coordinates, I just put in on a goban because its the thing to do here to interest peoples.
my proof was close the one in the link by RBerenguel, ie using only pythagore theorem and arriving to contradictions on the prime decomposition of a square

indeed the rotation idea is nice because it extends naturally to the rational case

For the algo proposed by HermanHiddema,

You can reduce the complexity to just N2 by picking A on the bottom edge, and B on the right edge.
ie A=(0,N-X) B=(N,Y)with X>Y (by symmetry). in that case if the 3rd point of the equilateral trinagle doenst fit on the goban, it wont fit for any translation of the base vector
you can also reduce to the case where , gcd(N-X,Y)=1,( the fixed edge is not reducible) but this doesnt reduce the O(N2) complexity

but there is a small issue
this probably works, but you have no guarantee that the integer point closest to the minimum is the on grid minimum as the derivative of E is not isotrope;
ie if we fix A(N-X,0) and B (N,Y) and let C(N-x,y) vary:

with a= sqrt(X2+Y2)
b(x,y) =sqrt((X-x)2+y2)
c(x,y)=sqrt((x)2+(y-Y)2)

E(x,y)=(a-b(x,y))2+(a-c(x,y))2+(b(x,y)-c(x,y))2/(ab(x,y)c(x,y))2/3

min E(x,y) is obtained for xmin=(N-X)+X/2-sqrt(3)Y/2,ymin=sqrt(3)X/2+Y/2

and we want the min of E with x,y integer and 0<x<N,0<y<N.

Its not clear in general that the minimum on this set is the closest point to (xmin,ymin).

If the point is in the goban, you need to check the 4 closest points (can we prove its enough ?)
If (xmin, ymin) is outside the goban, its enough to check 2 points on the edge of the goban, so complexity can stay at N2, but we would need to prove that the function have only 1 single min on the edge. (probably true)
Author:  DrStraw [ Sun Jul 26, 2015 3:45 am ]
Post subject:  Re: math problem (easy), algo problem (dunno if easy)
All very nice, Perceval, but it sounds a bit like using a slegehammer to crack a peanut. Good mathematics is simple and elegant. This sounds complex and inelegant as compared to the polar coordinates solution.
Author:  perceval [ Sun Jul 26, 2015 6:34 am ]
Post subject:  Re: math problem (easy), algo problem (dunno if easy)
DrStraw wrote:
All very nice, Perceval, but it sounds a bit like using a slegehammer to crack a peanut. Good mathematics is simple and elegant. This sounds complex and inelegant as compared to the polar coordinates solution.


Agreed, the short proof is the way to go.

The other part is an algorithm, its always much uglier than nice proof. But it answers a slightly different question: what is the closest thing you can get to an equilateral triangle, after proving you can't have a real one ? There is a different kind of beauty in shaving powers of N in an algorithm complexity. Or maybe not a beauty but a cleverness
Author:  DrStraw [ Sun Jul 26, 2015 8:49 am ]
Post subject:  Re: math problem (easy), algo problem (dunno if easy)
perceval wrote:
DrStraw wrote:
All very nice, Perceval, but it sounds a bit like using a slegehammer to crack a peanut. Good mathematics is simple and elegant. This sounds complex and inelegant as compared to the polar coordinates solution.


Agreed, the short proof is the way to go.

The other part is an algorithm, its always much uglier than nice proof. But it answers a slightly different question: what is the closest thing you can get to an equilateral triangle, after proving you can't have a real one ? There is a different kind of beauty in shaving powers of N in an algorithm complexity. Or maybe not a beauty but a cleverness


I am not really big on algorithms, even though I made a living using them in the IT world before I retired. I even wrote a PhD thesis about using them in algebra almost 40 years ago. But I still don't think the four color problem has been proved. Is has merely been shown to be true.
Page 1 of 2 All times are UTC - 8 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/