[crote]

ε 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]

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]

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_...

[kristopolous]

> There's an infinite number of ways you can arrange the small triangles

I don't understand how this is - you have to eventually have a consolidated gap for your extra triangle, everything else needs coverage. It demands a level of efficiency that confines the possibilities.

This isn't a packing problem as in gaps are permitted, it's a coverage problem as in, gaps are not.

You can overlap things at leisure but you quickly enter the efficiency problem again. Once your aggregate overlap is the area of one of your smaller triangles, it's no longer possible.

So as far as I can see those are the bounds. You're allowed to overlap and extrude up to some function of the (area of the smaller triangle, n and the epsilon) and the gap that's created must be confined to fit inside the geometry of one of the smaller triangles.

It appears to be tightly bound enough to exclude exotic arrangements of the triangles.

Furthermore there's no novel arrangement possibilities you get once n becomes really really big because of the geometry confinement problem - so some exotic thing like dilating a row along an arc or skewing through some pattern isn't going to help you.

This means demonstrating for a very small n is sufficient. You've got the geometry of the trapezoid to bring to the confine of the gap while the sum of the overlapping and extrusions can't pass a certain threshold.

I bet it's within my ability to write a computer program to exhaust it and if I was better at the mathematical fancyspeak, there's probably an algebraic proof in here.