Divide an equilateral triangle into at least $100$ regions? A piece of paper has the shape of an equilateral triangle. What is the minimum number of straight lines parallel to its sides that divide the triangle into at least $100$ regions?
The answer said it is $16$. But. But. Don't know how to solve it. Thank you.
 A: Let us start with one line, parallel to each side of the triangle. Consider the following diagram:
$$n=3$$
By drawing 3 lines, we split it up into 7 segments.
Now what we can do is split up the inner triangle with the same logic:
$$ n = 6  $$
Note that this splits up the inner triangle into another 7 parts. In addition to this, it also adds 6 other segments into the triangle, between the first and seconds sets of lines.
This means that with $6$ lines, we have $7 + 7 + 6  = 20 $ segments
It is obvious that if we add another 3 lines, one each parallel to the sides that it will split up the inner triangle into another 7 segments.
$$n=9$$

In addition to this 7, we see again, it adds another 6 segments, next to the 6 created after the previous step. And another 6 is also added, inside 1st set of lines but outside the second set.
Therefore, here we have $20 + 7 + 6 + 6 =39$ segments.
At this point we can put together a formula for this. Let $n$ be the number of lines divided by 3 and $f(n)$ be the number of segments. (We will work in sets of 3 as it is easier. Then we have $$f(1) = 7,\quad f(2)=20\quad f(3) = 39$$
For each addition of 1 in $n$, the inner triangle is split into 7. We also see an increase in multiples of 6.
We know that when $n=2$, we have $7 + 7 + 6$ segments.
When $n=3$, we have $7+7+7+6+6+6$ segments.
We can see a pattern here.
Thus, we can make the following equation:
$$ f(n) = 7n + 6n + 6(n-1) + 6(n-2) + ... 6,\quad n>0$$
$$\implies f(n) = 7n + 6n + 6n +... + 6n -6 - 12- 18 -...-6(n-1)$$
The $-6-12...$ bit can be written as $$-1(6 + 12 + 18 + ... + n-1) = -3(1+2+3+...+(n-1) = -3\left(\frac{(n-1)((n-1)+1)}{2}\right) = \frac{-2}{3}n(n-1)$$
So, now we have $$f(n) = 7n + 6n(n-1) -\frac{2}{3}n(n-1) = 7n + 6n^2 - 6n -\frac{2}{3}n + \frac{2}{3} = 6n^2 + \frac{1}{3}n + \frac{2}{3}$$
Now we want to investigate the case with 100 segments.
Let $f(n) = 100$
Then $$ 100 = 6n^2 + \frac{1}{3}n + \frac{2}{3} \implies n \approx 4.04$$
Therefore, we need at least $n=5$ for 100 segments (as $ n$ must be a whole number). 

Therefore, we need $ 3(5) = 15$ lines for at least 100 segments in the triangle.
A: We can use Euler's identity for graphs, $V - E + F = 2$. We want to have $F = 101$(the outside of the triangle is a face).
Recall that 3 lines will never intersect, as if we shift the third line, we can create an extra region, which means the 3 lines intersecting cannot yield a minimum. Let $x$ be the amount of lines parallel to side 1, $y$ to side 2 and $z$ to side 3. Lines parallel to side one will be called $x$ lines and sides 1,2,3 are baselines. Let us find the amount of vertices. 
Consider the vertices formed by the $x$ lines. Each of the $x$ lines intersects the base $2$ times, the $y$ lines $y$ times and the $z$ lines $z$ times. All together this yields $x(z + y + 2)$ vertices. Now consider the $y$ lines. They intersect the other lines in the same way, except we don't count the intersections between $x$ lines and $y$ lines as we have already counted those. This yields a $y(z + 2)$ vertices. Now consider the $z$ lines. We can't consider intersections with $x$ lines and $y$ lines as we have already counted those, so we have $2z$ vertices. Don't forget the original 3 vertices from the triangle. Now we have a function for $V$.
\begin{equation}
V(x,y,z) = x(y + z + 2) + y(z + 2) + 2z + 3 = xy + xz + yz + 2(x + y + z) + 3
\end{equation}
Now we consider edges. Consider edges that are parallel to the $x$ lines. You can see that each line contains the same amount of edges. So we just need to find the amount on side 1. Also we wont over count as an edge can't be parallel to both the $x$ lines and $y$ lines. We can see that the amount of edges on side 1 is $y + z + 1$. There are $x + 1$ total lines like this in the triangle. We can use this argument for side 2 and side 3 as well. This yields the expression
\begin{align}
E(x,y,z) &= (x + 1)(y + z + 1) + (y + 1)(x + z + 1) + (z + 1)(x + y + 1)\\
&= 2(x + y + z + xy + xz + yz) + 3
\end{align}
Note that it is always more optimal to have $x$,$y$ and $z$ as close to each other as possible(consider a triangle with only $x$ lines) so they should only differ by 1. So lets consider cases where $x = y = z$ using the simplified formulas
\begin{align}
V(x,x,x) &= 3x^2 + 6x + 3\\
E(x,x,x) &= 6x^2 + 6x + 3 
\end{align}
and then add or subtract 1 from one or two of the variables.
We now do a bit of algebra(remember that $x \geq 0$).
\begin{align}
V - E &= 2 - F\\
3x^2 + 6x + 3 - 6x^2 - 6x - 3 &= 2 - 101\\
3x^2 &= 99\\
x &= \sqrt{33} \approx 5.7
\end{align}
We can see that having $x = y = z = 5$ yielding $15$ lines is not enough(do not round up as we can get more faces by adding individual lines instead of in groups of 3). So first we will add 1 line to $x$. If that doesn't work we can add one line to side $y$. Now if those two cases don't work, then we can round $5.7$ to $6$.
First adding one to $x$. We can see that $E(6,5,5) = 241$ and $V(6,5,5) = 139$. Plugging this into $F = E - V + 2$ we get that $F = 241 - 139 + 2 = 104$. Since $104 > 100$ we are done, as adding one more to $y$(i.e using $V(6,6,5)$) would yield more sides than we need.
Therefore we will require $5 + 5 + 6 = 16$ of such lines. 
