A "holey triangle" is an upward equilateral triangle of side length n with n upward unit triangular holes cut out. A "diamond" is a 60-120 unit rhombus. Prove that a holey triangle T can be tiled with diamonds if and only if the following condition holds: Every upward equilateral triangle of side length k in T contains at most k holes, for 1 <= k <= n. ------------------------------------------------- n=1 is a trivial case n=2: can be tiled if one the holes are corners: * * * X . X * * * | * * * ./' X X ' X X '\. * * * * * * * * * So, actually every time. And the condition says that every 1-triangle contains at most 1 hole -- trivially satisfied. Let's try n=3, when the condition is not satisfied. Well, then there is a 2-triangle of the form * X * * X ' X * * * Obviously, it cannot be tiled. On the contrary, if no holes form three corners of a 2-triangle. What are the options (up to symmetry) * * * * * . X X X X * * * * * * * * * * X ' X . ' . X ' . X ' . X ' . * * * * * * * * * * * * * * * . ' X ' . X ' . ' X X ' . ' . . ' X ' . . ' . ' X * * * * * * * * * * * * * * * * * * * * These are all the options. Can I tile all of them (I should according to the problem statement) * * * * * . X X X X * | * * * * * * * * * X ' X . '\. X '\. X '\. X '\. * * * * | * * * * * * * * * * * ./' X '\. X ' ./' X X '\. '\. ./' X '\. ./' ./' X * * * * * * * * * * * * * * * * * * * * Now, I am interested how the blocking condition works in bigger triangles. (in the 2-triangle it is too obvious) So let's cut 4 holes in a 3-triangle: * * X . * * * * X ' . X ' X * * * * * * X ' . ' X X ' . ' X * * * * * * * * These are all the options not making blocked 2-triangle. Both of the blocking options work the way that they block it globally, even if there were other space around, it still cannot be tiled with the diamonds: * * X . * * * * X '\. X ' X * * * * * * X '\.(')X X '\.(')X * * * * * * * * After the forced moves, we have a triangle surrounded by tiled triangles -> contradiction. And the forced moves were not using the edges of the 3-triangle. This is according to the expectations, we would like such 3-triangles with holes to be blocking a tiling inside a bigger triangle. Actually, how could a tiling from outside could help? We could hypothetically tile something from outside, let's say from the bottom: * X * * X ' . * * * X ' . ' X * * | * * ' ... but it is actually equivalent to making more holes: * X * * X ' . * * * X ' X ' X * * * * So simply too much upward triangles are bad. This is the simple counting argument. in an n-triangle, there are n more up triangles than down-triangles. Once I block more than n up-triangles, I cannot tile it, not even with the help of outside because the "help from outside" only blocks more up-triangles. Implication "->" is proved. Now, I want to find the construction. I looks as an induction, -- tiling the bottom line, and reducing it to the 1-smaller case. There is the bottom line: ... * * * * * . ' . ' . ' ... ' . ' . * * * * * * * It has to contain at least one hole, otherwise the condition is broken. * * * * * . ' . ' ... ' X ' ... ' . ' . * * * * * * * * The corners force the tiling up to the closest hole. * * * * * * * * ./' ./' .../' ./' X ' ... ' X '\. '\... '\. '\. * * * * * * * * * * * * On the other hand, between any two holes, there is a "bathtub", that can raise a triangle anywhere above it. * * * * . . . . * | * * * * * * | * * * * * * | * * * * * * | * X ' ./' ./' ./' X X '\. ' ./' ./' X X '\. '\. ' ./' X X '\. '\. '\. ' X * * * * * * * * * * * * * * * * A problem would be (1) If all the options for raising a triangle were occupied by a hole. (2) If cutting out the last line, and adding holes above our "bathtubs" would break the condition. If we prove that both (1) and (2) cannot happen, we are done: * By tiling the last row, und cutting it, we add one hole per bath-tub to the one smaller triangle, that is one less holes that there were in the last row. So we decrease the number of holes by one, and we have the same tiling task with a triangle smaller by one (in other words, we just use the induction condition and we are done). Note that our tiling moves were forced. There are no other ways how to tile the corners, or the bathtub. So if it can be tiled, it can be tiled in the way we are doing it, in particular it should be provable that (1) and (2) cannot happen. (1) is relatively easy: If all the positions were blocked by a hole, * * * * X X X X * * * * * X ' . ' . ' . ' X * * * * * * Then the corresponding triangle contains too much holes: there is a k-triangle containing two holes at the last row and k-1 holes in the one but last row, at least k+1 holes in total, contradiction. Now, let's look at (2). For simplisity, assume that the left-most triangle above teh bathtub is free. * (.) * | * * * * X ' ./' ./' ./' X * * * * * What if putting a hole there (and cutting out the last row) breaks the condition. There has to be a k-triangle containing the triangle (.) at its last row, such that it already contains k holes. If its bottom side covers the bathtub, we can extend it by one, adding two holes to it, and make a contradiction. But it seems to be too much specific. It can be small, or large but going to the left, or there can be actually more than one extra holes due to the other bathtubs... Agrh... There must be a better way. Some generalization of a triangle. How to recognize a tilable shape in general? Can I break it by putting the diamond somewhere? * Yes, I can. * Because I can make the condition fail. * Or I can break the "dual condition": * . * * . ' . * | * * . '(.)'\. * * * * . ' ./' . ' . * * * * * So is the general condition for tilability of a shape that? (1) there is equal amount of 1-up-triangles and 1-down-triangles (2) if we restrict ourselves to a given k-up-triangle, there are at least as much 1-up-triangles as 1-down-triangles (3) if we restrict ourselves to a given k-down-triangle, there are at least as much 1-down-triangles as 1-up-triangles (these are all necessary conditions) I don't have a counterexample. Let's try to prove it. * Take the bottom-most row, and the left-most triangle in it. * if the triangle is an up-triangle, the tiling of it is forced. * there have to be a down-triangle next to it to satisfy the condition. * does the shape still satisfy the property? It cannot break any condition about an up-triangle. Can it break a condition about a down-triangle? * Do I really have to consider them? In the end, I am just emulating the bathtub process diamond by diamond. * Let's ignore it for now. * if the left-most triangle is a down-triangle. * suppose for contradiction that both options for a diamond breaks the condition (for up-triangles, obviously). * actually, blocking the diamond by a hole can be also seen as breaking the condition for a 1-up-triangle (if we use an unorthodox multi-hole interpretation), so the general case really is that both diamonds break the condition. * So there are two general up-triangles on the right and at the top of our 1-down-triangle that are both "full" (containing the same number of 1-up-triangles and 1-down-triangles). * How is this contradictory? Does it have to be? * If there is a hole on the right of T (our selected 1-down triangle), then the full up-triangle on the top of T can be extended one row down, creating a blocking up-triangle. So this case is fine: . ' . ' . ' . ' . ' . ' . ' . ' . ' * * * * * * * * * * . ' . ' . ' . '/.\' . ' . ' . ' . ' . ' * * * * * * * * * * . ' . ' . '/. ' .\' . ' . ' . ' . ' * * * * * * * * * * . ' . ' . '/. ' . ' .\' . ' . ' . ' . ' * * * * * * * * * * . ' . '/. ' . ' . ' .\' . ' . ' . ' * * * * * * * * * * . ' . '/. ' . ' . ' . ' .\' . ' . ' . ' * *---*---*-|-*---*---* * * * / ' X ' . ' .\' . ' . ' --- --- ---*---*---*---* * * * What if there is a hole at the top of T? Then again, the full triangle on the top of T can be extended to a blocking triangle by adding one left row and two holes -> also contradiction. . ' . ' . ' . ' . ' . ' . ' . ' . ' * * * * * * * * * * . ' . ' . ' . ' . '/.\' . ' . ' . ' . ' * * * * * * * * * * . ' . ' . ' . '/. '/.\' . ' . ' . ' * * * * * * * * * * . ' . ' . ' . '/. '/. ' .\' . ' . ' . ' * * * * * * * * * * . ' . ' . '/. '/. ' . ' .\' . ' . ' * * * * * * * * * * . ' . ' . '/X '/. ' . ' . ' .\' . ' . ' * * * * * * * * * * /X '\. ' . ' . ' . ' .\' . ' ---*---*---*---*---*---* * * But what about the general case: . ' . ' . ' . ' . ' . ' . ' . ' . ' . ' * * * * * * * * * * . ' . ' . ' . '/.\' . ' . ' . ' . ' * * * * * * * * * * . ' . ' . ' . '/. ' .\'/.\' . ' . ' . ' * * * * * * * * * * . ' . ' . '/. ' . '/.\' .\' . ' . ' * * * * * * * * * * . ' . ' . '/. ' . '/. ' .\' .\' . ' . ' * * * * * * * * * * . ' . '/. ' . '/. ' . ' .\' .\' . ' * * * * * * * * * * . ' . '/. ' . '/. ' . ' . ' .\' .\' . ' * *---*---*---*---*---*---* * * ?/. ' . ' . ' . ' . ' .\' *---*---*---*---*---*---* * Both triangles are full, so both have holes, and the holes could be somewhere away like that: * * * * * * * * * * . ' . ' . ' . ' . '/.\' . ' . ' . ' . ' * * * * * * * * * * . ' . ' . ' . '/X\' .\' . ' . ' . ' * * * * * * * * * * . ' . ' . ' . '/X ' .\'/X\' . ' . ' . ' * * * * * * * * * * . ' . ' . '/X ' . '/.\' X\' . ' . ' * * * * * * * * * * . ' . ' . '/X ' . '/. ' .\' X\' . ' . ' * * * * * * * * * * . ' . '/X ' . '/. ' . ' .\' X\' . ' * * * * * * * * * * . ' . '/X ' . '/. ' . ' . ' .\' X\' . ' * *---*---*---*---*---*---* * * / ?/. ' . ' . ' . ' . ' X\' -------*---*---*---*---*---*---* but then the triangle covering both has too many holes. It could be possibly prevented by putting holes into the intersection of the two triangles: . ' . ' . ' . ' . ' . ' . ' . ' . ' . ' * * * * * * * * * * . ' . ' . ' . '/.\' . ' . ' . ' . ' * * * * * * * * * * . ' . ' . ' . '/. ' .\'/.\' . ' . ' . ' * * * * * * * * * * . ' . ' . '/. ' . '/.\' .\' . ' . ' * * * * * * * * * * . ' . ' . '/. ' . '/X ' X\' .\' . ' . ' * * * * * * * * * * . ' . '/. ' . '/. ' . ' .\' .\' . ' * * * * * * * * * * . ' . '/. ' . '/X ' X ' X ' X\' .\' . ' * *---*---*---*---*---*---* * * ?/. ' . ' . ' . ' . ' .\' *---*---*---*---*---*---* but then the intersection has too many holes. So what is the general setup? Upper triangle has size 'a', right triangle has size b, and the upper triangle overlaps into the right triangle by c units: . ' . ' . ' . ' . ' . ' . ' . ' . ' . ' * * * * * * * * * * . ' . ' . ' . '/.\' . ' . ' . ' . ' * * * * * * * * * * . ' . ' . ' . '/. ' .\'/.\' . ' . ' . ' * * * * * * * * * * . ' . ' . '/. ' . '/.\' .\' . ' . ' * * * * * * * * * * . ' . ' . '/. ' . '/. ' .\' .\' . ' . ' * * * * * * * * * * . ' . '/. ' . '/. ' . ' .\' .\' . ' * * * * * * * * * * . ' . '/. ' . '/===== c =====\' .\' . ' * *---*---*---*---*---*---* * * / ===X=?/=== a ==========. ' .\' *--- ---*---*---*---*---*---*---* ========== b ========== ========== a + b - c ========== Then the triangle covering all that has length a+b-c. And the overall number of holes here is a+b (because the triangles are full) minus at most c (there cannot be more holes in the intersection, otherwise, we have a contradiction), plus one (the "hole" at the left of the first triangle in our shape). So the union has at least a+b-c+1 holes -- contradiction. Almost QED Oh, realization: the reasoning of the case "If the triangle is an up-triangle, the tiling of it is forced." was too fast. The addition of the diamond could add a "hole" to a triangle: * * * * * * * * * * . ' . ' . ' . ' . ' . ' . ' . ' . ' * * * * * * * * * * . ' . ' . '/.\' . ' . ' . ' . ' . ' . ' * * * * * * * * * * . ' . '/. ' .\' . ' . ' . ' . ' . ' * * * * * * * * * * . ' . '/. ' . ' .\' . ' . ' . ' . ' . ' * * * * * * * * * * / ./' . ' . ' . ' . ' -----------*---* * * * * but then there is a triangle smaller by this one added hole: * * * * * * * * * * . ' . ' . ' . ' . ' . ' . ' . ' . ' * * * * * * * * * * . ' . ' . '/.\' . ' . ' . ' . ' . ' . ' * * * * * * * * * * . ' . '/. ' .\' . ' . ' . ' . ' . ' * * * * * * * * * * . ' . '/. ' . ' .\' . ' . ' . ' . ' . ' * *---*---*---* * * * * * ./' . ' . ' . ' . ' * * * * * * So if this triangle satisfies the condition, so does the bigger triangle with the new hole. The problem feels almost solved but we have not exactly resolved what is the induction going on. Any shape satisfying the property from the problem statement and its dual? But we have not discussed the dual condition at all, there should be a way around it. For example some condition on our shape so that we don't have to care about the dual condition. The dual condition is necessary for arguing that there is always space for the forced diamond if the bottom-most, left-most triangle is an up-triangle. This could hypothetically break it: * * * * * * * * * * . X . ' . ' . ' . ' * * * * * * And this application of the dual condition could prevent it from happenning, the down-triangle contains more 1-up-triangles than 1-down-triangles. * * * *---*---*---* * * * \X . X . '/. ' . ' . ' * * * * * * \X X X/ \ / \X/ So, some condition like "every down-hole has an up-hole next to it"? * That is not sufficient. Even the up-holes could satisfy a similar condition and yet block any tiling. What about every down-hole is next to at least two up-holes? * That does not have to be true. In particular a hole created by a forced diamond typically does not satisfiy this condition: * X * * . ' X * * * X(X). ' X * * * * this does not seem as the right approach. Why does actually the original holey triangle satisfy the dual condition? * . -------*---*--- \ . ' . / \ * * * \ . ' . '/. * * * * .\' . '/. ' . * * * * * \ / Well, in this triangle, there is already equal number of 1-down-triangles as 1-up-triangles, and I am not even counting the holes. * . -------*---*------- \ . ' . / \ * * * / \ . ' . ' . / * * * * .\' . ' . '/. * * * * * \ / \ / \ / There could be more down-triangles than up-triangles here but there must be also at least one 1-hole in it since I cannot fit 4 holes into the 3 corners. Let's define "balance" of a shape as the number of available (non-hole) 1-down-triangles minus the number of 1-up-triangles. In general, if the big down-triangle intersects all three sides of the holey triangle, then the balance of it is zero (balance of the original holey triangle) minus the balance of the cut out corners. The balance of a corner is a number between 0 and '-a', where '-a' stands for its size. Balance of a corner is non-positive because of the condition on up-triangles. And because it is non-positive, the balance of the down-triangle is non-negative. It is still unclear what happens if the down-triangle does not intersect all three sides. But I actually proved the dual condition from the original condition. Could the two conditions be equivalent? Let's try to break just the dual condition: * . * * . ' X *---* | * X/X . X/. * * * * . ' .\X\X ' . * * * * * The middle 2-triangle here would not satisfy the dual condition but I still need to add 4 up-holes to make the entire triangle balanced. So I must either put an up-hole to the middle and revive the dual condition, or to put two up-holes to one of the corners, and destroy the original condition. What about trying to break only the original condition and not the dual condition. * X * * X ' X * * * . ' . ' . * * * * But then this down triangle does not satisfy the dual condition. * X * * X ' X ---*---*---*--- \ . ' . ' . / * * * * \ / \ / \ / \ / \ / Proving the equivalence seems difficult. But what if I could just replace the dual condition with the original condition where I needed the dual condition? In particular preventing: * * * * * * * * * * . X . ' . ' . ' . ' * * * * * * Is there an up-triangle with positive balance? Realization: I actually needed a good behavior of the shape not only at this position. * Also, when counting the holes of the triangle of the size a+b-c, I needed to know that there are no extra down-holes. Like here: * . * * X X X * * * X ' . ' X * * * * * In this shape, actually every up-triangle has non-positive balance. but it cannot be tiled. * The down-triangle with negative balance here is ---*--- \ . / * * X\X/X * * * X ' . ' X * * * * Just stop trying to handle general shapes. The proof is virtually done (from the "almost QED" point), we just need to handle holey triangles and what remains from them after cutting of several diamonds according to out procedure (down-most, left-most). It leads to a "generalized up-triangle": * /.\ * * /. ' .\ * * * /. ' . ' .\ * * * * /. ' . ' . ' .\ * * * * * /. ' . ' . ' . ' .\ * * * * * * /. ' . ' . ' . ' . ' .\ * * * * * * * /. ' . ' . ' . ' . ' . ' .\ * * * * * * * * /. ' . ' . ' . ' . ' . ' . ' .\ *---*---*---* * * * * * /. ' . ' . ' . ' . ' .\ *---*---*---*---*---*---* an up-triangle which can have the first (2n) 1-triangles from its last row being cut off. By a size of the generalized up-triangle, we mean the size of its right edge (that is the size of the original triangle). The generalized holey triangle is a generalized up-triangle of size n with n up-holes satisfying a generalized condition: * Every standard up-triangle intersects the generalized holey triangle in a (possibly generalized) up-triangle. * We require the number of holes in any such (generalized) up-triangle to be at most the size of the intersected (generalized) up-triangle. Now, we can run our proof ("almost QED") on these shapes, and it will work. ---------------------------------- UPDATE: I was still thinking about what is the condition for general shapes composed of unit 1-up-triangles and 1-down-triangles. * Obviously, the shape must be balanced (its balance must be equal zero, that is the same amount of 1-up triangles and 1-down triangles) * this corresponds to the assumption that there are n holes in the triangle at the beginning * Then I want a generalized condition of the standard condition, and the dual condition * A down-triangle breaking the dual condition has negative balance. * Since the entire shape is balanced, the complement of the down-triangle has positive balance. * So I could formulate a condition that generalizes an up-triangle, and a complement of a down-triangle, and requires them to have non-positive balance. * The common property of these two shapes is that they both have only up-triangle on their inner border. (maybe) General condition: * Every shape which has only 1-up-triangles at its inner border has non-positive balance. Let's call such a shape as an "up-shape" It is clear (it is designed the way) that this condition is still necessary and stronger than the original condition and the dual condition. However, it is not evident (without using solution) whether the holey triangle satisfying the original condition also satisfies the general condition. So what is a general up-shape? * For every 1-down-triangle I put in it, I must put there all its neighbors. And I can also use additional 1-up-triangles. * The additional 1-up-triangles does not help with breaking the condition since they can only decrease the balance. * I can assume that the general shape is given by a set of down-triangles, plus all their neighbors. * And the non-positive balance condition says that there are at least as many 1-up-triangles in the neighborhood than is the number of the 1-down-triangles that we started with. * Hm... This looks a lot like the condition in Hall's marriage theorem. * The theorem states: I have a bipartite graph satisfying the following: * whenever I pick a subset of the left part, it covers at least as big set on the right as is the size of the set on the left I started with. * Then there is a matching covering the entire left part. * Note: The backward implication also trivially holds. * In our case * the left part of the graph is formed by 1-down-triangles, * the right part of the graph is formed by 1-up-triangles, * edges represent neighborhood. * Our "General condition" exactly fit the condition in Hall's marriage theorem * So the theorem gives as a matching a.k.a. a tiling with diamonds covering every down-triangle (that is, covering the entire shape). Good, so the general condition is actually sufficient for any shape. But it is stil not evident whether this condition is satisfied in the original specific problem. Let's assume that we have a set of down-triangle breaking the Hall's condition (equivalently up-shape breaking general condition). * We need to find a triangle in which the original condition (equivalently the Hall's condition on a specific set) is broken. * There can be more "chunks" of the down-triangles, more specifically, there can be more components in the up-shape. * At least one of the component must have positive balance, so we can WLOG assume that the up-shape breaking general condition is symmetric. * The smallest up-triangle covering our up-shape is a natural candidate but it is not clear that it will work. * What if I could gradually expand the shape up to the triangle. * Assume there is a down-triangle having at least two neighbors already in the shape. * . * * /.\'/.\ *XXX*XXX* /.X'X.X'X.\ *XXX*XXX*XXX* /.X'X.X'X.X'X.\ * Then I can add them and keep the condition broken, * /.\ *XXX* /.X'X.\ *XXX*XXX* /.X'X.X'X.\ *XXX*XXX*XXX* /.X'X.X'X.X'X.\ because I added one 1-down-triangle and at most one 1-up-triangle. * Cool, if I keep adding 1-down-triangles according to this rule, I will eventually fill the entire triangle. * Problem solved! (second time) I like this solution much more than the previous one.