There is a grid of equilateral triangles with a distance 1 between any two neighboring grid points. An equilateral triangle with side length n lies on the grid so that all of its vertices are grid points, and all of its sides match the grid. Now, let us decompose this equilateral triangle into n2 smaller triangles (not necessarily equilateral triangles) so that the vertices of all these smaller triangles are all grid points, and all these small triangles have equal areas. Prove that there are at least n equilateral triangles among these smaller triangles.
Problem
Source: 2016 Taiwan TST Round 2
Tags: combinatorial geometry, combinatorics
20.07.2016 16:58
Nice problem, which I'm told is also by Bobson. Solution with Ryan Alweiss: First, suppose there is some diagonal AB>√3 of maximal length in the dissection. Take C and D as shown in the figure. We claim that △ABC, △ADB are both in the dissection. For if △ABC is not, then some triangle △ABC′ is, with C′ on the same side as C. WLOG ray CC′ is in the same direction as ray AB. Then since ∠ABC<60∘, it follows that BC′>BA, contradicting the fact that AB was maximal. Similarly △ADB is present too; this proves the claim. [asy][asy] size(7cm); pair o = (0,0); pair y = dir(60); pair x = dir(0); filldraw(o--(2*x+y)--(x+y)--cycle, rgb(1,0.9,0.85), red); filldraw(o--(2*x+y)--(x)--cycle, rgb(1,0.9,0.85), red); draw(o--y--x--(x+y)--(2*x)--(2*x+y)); draw(o--(2*x)); draw(y--(2*x+y)); draw(x--(x+y), blue); pair C1 = -x; draw((x+y)--C1, dashed); draw((2*x+y)--C1--o, heavygreen); dot(y); dot(2*x); dot("A", o, dir(225)); dot("B", 2*x+y, dir(45)); dot("C", x+y, dir(45)); dot("D", x, dir(-45)); dot("C′", C1, dir(-90)); [/asy][/asy] Now consider the following process. Let AB>√3 and C, D as above. Then, replace △ABC and △ADB with △ACD and △BDC. As ∠CAD<60∘, we have 1<CD<AB, so this operation decreases the sum of perimeters in the dissection. By repeating this operation, we eventually arrive at a dissection which has no diagonals of length exceeding √3, and which contains the same number of unit equilateral triangles as before. Finally, in this case, color the original grid with alternating black and white; and we can WLOG assume there are n more black than white unit triangles. Each parallelogram with side length √3 pairs up a black and white triangle. Thus there must be at least n black triangles left in the grid, as desired.
20.07.2016 19:47
v_Enhance wrote: First, suppose there is some diagonal AB>√3 of maximal length in the dissection. Take C and D as shown in the figure. We claim that △ABC, △ADB are both in the dissection. Can you look at the following dissection, plz Note that I assume that middle point of the grid have coordinate (0,0) then consider A(−52,−√32),B(52,√32) and then let E(−1,0) we can have dissection △ABE,... , then that claim is wrong. I hope you understand what I want to say and sorry if I'm just stupid.
20.07.2016 19:51
I guess I wasn't clear what I meant by C and D. They are the two points whose projections lie in the interior of AB, and which have the shortest altitudes to AB. EDIT: Er, also, your triangle has area √3/2 instead of √3/4 if I'm not mistaken? Generally, by Pick's theorem (well, after an affine transform) one can see it's impossible to have a √3/4 triangle in the dissection with any points on its boundary (other than vertices).
20.07.2016 20:03
v_Enhance wrote: I guess I wasn't clear what I meant by C and D. They are the two points whose projections lie in the interior of AB, and which have the shortest altitudes to AB. EDIT: Er, also, your triangle has area √3/2 instead of √3/4 if I'm not mistaken? Generally, by Pick's theorem (well, after an affine transform) one can see it's impossible to have a √3/4 triangle in the dissection with any points on its boundary (other than vertices). OK, thanks I understand it now P.S. Oh sorry for mistaken about the area
03.04.2021 11:41
Solution with p_square, Arwen713 and MathPassionForever. Idea is similar to v_Enhance but posting for storage. We consider the longest edge in the tiling which is >√3 in length. Let it be AB. Now, it must be part of two triangles, one on either side of the edge. Now, we claim that on either side, only one point is eligible to be on the triangle. Proof: Assume that there are two such points C,D on same side of AB. Now, C and D are at the same height from AB, now CD∥AB. We also have that CD is of shorter length than AB as both lie between the lines through A and B perpendicular to AB as AB is the longest edge. But, then A+D−C or A+C−D is also a point on the edge AB. Thus, there is another lattice point on the segment AB but this is impossible as ABC has area 1 and Pick's theorem gives a contradiction. Thus, the claim follows. Now, let C be the point on one side of AB that works. Then the reflection C in midpoint of AB i.e. D=A+B−C also works. So, the two triangles ABC and ABD are in the current figure. We replace AB with CD and as AB>CD, we have that the perimeter of the figure decreases. Observe that this process does not change the number of equilateral triangles. We repeat this process untill all edges are either √3 in length or 1 in length. Now, observe that this means that the entire tiling is with parallelograms with long diagonal of length √3 and equilateral triangles. Now, in each of the 3 directions parallel to the sides of the equilateral triangle associate the vector (1,0,0), (0,1,0) and (0,0,1). Add this vector in case we move clockwise and subtract in case we move anti clockwise. Now, the sum over all clockwise triangles is (1,1,1), anti-clockwise triangles it is (−1,−1,−1) and for the entire figure it is (n,n,n) and for just a parallelogram it is (0,0,0). So, we get that the number of clockwise equilateral triangles-anti-clockwise equilateral triangles is n. Thus, there are atleast n equilateral triangles.
28.08.2022 18:14
Sketch because it's hard to explain in detail without drawings: The idea is to delete "nice parallelograms", which are 60-120, and prove that once we're done deleting, we only have equilateral triangles. Suppose we have some state where the "edges" of the remaining figure are all parallel to the grid lines, and we have some triangle that's not equilateral. WLOG let that triangle's length 1 side be horizontal, and define "slope" such that the grid lines have slope ±1, a side of length √3 has slope ±2 depending on orientation, etc., so that triangle has a side whose slope has absolute value at least two (and the other one is one closer to zero). We form a parallelogram, starting from that triangle, by noting that if some non-horizontal edge of our parallelogram with absolute value greater than one, then the triangle not in the parallelogram adjacent to that edge has to also have a horizontal side of length 1, forming a new edge whose slope differs from the previous by one (in either direction). Note that because of our overarching condition on the edges of the figure, we cannot indefinitely have edges whose absolute values are greater than one, so by discrete continuity at some point we'll have to hit ±1 on both sides (with the signs both being equal to the sign of the original edge), and we have our parallelogram. Color the original grid in a "checkerboard" pattern such that one corner of the equilateral triangle is black, and note that every nice parallelogram covers equal white and black areas. However, there are evidently n more black unit triangles than white ones, so we need at least n equilateral triangles to make up the difference.
27.11.2023 19:09
I found the bad solution!!!! Claim: Any triangle in a dissection only contains 3 lattice points at the vertices and not on the interior or boundary. Proof. Take an affine transform to a square grid, then apply Pick's theorem. ◼ Orient the triangle such that it points up. Call an equilateral grid triangle an up triangle if it points upward, else a down triangle. Note that in a grid, there are n more up triangles than down triangles. Call a triangle non-primitive if it is not an up or down triangle. Split the arguments of lines into 6 closed sections which go from 15k degrees to 15k+15 degrees. Claim: All non-primitive triangles with a length larger than √3 with arguments in the same section. Proof. This can be manually verified when a length of 1 or √3 appears by fixing that line and considering the locus of the third point. Else, suppose that all side lengths are larger than √3. If two lines are not in the same section, then it follows by their length that they have an interior point, contradiction. ◼ Claim: The non-primitive triangles cover an equal amount of up and down triangles. Proof. Allow us to mark triangles. We run the following algorithm till termination. Take any nonmarked nonprimitive triangle and add it to a set S. For each side length s with length more than √3 on the boundary of S, take the triangle which shares s and add it to S. Then, consider the boundary of S when out of sides. The border must be axis-aligned, and have arguments in the same section. However, it is then possible to tesselate S using √3×1 parallelograms, giving the result. ◼ As such, it follows that there are at least n up triangles covered by primitive triangles, as desired.
27.01.2024 05:49
Solved with Shreyasharma. Claim: There is at least one equilateral triangle in each row of the large equilateral triangle. Proof: We can show that all non-equilateral triangles can be fit into groups of distinct 60∘−120∘ parallelograms. Since these parallelograms have an even number of triangles in them, this implies that there must be at least one equilateral triangle in a row(because each row has an odd number of triangles.) \newline FTSOC, let us try to tile the grid using purely non-equilateral triangles. We can only go row-by-row, since the height of a non-equilateral triangle cannot be >√32. The largest edge of the first triangle we place must be shared with a congruent triangle(that is a reflection of the triangle over this edge.) The sides of the two congruent triangles(not parallel to the grid lines) must also be shared with two more non-equilateral triangles, unless the length of the new side is equal to 1. \newline Note that these two new non-equilateral triangles are both reflections over the original largest edge. We can continue this process, until the new sides are equal to 1. When the new sides are equal to 1 we are forced to add equilateral triangles, so our parallelogram is complete. This is enough, since there are n rows in the equilateral triangle, and one being in each row finishes. ◼
14.10.2024 14:53
This was a nice problem The main claim is the following: Claim Of all triangles in the partition, the maximum side length is ≤√3. Note that this gives each triangle is the half of a 60-120 in one of its two diagonals Proof This is hard to explain without diagrams and hence is not included though my solution is almost identical to v_Enhance and Rg230403 After this the finish is easy, color the grid in a "checkerboard" manner so that the top vertex is black. This gives that there are n more black triangles than white triangles, so if we delete all the 30-30-120 triangles, there should be atleast n equilateral triangles left inorder to make up with the area imbalance and that finishes
12.11.2024 06:59
Here's a funny buff: Let n be a positive integer. What is the fewest number of right isosceles triangles in any triangulation of an n×n square lattice grid?
12.11.2024 07:34
ihatemath123 wrote: Here's a funny buff: Let n be a positive integer. What is the fewest number of right isosceles triangles in any triangulation of an n×n square lattice grid?
12.11.2024 10:37
04.01.2025 06:45
Observe each triangle must have area at least √34, and the total area is √34n2, so each triangle must have area exactly √34. This means it is either an equilateral triangle with side length 1 or half of a parallelogram composed by two equilateral triangles, split along its longest diagonal. For the latter case, the triangle has a side with length √3, which must be part of an identical, flipped triangle - if the side is any shorter than √3, it does not cover two lattice points, and if it is any longer, as the other two sides are at least 1, applying Heron's formula forms a contradiction by area. Thus if we have a non-equilateral triangle, it must come in a pair that forms a parallelogram. Now, color the top triangle black, and alternate black and white between triangles that share a side. Observe parallelograms take both a black triangle and white triangle, while equilateral triangles can be either black or white. As there are n more black triangles than white triangles, there are at least n equilateral triangles.