Square In A Haystack

Geometry Level 2

The above shows a part of an infinitely large equilateral triangular grid. The four purple lattice points form a rectangle.

Is it possible to form a square by connecting some four lattice points on the grid?

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

5 solutions

Calvin Lin Staff
Apr 20, 2016

The lattice points of this triangular grid can be represented by integer pairs ( a , b ) (a,b) , where the distance between ( a , b ) (a,b) and ( c , d ) (c,d) by cosine rule is

( a c ) 2 + ( b d ) 2 2 ( a c ) ( b d ) cos 6 0 = ( a c ) 2 + ( b d ) 2 ( a c ) ( b d ) . (a-c)^2 + (b-d)^2 - 2 (a-c)(b-d) \cos 60^\circ = (a-c)^2 + (b-d)^2 - (a-c)(b-d).

To show that we cannot find 4 points which form a square, we will show that there does not exist 3 distinct points X = ( a , b ) , Y = ( c , d ) , Z = ( e , f ) X = (a,b), Y = (c,d), Z = (e,f) such that X Y = Y Z |XY| = |YZ| and X Y Y Z XY \perp YZ .

Proof by contradiction. Suppose not, then by comparing lengths X Y |XY| and X Z |XZ| , we have
2 = X Z X Y = ( a e ) 2 + ( b f ) 2 ( a e ) ( b f ) ( a c ) 2 + ( b d ) 2 ( a c ) ( b d ) \sqrt{2} = \frac{ |XZ| } {|XY| } = \frac{ (a-e)^2 + (b-f)^2 - (a-e)(b-f) } { (a-c)^2 + (b-d)^2 - (a-c)(b-d)} Since these points are distinct, notice that the numerator and denominator on the right-hand side are non-zero. Also, since a , b , c , d , e a, b, c, d, e and f f are integers, thus the numerator and denominator are integers. Hence, we have a representation of 2 \sqrt{2} as a rational numbers. This contradicts the fact that 2 \sqrt{2} is irrational .

Sir, how did you get √2 ?

Vishal Yadav - 5 years, 1 month ago

Log in to reply

If X Y Z W XYZW is a square with X Y Y Z XY \perp YZ , what is the ratio of X Z X Y \frac{ |XZ| } { |XY|} ? This is the ratio of the diagonal to the side of the square.

Calvin Lin Staff - 5 years, 1 month ago
展豪 張
Apr 24, 2016

For any two lattice points on this grid, a third point which forms equilateral triangle with these two points is also a lattice point. (The proof of this should be easy so I am not showing it)
Now suppose there are squares of lattice points on this plane.
Pick the smallest one.
However, we can construct a smaller one base on this square:

which leads to a contradiction to the 'smallest' assumption.
So there does not exist squares of lattice points on this plane.

Very nice infinite descent argument!

As a side note, you should explain why there exists a "smallest square". For example, if there were squares of side length n + 1 n \frac{n+1}{n} , then there is no "smallest square" in this sequence.

Calvin Lin Staff - 5 years, 1 month ago

Log in to reply

Thank you! Actually I am not familiar with this part so I skipped it and pretend that nobody will notice...
Anyway, I will try to prove it:

Define two unit vectors i ^ , j ^ \hat i, \hat j which are 6 0 60^{\circ} apart (instead of 9 0 90^{\circ} in usual).
Position of lattice points on the plane can be denoted as x i ^ + y j ^ x\hat i+y\hat j where x , y Z x,y \in \mathbb Z when one of the lattice point is picked as origin and the plane is oriented appropriately.
Let A = a i ^ + b j ^ , B = c i ^ + d j ^ A=a\hat i+b\hat j,B=c\hat i+d\hat j ( a , b , c , d Z a,b,c,d \in \mathbb Z ) be two lattice points on the plane.
A B 2 = A B A B = ( ( c a ) i ^ + ( d b ) j ^ ) ( ( c a ) i ^ + ( d b ) j ^ ) = ( c a ) 2 + ( d b ) 2 + 2 ( c a ) ( d b ) i ^ j ^ = ( c a ) 2 + ( d b ) 2 + 2 ( c a ) ( d b ) cos 6 0 angle between i ^ and j ^ is 6 0 = ( c a ) 2 + ( d b ) 2 + ( c a ) ( d b ) \begin{aligned}\vert AB \vert ^2 &= \vec{AB}\cdot\vec{AB} \\&= ((c-a)\hat i+(d-b)\hat j)\cdot((c-a)\hat i+(d-b)\hat j) \\&= (c-a)^2+(d-b)^2 +2(c-a)(d-b)\hat i\cdot\hat j \\&=(c-a)^2+(d-b)^2+2(c-a)(d-b)\cos 60^\circ & \text{angle between }\hat i\text{ and }\hat j\text{ is }60^\circ \\&= (c-a)^2+(d-b)^2+(c-a)(d-b)\end{aligned}
which is an integer.
Integer is well-ordered, and squaring preserves ordering.
Therefore, the length of sides are also well-ordered.
Thus we can find a smallest square.

展豪 張 - 5 years, 1 month ago

Log in to reply

Great! That's one way of doing it.

Another possibility is to calculate the ratio of the lengths of the squares that we generated as r < 1 r < 1 , which is a fixed ratio regardless of the original square's side length. From which, it follows from the existence assumption, there is a square of side length r n L r^n L for all n n , which eventually gets too small. Hence, contradiction.

This works because we have constant scaling, as opposed to the { n + 1 n } \{ \frac{n+1}{n} \} example that I gave above.

Calvin Lin Staff - 5 years, 1 month ago

Log in to reply

@Calvin Lin Yours approach is much more concise than mine! Thanks for teaching me this approach. =D

展豪 張 - 5 years, 1 month ago
Akash Saha
Apr 14, 2016

Let the sides of the equilateral triangle be a a .

Now Consider 2 axes mutually perpendicular to each other because the angle contained by the sides of a square is 90°

Let one axis be along the sides of the triangles(X axis), while the other be along the height of the equilateral triangles(Y axis)

To go from one lattice point to other on the X axis, we must go in multiples of a a

Therefore, one side of the square is n . a n.a for integral n n .

Similarly, to move from one lattice point to the other on the Y axis, we must go in multiples of 3 a \sqrt{3}a

Therefore, another side of the square is m . 3 a m.\sqrt {3}a for integral m m .

But the sides of a square are equal, which implies m . 3 . a = n . a m.\sqrt{3}.a = n.a

Therefore n m \frac{n}{m} = 3 \sqrt{3} .

But n n and m m are integral and thus LHS is rational, however RHS is irrational.

Hence, it is impossible to embed a square on this lattice.

P.S. : For those wondering why to take two integers m m and n n , consider a rectangle with dimensions 2x3 You totally need 6 rectangles to form a square(6x6).

Good analysis! Why must we have "let one axis be along the sides of the triangle"?

Why isn't it possible to have a square where no edge is along a lattice gridline?

E.g. In the rectangular grid that we're used to, ( 1 , 0 ) , ( 2 , 1 ) , ( 1 , 3 ) , ( 0 , 1 ) (1,0), (2, 1), (1, 3), (0,1) form a square where no edge is along a gridline.

Calvin Lin Staff - 5 years, 2 months ago

Log in to reply

Very true. Did not think about that.

Akash Saha - 5 years, 2 months ago

To attach a picture, click "Edit" (your solution), then click this button

Pi Han Goh - 5 years, 2 months ago

Log in to reply

I am using the app, which I think currently doesn't support an attachment. Maybe I'll post the picture tomorrow from PC. Thanks anyways. :)

Akash Saha - 5 years, 2 months ago

Log in to reply

No problem! Looking forward to your pictures! =D

Pi Han Goh - 5 years, 2 months ago
Nowras Otmen
Apr 13, 2016

Let l l be the side of the triangle. We know that its area is A = l 2 3 4 A=\dfrac{l^2\sqrt{3}}{4} . For any two points we choose, we can determine the square's side. Letting n n be the amount of triangles between the two chosen points, n l nl will be the square's side, with n Z n \in \mathbb{Z} . If it were possible to form a square choosing any four points among the vertices, we would have that m A = n 2 l 2 mA=n^2l^2 , where n 2 l 2 n^2l^2 is the area of the square and m m represents the amount of triangles inside the square and has to be, necessarily, an integer.

m l 2 3 4 = n 2 l 2 m\dfrac{l^2\sqrt{3}}{4}=n^2l^2

m = n 2 4 3 3 m=\dfrac{n^2 4\sqrt{3}}{3}

We can clearly see that m m isn't an integer and, therefore, a whole number of triangles can't fill the square.

Why must there be an integer number of triangles between any two chosen points?

IE What is the n n corresponding to these 2 points?

Calvin Lin Staff - 5 years, 2 months ago

Log in to reply

Good point, n n wouldn't be an integer in that case and in many other cases. My attempt at the problem was too simplistic, I'll keep trying.

Nowras Otmen - 5 years, 2 months ago

Log in to reply

You are not too far off from the actual proof. Find a way to express these points in the lattice grid, in order to calcualte the lengths and angles.

Calvin Lin Staff - 5 years, 2 months ago
Atul Shivam
Apr 12, 2016

It is not possible to form any square by taking any four points, it will lead to the formation of quadrilateral whose two adjacant angle will be ( 60 ° 60° and 120 ° 120° ) or 90 ° 90° , and the resulting quadrilateral formed will be either ( r h o m b u s (rhombus or p a r a l l e l o g r a m parallelogram or t r a p e z i u m trapezium ) or r e c t a n g l e rectangle

for further clarification you may ask any questions

Moderator note:

This solution is merely an assertion. It doesn't constitute a proof that we cannot obtain a square. In particular, since squares are also rectangles, it is not clear why we cannot get a square.

Got a proof?

Pi Han Goh - 5 years, 2 months ago

Log in to reply

You mean mathematical proof?

Atul Shivam - 5 years, 2 months ago

Why must the 4 points be "close" together? They could be any 4 points on the entire lattice grid.

It's not too hard to find 3 points that give a right angle. For example, these 4 points give us a rectangle:

.

Note also that since squares are rhombuses, you have not ruled out being able to find a square.

Calvin Lin Staff - 5 years, 2 months ago

Log in to reply

You have connected 4 points that forma right angle, but still it is not a square (all sides are not of same length)

Atul Shivam - 5 years, 2 months ago

Log in to reply

I did not say it is a square. I said:

For example, these 4 points give us a rectangle.

The point is that your statement of "it will lead to the formation of quadrilateral whose two adjacent angles will be 60 ° 60° and 120 ° 120° " is not true, because you are only considering "consecutive points in a line", instead of any 2 arbitraty points on the grid. (IE You only considered points that were "close together" and thought that we could only get those 2 angles)

Calvin Lin Staff - 5 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...