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.