Every diamond contains an upward and a downward triangle with a common edge. Now in every upward triangle $ T$ with sidelength $ k$ we have $ \frac{k^{2}+k}2$ upward triangles and $ \frac{k^{2}-k}2$ downward triangles. The downward triangles are adjacent only with upward triangles from $ T$, so if more than $ k$ upward triangles are removed, there are not enough of them to match with the downward ones. This proves the easier part of the problem. Now let's prove the converse by induction on $ n$. Call a sequence $ 2k+1$ of consecutive upward and downward triangles (starting and ending with upward triangles) from the same row a "block". The block above it of $ 2k-1$ triangles be called the "above block". We wish to cover all the triangles in the last row of the big triangle $ T$ with diamonds. There can be horizontal diamond, but there also can be vertical ones, and for them we will need to borrow upward triangles from the above row. When we finish, it is easy to conclude there will be $ n-1$ holes in the remaining triangle $ T'$ of side $ n-1$. We just need to pick up the diamonds in such a way that the induction hypothesis is respected. Call a triangle which contains a part of the base a "base" triangle. Call a triangle which contains as many holes as its sidelength "full", and one which contains more than its sidelength "deadly". We must not create "deadly" triangles after cutting the last row. It is clear a deadly triangle may appear only as a "base" triangle for $ T'$. We claim that if a block from the base contained $ r$ holes, at most $ r$ holes are added to the block above it after removing the last row. We do the following procedure: the space between two consecutive holes in the last row can be filed in with diamonds except one downward triangle which has to be connected with a triangle above (clearly at least one of the downward triangles can be matched otherwise there would be too many holes breaking the condition). It is is easy to verify the claim after such a conclusion. Moreover it clear that any arrangement is of the above type otherwise we would create too many holes in $ T'$ (between any two consecutive holes we must crate a hole in $ T'$, and if we somewhere create more it would be over). Now we claim a "deadly" triangle arises from a full triangle. Indeed, if we have a base deadly triangle with sidelength $ j$ an $ j+l$ holes we can extend it one unit downward. This triangle has sidelength $ j+1$ and had originally also at least $ j+l$ holes according to our claim. So $ l=1$ and this triangle was full at the beginning. It only remains to manage the full base triangles, thus. If two full triangles of sidelength $ k,l$ intersect in a triangle of sidelength $ m$, we deduce this small triangle is also full and the big traingle of length $ k+l-m$ is too. So we may do such unions unless $ k+l-m$ is not $ n$. When we finish, we have two possible cases: a) we have some non-intersecting full triangles. Then every full base triangle is contained in one of them otherwise we could still unite it with one. Applying the induction hypothesis for them we can tile the bottom rows of them with diamonds without not making them full. Completing the tiling we achieve the goal. b) We have intersecting triangles, but uniting them would form the big triangle $ T$ for which we can not apply the induction step. It is easy to see this is possible only when there are two such triangles of sidelength $ k,l$ which intersect in a traingle of sidelength $ m$ and $ k+l-m=n$. Then we have at most $ m$ holes in the common part. So at least $ k+l-m=n$ holes in the union of these two traingles. It means the remaining parallelogram at the top contains no hole and then it can be tiled with diamonds. The two triangles can also be tiled. Moreover any tiling tiles also the common part of sidelength $ m$ completely. So we may tile one triangle, and tile the remaining part of the second. This is the desired tiling of $ T$. QED

Let me post a little bit shorter solution . Consider tiling with rhombus as matching upward and downward triangles and use Hall's theorem. All we have to do is check if Hall's condition is true. We know it's true for some special sets - all downwards triangles contained in some equilateral upward triangles. Suppose that Hall's condition is false and consider smallest set of downwards triangles and their neighbours which make that condition false. It has to be connected (connections by side). Consider smallest upward equilateral triangle containing this set (call its side's lenght k). Now we have to prove that in this set there are at most $k$ more upward triangles than downard but it can be easily proven by induction on $k$ that there are exactly $k$ more upward triangles (recall that we consider smallest equilateral triangle containing that set, so that set has to touch all sides of that triangle). P.S. My 100th post !

I think your shorter solution is incorrect. Proving that in the equilateral triangle there are at most $k$ more upward triangles than downward triangles does not complete the proof, because it doesn't tell you anything about your original set that violated Hall's condition. Also, you didn't prove that if the tiling exists then no triangle that violates the condition exists. Here is my solution. First I prove that the condition implies the tiling exists. We want to use Hall's theorem to prove the Downward and the Upward triangles (we will call them Dts and Uts from now on, for convenience) in the holey triangle can be "married". Since in the original big triangle there are $n$ more Uts than Dts, there is an equal number of Dts than Uts in the holey triangle. Now, suppose they can't be married. Then by hall theorem there exists a set $S$ of Dts such that $N(S) < S$ (sorry, I want to put cardinality symbols but I don't know how to in this keyboard). ($N(S)$ is the set of Uts adjacant to a Dt in $S$). Take the LARGEST such set $S$. Say $S=D_1,...,D_m$ (sorry, I don't know how to put curly brackets in this keyboard). We will call a "$p$-arrow" the set of Dts that are contained in an upward equilateral triangle of side $p$. For example, a $2$-arrow is just one Dt. If $A$ is an arrow, call $f(A)$ the "side" of $A$ (the such that $A$ is an $f(A)$-arrow), Take $S=A_1 \cup A_2 ... \cup A_x$ (where $A_i$ is an arrow) such that $x$ is minimal. (Such a thing is possible, since we could consider the union of $m$ $2$-arrows ($m$ Dts).) Now, if the upward triangles corresponding to $A_1$, ..., $A_x$ were disjoint, then we could apply the condition about upward triangles to finish with a contradiction (Note: it is easy to see these triangles do not escape the boundary of the holey triangle). So assume we have $A_1 \cap A_2$ is not empty. First, we have to establish two facts about $S$. First, if two consecutive Dts are both in $S$, then the Dt that is above these Dts must also be in $S$ (since it contributes only at most one new element to $N(S)$ and $S$ is maximal). Also, if two semiconsecutive Dts are both in $S$ (separated by one Dt), then this Dt must also be in $S$ by the same reasoning. Using those propositions many times, we can conclude that $A'$ (the smallest arrow containing both $A_1$ and $A_2$, which is easy to see is contained in the holey triangle) satisfies $A'$ is a subset of $S$. Then we can make $x$ smaller by substituting $A_1$ and $A_2$ by $A'$. CONTRADICTION Therefore we are done with the difficult part. Now we do the easy part. This is easy. We also use Hall's Theorem, but backwards. The condition is equivalent to proving that $N(A)$ has more or equal elements than $A$, where $A$ is an arrow. This is true because of Hall's theorem. So we are done!

We will prove the result with induction. The $n=1$ case is trivial, so proceed to the inductive step, with a holey triangle of size $n$. It is obvious that there is at least $1$ hole in the base, so consider all holes in the base, at positions $a_1,a_2,\ldots,a_k$, where position $1$ refers to the leftmost unit equilateral on the base. Clearly, we can tile the triangles between positions $1$ and $a_1$ with diamonds, as well as the positions $a_k$ to $n$. Now, consider the interval between $a_i$ and $a_{i+1}$, for all $i$. Within this range, there are an odd amount of unit equilaterals, so we will have to have at least one vertical diamond. Suppose we use exactly one, then note that it creates an effective hole in the upper equilateral triangle of size $n-1$, and the hole created by the diamond can be placed anywhere above the interval. Now, I claim I can place the hole such that the holey condition is still satisfied for the upper $n-1$-equilateral. Of course, we only need to consider sub-equilateral triangles which include the bottom row of the $n-1$-equilateral. Now, define a maximal triangle to be a triangle of side length $k$ with base on the bottom row of the $n-1$-equilateral such that there are exactly $k$ holes inside of it. Note that as long as the hole isn't put inside a pre-existing maximal triangle, the new hole will preserve the holey-ness of the arrangement. Lemma: If the union of the bases of two maximal triangles is a line segment, then the triangle with base defined as that union is also maximal. Proof: Call the triangle in question the MEGA-triangle. Note that the amount of holes in the MEGA-triangle is equal to the sum of the side lengths of the two maximal triangles which form it, minus the amount of holes in their intersection. If the side length of the MEGA-triangle is $c$, note that the aforementioned quantity is at least $c$, however the amount of holes in the MEGA-triangle is at most $c$, due to the holey-ness of the arrangement. Therefore, there are $c$ holes in the MEGA-triangle, and the MEGA-triangle must be maximal as well. Now, we will proceed sequentially through the ranges. Suppose that we have already placed the vertical diamonds in the ranges $a_i\rightarrow a_{i+1}$ for $1\le i < k$ (in positions $t_1$ through $t_{k-1}$ in the second to last row), and the holey-ness condition is still preserved for the top $n-1$-equilateral. I claim we can find a way to place the vertical diamond in the range $a_k$ to $a_{k+1}$. To do this, consider all currently existing maximal triangles (taking into account the newly formed holes.) Now, combine overlapping maximal triangles into MEGA-triangles, until we have a collection of disjoint maximal triangles which represent the union of the bases of all the maximal triangles. Now, if there exists a space within the range which isn't part of the base of a maximal triangle, we can just place our new hole there, and it will work perfectly. Otherwise, we will have a maximal triangle which covers the entire range, which we will call the SUPER-triangle. Also, extend the SUPER-triangle down a row, to form a SUPERR-triangle. Note that if there are $a$ new holes in the SUPER-triangle, then in the original configuration, there were at least $a+1$ holes in the SUPERR-triangles at the beginning. So, before we added any holes, the SUPERR-triangle had to be maximal, or else there would've been a contradiction, which occurs when there are exactly $a+1$ holes in its base. In other words, if the position of the leftmost point in the SUPER-triangle is $l$ and the rightmost point of $r$, then we must have $r<a_{k+2}-1$, and $a_j < l \le t_j$, for some $j$. However, since we know that the SUPER-triangle isn't next to any other maximal triangle, location $l-1\ge a_j$ cannot be in a maximal triangle, so we can shift the hole at $t_j$ to $l-1$. Now, we repeat this process. As the sum of the positions of the holes strictly decreases after every adjustment, this algorithm eventually terminates, and after all the adjustments have been made, we will have a viable place to place the hole in our range. Now, repeat this for all intervals to get a viable way to place all our holes. After this is done, note that we have filled the entire bottom row, and the upper $n-1$-triangle has exactly $n-1$ holes, and satisfies the holey condition, so we can apply inductive hypothesis to finish.

Attachments:

Ha, Hall’s Marriage Theorem is the shortcut that make it an ez problem.

Outline of solution from Twitch Solves ISL: The idea is to show that the condition in the problem is equivalent to the condition in Hall's Marriage Lemma, wherein we try to match down-triangles to non-hole up-triangles. To this end, let's say two holes are adjacent if they share a vertex, and a set of holes is connected if they form a connected component with respect to the adjacency condition. Finally, the bounding box of a set of holes is the smallest upwards equilateral triangle of some side length (by inclusion) that contains all the triangles. Claim: Consider a connected set $D$ of down-triangles which has a bounding box of side length $k$. Then at least $\left\lvert D \right\rvert + k$ up-triangles are adjacent to at least one of the down-triangles in $D$. Proof. [Outline of proof] The idea is to go by induction on $|D|$, by deleting the uppermost triangle which touches the left boundary of the bounding box of $D$. (The catch is that doing this deletion may disconnect $D$, so this case needs to be handled as well.) $\blacksquare$ Suppose the problem condition holds; we prove Hall's condition. Consider a general set $\mathcal D$ of down-triangles. The $\mathcal D$ is the disjoint union $D_1 \sqcup \dots \sqcup D_k$ of $k$ connected components. The problem condition implies that now that there are at least $|D_i|$ up-holes neighboring some down-hole in $D_i$, and any up-hole is adjacent to down-triangles in at most one $D_i$; so Hall's condition holds for $\mathcal D$. For the converse direction, if Hall's condition holds, taking $\mathcal D$ to be all the down-triangles in some equilateral triangle of side length $k$ implies the result. (This does not need the claim; it is the easy direction.)

Ignore this.

Refer to unit upward and downward triangles as up-triangles and down-triangles respectively (upward/downward triangle still refer to triangles of any side length), and ignore the problem's definition of $T$. We will use Hall's Marriage Lemma to show that there exists a perfect matching between the down-triangles and the non-removed up-triangles. Call two unit triangles adjacent if they share an edge, and a set of down-triangles connected if the graph formed where shared vertices correspond to edges is also connected. Finally, let the bounding triangle of a set of down-triangles be the smallest upward triangle that contains the set, and let $f(S)$ denote the side length of the bounding triangle of $S$. Note that two non-connected sets of down-triangles have non-overlapping bounding triangles, so no up-triangle can be adjacent to elements of both sets. The key claim is the following: Claim: For any connected set $D$ of down-triangles, there are at least $|D|+f(D)$ (not necessarily non-removed) up-triangles adjacent to some element of $D$ (henceforth referred to as simply "adjacent to $D$"). Proof: We use downwards induction on $|D|$. For the base case of $|D|=1$, note that the bounding triangle of $D$ has side length $2$, so at most $2$ of the $3$ adjacent triangles to the sole element of $D$ are removed, as desired. For the inductive step, we consider the following cases on the number of triangles in the lowest "row" of $D$: At least two triangles. Let the leftmost triangle on this row be $T$. Then the up-triangle $T'$ immediately left of $T$ (which evidently exists) is not adjacent to any element of $D$ except for $T$. Now remove $T$ from $D$ to yield $D'$. If $D'$ is connected, we have $f(D)=f(D')$, so there are at least $|D|+f(D)-1$ up-triangles adjacent to $D'$. Otherwise, $D'$ can be partitioned into two connected subsets $D'_1,D'_2$ (which are connected to the upper left and bottom corners of $T$). It is easy to see that we must have $f(D'_1)+f(D'_2)=f(D')$ (left and right edges should be shared, and the two bounding triangles should touch at the upper right corner of $T$, so by inductive hypothesis there are at least $|D'_1|+|D'_2|+f(D'_1)+f(D'_2)=|D|+f(D)-1$ up-triangles adjacent to $D'$. It then follows that there are at least $|D|+f(D)$ up-triangles adjacent to $D$, as desired. One triangle. Let this triangle be $T$. Then the up-triangles $T',T''$ immediately to the left and right of $T$ respectively are not adjacent to any other element of $D$. Remove $T$ from $D$ to yield $D'$. If $D'$ is disconnected, then it can be partitioned into $D'_1,D'_2$ which touch the top left and top right corners of $D'$ respectively. But since no other down-triangles lie in $T$'s row, both down-triangles above $T$ and sharing a vertex with $T$ are in $D'$, so $D'$ is connected. Thus we have $f(D)-1=f(D')$, so there are at least $|D|+f(D)-2$ up-triangles adjacent to $D'$ and then $|D|+f(D)$ triangles adjacent to $D$. Suppose the problem condition holds, and consider an arbitrary set $D$ of down-triangles. We partition it into disjoint connected subsets $D_1,\ldots,D_m$. Then the claim implies that there are at least $|D_1|+\cdots+|D_m|+f(D_1)+\cdots+f(D_m)$ up-triangles adjacent to $D$. Removing all holes, it follows that we have at least $|D_1|+\cdots+|D_m|=|D|$ non-hole up-triangles adjacent to $D$, so Hall's condition is satisfied and thus a perfect matching exists (this is the if direction). For the only if direction, note that if a matching exists, we can take $D$ to be any complete set of down-triangles in an upwards equilateral triangle $T$ of side length $k$. Then we need at most $k$ holes in $T$, else there are fewer up-triangles than down-triangles in $T$ which contradicts the existence of a matching. $\blacksquare$

JuanOrtiz wrote: I think your shorter solution is incorrect. Proving that in the equilateral triangle there are at most $k$ more upward triangles than downward triangles does not complete the proof, because it doesn't tell you anything about your original set that violated Hall's condition. Also, you didn't prove that if the tiling exists then no triangle that violates the condition exists. Here is my solution. First I prove that the condition implies the tiling exists. We want to use Hall's theorem to prove the Downward and the Upward triangles (we will call them Dts and Uts from now on, for convenience) in the holey triangle can be "married". Since in the original big triangle there are $n$ more Uts than Dts, there is an equal number of Dts than Uts in the holey triangle. Now, suppose they can't be married. Then by hall theorem there exists a set $S$ of Dts such that $N(S) < S$ (sorry, I want to put cardinality symbols but I don't know how to in this keyboard). ($N(S)$ is the set of Uts adjacant to a Dt in $S$). Take the LARGEST such set $S$. Say $S=D_1,...,D_m$ (sorry, I don't know how to put curly brackets in this keyboard). We will call a "$p$-arrow" the set of Dts that are contained in an upward equilateral triangle of side $p$. For example, a $2$-arrow is just one Dt. If $A$ is an arrow, call $f(A)$ the "side" of $A$ (the such that $A$ is an $f(A)$-arrow), Take $S=A_1 \cup A_2 ... \cup A_x$ (where $A_i$ is an arrow) such that $x$ is minimal. (Such a thing is possible, since we could consider the union of $m$ $2$-arrows ($m$ Dts).) Now, if the upward triangles corresponding to $A_1$, ..., $A_x$ were disjoint, then we could apply the condition about upward triangles to finish with a contradiction (Note: it is easy to see these triangles do not escape the boundary of the holey triangle). So assume we have $A_1 \cap A_2$ is not empty. First, we have to establish two facts about $S$. First, if two consecutive Dts are both in $S$, then the Dt that is above these Dts must also be in $S$ (since it contributes only at most one new element to $N(S)$ and $S$ is maximal). Also, if two semiconsecutive Dts are both in $S$ (separated by one Dt), then this Dt must also be in $S$ by the same reasoning. Using those propositions many times, we can conclude that $A'$ (the smallest arrow containing both $A_1$ and $A_2$, which is easy to see is contained in the holey triangle) satisfies $A'$ is a subset of $S$. Then we can make $x$ smaller by substituting $A_1$ and $A_2$ by $A'$. CONTRADICTION Therefore we are done with the difficult part. Now we do the easy part. This is easy. We also use Hall's Theorem, but backwards. The condition is equivalent to proving that $N(A)$ has more or equal elements than $A$, where $A$ is an arrow. This is true because of Hall's theorem. So we are done! How can you guarantee that when you replace $A_1$ and $A_2$ with $A'$ you don't get an upward triangle with extra Uts? Moreover, could you clarify why $S$ should contain $A'$? What do you mean by "....using those propositions...? Do you increase the elements of $S$ or do you say the imposibility of $S$ having neither consecutive Dts nor semiconsecutive Dts because of the maximality of $|S|$? Could you help me to understand the solution? I want to understand the solution as it looks really nice because of the Marriage theorem. Thanks in advance.

Call upward and downward equilateral triangles of unit length u-Triangles and d-Triangles, respectively. Clearly, in an upward equilateral triangle of side length $k$, there are $k$ more u-Triangles than d-Triangles. In a tiling, each d-Triangle must be matched up with an adjacent u-Triangle. For each d-Triangle in this $k$-lengthed upward equilateral triangle, the only adjacent triangles are also inside the triangle, so if we remove more than $k$ u-Triangles then there are not enough u-Triangles to match up with all the d-Triangles. Thus, the condition is necessary. Now to prove that it is sufficient. We proceed with Hall's. We will show that after the $n$ removals, we can match each d-Triangle with a distinct u-Triangle and thus completing the tiling. It suffices to prove that for any set of d-Triangles, there are as many u-Triangles that are adjacent to some d-Triangle in the set. Suppose this set is not connected. That is, suppose that we can partition the set into two subsets such that no two d-Triangles in different subsets can be touching by a corner. In this way, the u-Triangles adjacent to the two subsets are also different, so it suffices to prove them separately. We proceed with induction. We start with a single d-Triangle. For the induction, we take off the d-Triangle that that has the greatest impact on the number of u-Triangles adjacent to some d-Triangle. We switch to addition. We keep track of three variables as we add onto this single d-Triangle: $d$, then number of d-Triangles, $u$, the number of u-Triangles adjacent to some d-Triangle in the set, and $s$, the size of the smallest upward equilateral triangle that encompasses all of our current ones. At any point, the number of u-Triangles adjacent to some d-Triangle that wasn't removed is at least $u-s$. We start with $d=1$, $u=3$, and $s=2$. If we add one to $d$, then we add zero, one or two to $u$. We cannot add three since that requires us to create a disconnected set of d-Triangles. We also add at most one to $s$. If we add two to $u$, $u-s\ge d$ still must hold since $s$ increases at most $1$ and $d$ exactly $1$. If we add one to $u$ and add one to $s$, that's not possible since the added d-Triangle, and thus two of its adjacent u-Triangles, must be outside of the all-encompassing upward equilateral triangle. If we add zero to $u$, then we have filled in a "hole" that must be surrounded by other d-Triangles, contradiction to our selection criteria. Thus, we are done.