math problem (easy), algo problem (dunno if easy)

[perceval]

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)²+(a-c)²+(b-c)²)/(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(N⁶), can you find better ? for now i have nothing, i wonder if there is a smart way of enhancing a starting triangle

[RBerenguel]

Equivalent: are there equilateral triangles in \mathbb{Z}^2?

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

[HermanHiddema]

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)²+(a-c)²+(b-c)²)/(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(N⁶), 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(n⁴). 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

[gowan]

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.

[DrStraw]

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.

[RBerenguel]

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.

[HermanHiddema]

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)²+(a-c)²+(b-c)²)/(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(N⁶), 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(n⁴). 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(n²)

[DrStraw]

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.

[Knotwilg]

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?

[RBerenguel]

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

[DrStraw]

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.

[DrStraw]

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.

[Mike Novack]

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.

[Knotwilg]

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.

[phillip1882]

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.