5 ms·

It exhibits two distinct constructions both of which demonstrate that n^2 + 2 unit equilateral triangles are sufficient to cover an equilateral triangle of side

It exhibits two distinct constructions both of which demonstrate that n^2 + 2 unit equilateral triangles are sufficient to cover an equilateral triangle of side n + ε. The obvious area argument shows that at least n^2 + 1 are required. A small modification of the second figure can show that for any non-equilateral triangle, n^2 + 1 such triangles will cover a similar triangle of length ration 1 : n + ε; it remains (as of 2010, at least; see [1]) an open problem whether a construction of n^2 + 1 triangles exists in the equilateral case. 1. http://www.wfnmc.org/mc20101.pdf http://www.wfnmc.org/mc20101.pdf

kristopolous 3y ago
What's ε in this case? How is it bound? Also, they're permitting overlapping of triangles, right? If that's the case, why can't you just add an arbitrary + 1 wherever you please and call it a day?
- mkl 3y ago
  ε > 0. Yes, overlapping triangles. Add an arbitrary + 1 to what? You need to arrange the small triangles so that they cover the big triangle of side length n+ε. n² unit equilateral triangles cover a big equilateral triangle of side length n without overlap, so at least n²+1 are needed for side length n+ε, and the paper shows (not especially clearly, IMHO) that at most n²+2 are needed.
  - deleted 3y ago
    [deleted]
  - crote 3y ago
    Figure 1 on its own is a pretty decent demonstration, once you zoom in quite a bit. The annoying part about the paper is figure 2: it shows a different method of doing so, without mentioning that it is unrelated to figure 1. It is also drawn in a less obvious style, which really hurts its readability.
    - mkl 3y ago
      Yes, Figure 1 is okay, but Figure 2 is not very clear; most of the triangles are missing and have to be imagined. I also think the examples for a single n are not the best argument for the general case - the reader can extrapolate other diagrams and a proof but I think a slightly longer paper could be clearer.
- crote 3y ago
  ε is used to denote an arbitrary small value, which isn't zero. Overlap is indeed required here. Let's say you have a large equilateral triangle of side n. Covering it with triangles of side 1 is pretty easy: you build a pyramid out of them without any overlap. That requires n^2 smaller triangles. Now let's say you make the large triangle sliiightly larger, so it'll have sides of n+ε instead of n - for example we gone from 11.0 to 11.00001. How many smaller triangles do you need to cover it? Obviously n^2 isn't going to be enough - because that was exactly enough to cover a large triangle of side n. Our slighty-bigger triangle is slightly bigger, so it has a larger area. We're going to need at least one additional small triangle to cover the added area, leaving us with n^2+1 as an absolute lower bound. But just because it is a lower bound doesn't mean it is actually possible - you'd first have to demonstrate that it can actually be done. This paper demonstrates two different methods of constructing it with n^2+2 triangles, providing an upper bound which is definitely possible. This means we still don't know the exact number of triangles required, but we do know it is definitely bigger than n^2 and definitely smaller than or equal to n^2+2. This leaves the question: is n^2+1 possible?
  - kristopolous 3y ago
    Q1: So the second one is essentially "pushing things down" from the top as in the extra space is being accounted for by those 2 additional triangles? Q2: The problem is non-trivial because it appears to open up a trapezoid somewhere in the stacked triangle solution that can't be covered by a single triangle? Q3: This sounds provably impossible unless there's another way to cover the n triangle other than stacking. It sounds like the solution space is pretty finite and can be manually exhausted. Is there something I'm missing? Sorry, I'm slow on these things.
    - crote 3y ago
      Q1: If you look at figure 1, you can see that the "down" triangle row is sticking out a bit to the left and to the right. This allows the "up" triangles to move down and to the side a little bit. Both the "up" and the "down row are one triangle bigger than then would've been in the non-ε variant, which allows the extra space being covered. Q2: A trapezoid is left at the bottom if you just stack triangles, yes. Other approaches will probably result in one or more gaps of a different shape. Q3: There's an infinite number of ways you can arrange the small triangles, so an exhaustive search isn't going to help you. The interesting part is that there is a proof of n^2+1 being possible for all non-equilateral triangles, so there is definitely a possibility of it also being possible for equilateral triangles. As you already noticed, there might be approaches beyond stacking. Look up "square packing in a square"[0] for fun, you get some really ugly-looking non-obvious results out of that. Don't worry about it, I know just enough to understand the problem - half of the linked PDF is also beyond me. [0]: https://en.wikipedia.org/wiki/Square_packing#Square_packing_in_a_square https://en.wikipedia.org/wiki/Square_packing#Square_packing_...

kristopolous 3y ago

What's ε in this case? How is it bound? Also, they're permitting overlapping of triangles, right? If that's the case, why can't you just add an arbitrary + 1 wherever you please and call it a day?

mkl 3y ago
ε > 0. Yes, overlapping triangles. Add an arbitrary + 1 to what? You need to arrange the small triangles so that they cover the big triangle of side length n+ε. n² unit equilateral triangles cover a big equilateral triangle of side length n without overlap, so at least n²+1 are needed for side length n+ε, and the paper shows (not especially clearly, IMHO) that at most n²+2 are needed.
- deleted 3y ago
  [deleted]
- crote 3y ago
  Figure 1 on its own is a pretty decent demonstration, once you zoom in quite a bit. The annoying part about the paper is figure 2: it shows a different method of doing so, without mentioning that it is unrelated to figure 1. It is also drawn in a less obvious style, which really hurts its readability.
  - mkl 3y ago
    Yes, Figure 1 is okay, but Figure 2 is not very clear; most of the triangles are missing and have to be imagined. I also think the examples for a single n are not the best argument for the general case - the reader can extrapolate other diagrams and a proof but I think a slightly longer paper could be clearer.
crote 3y ago
ε is used to denote an arbitrary small value, which isn't zero. Overlap is indeed required here. Let's say you have a large equilateral triangle of side n. Covering it with triangles of side 1 is pretty easy: you build a pyramid out of them without any overlap. That requires n^2 smaller triangles. Now let's say you make the large triangle sliiightly larger, so it'll have sides of n+ε instead of n - for example we gone from 11.0 to 11.00001. How many smaller triangles do you need to cover it? Obviously n^2 isn't going to be enough - because that was exactly enough to cover a large triangle of side n. Our slighty-bigger triangle is slightly bigger, so it has a larger area. We're going to need at least one additional small triangle to cover the added area, leaving us with n^2+1 as an absolute lower bound. But just because it is a lower bound doesn't mean it is actually possible - you'd first have to demonstrate that it can actually be done. This paper demonstrates two different methods of constructing it with n^2+2 triangles, providing an upper bound which is definitely possible. This means we still don't know the exact number of triangles required, but we do know it is definitely bigger than n^2 and definitely smaller than or equal to n^2+2. This leaves the question: is n^2+1 possible?
- kristopolous 3y ago
  Q1: So the second one is essentially "pushing things down" from the top as in the extra space is being accounted for by those 2 additional triangles? Q2: The problem is non-trivial because it appears to open up a trapezoid somewhere in the stacked triangle solution that can't be covered by a single triangle? Q3: This sounds provably impossible unless there's another way to cover the n triangle other than stacking. It sounds like the solution space is pretty finite and can be manually exhausted. Is there something I'm missing? Sorry, I'm slow on these things.
  - crote 3y ago
    Q1: If you look at figure 1, you can see that the "down" triangle row is sticking out a bit to the left and to the right. This allows the "up" triangles to move down and to the side a little bit. Both the "up" and the "down row are one triangle bigger than then would've been in the non-ε variant, which allows the extra space being covered. Q2: A trapezoid is left at the bottom if you just stack triangles, yes. Other approaches will probably result in one or more gaps of a different shape. Q3: There's an infinite number of ways you can arrange the small triangles, so an exhaustive search isn't going to help you. The interesting part is that there is a proof of n^2+1 being possible for all non-equilateral triangles, so there is definitely a possibility of it also being possible for equilateral triangles. As you already noticed, there might be approaches beyond stacking. Look up "square packing in a square"[0] for fun, you get some really ugly-looking non-obvious results out of that. Don't worry about it, I know just enough to understand the problem - half of the linked PDF is also beyond me. [0]: https://en.wikipedia.org/wiki/Square_packing#Square_packing_in_a_square https://en.wikipedia.org/wiki/Square_packing#Square_packing_...