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