If a unitsquare is partitioned into 101 triangles, is the area of one at least 1%?

Question

Update: The answer to the title question is no, as pointed out by Tapio and Willie. I would be more interested in lower bounds.

Monsky's famous theorem with amazingly tricky proof says that if we dissect a square into an odd number of triangles, they cannot have the same area. However, this proof does not give any quantitative bounds, while from the compactness it follows that there should be some bound, e.g. on the size of the largest triangle that is well separated from the reciprocal of the number of triangles. I don't think the original proof gives any bounds, and I am not aware of any (substantially) different proofs.

So if a unitsquare is partitioned into n (odd) triangles, then what is the smallest $f$ such that the largest will have area at least $f(n)$? Monsky says that $f(n)>1/n$, but how much bigger? If we partition to $n-1$ (even) equal area triangles and then cut one of them, then this gives $f(n)\le 1/(n-1)$, which is not sharp as shown by Tapio and Willie. But can anyone give a better lower bound than $1/n$?

Answer 1

As suggested in a comment above, I had asked a version of this question years ago. It makes sense to look at upper and lower bounds for the quantity $f(n)-\frac1n$. It is easily seen that $$ f(n) - \frac1n \le \frac1{n^2-n} $$ and indeed has shown that $$ f(n) - \frac1n = O\big(\frac1{n^3}\big), $$ see Bernd Schulze's paper "On the area discrepancy of triangulations of squares and trapezoids", The Electronic Journal of Combinatorics 18(1) (2011), #P137, 16 pp.

Computational experiments from an unpublished Diploma thesis (Katja Mansow, Ungerade Dreieckszerlegungen, TU Berlin 2003, 49 pages, in German) suggest that the true order of this difference is, however, singly-exponentially small. From gap-theorems in semi-algebraic geometry there is a doubly-exponential lower bound (details to be worked out).

Answer 2

For all $n \ge 5$ (odd) we have $f(n) < \frac{1}{n-1}$. So the answer to the question in the title is "not necessarily". Naturally, this does not answer the more interesting question on what the optimal $f$ is.

A triangulation showing this is in the picture: take a triangle $A$ of area $\frac{1}{n}$ at the left corner and divide the rest of the square with triangles so that (for instance)

1. the sides of the triangles that are partly common with the right side of the square have equal length and

2. the triangles having part of one of their side common with $A$ have equal area.

Answer 3

Are you sure about $n = 5$?

Start with a unit square and remove from it a right triangle of side $\epsilon$ and height 1. You are left with a trapezoid. Divide the trapezoid height-wise into $k$ pieces each of the same area, and chop each sub-trapezoid diagonally into two triangles. Each of the triangles will have area $\approx \frac{1 - \epsilon/2}{2k}$ (but not exact). First optimise to get

$$ \frac{\epsilon}{2} = \frac{1 - \epsilon /2}{2k} \implies \epsilon = \frac{2}{2k+1} $$

It is easy to see that the subtrapezoid with the two horizontal lengths being $1 - \epsilon$ and $1 - \epsilon + h\epsilon$ where $h$ is chosen so that

$$ h \cdot \frac{2 - 2\epsilon + h\epsilon}{2} = \epsilon \tag{h}$$

will be the one divided "most unevenly" by the diagonal cut ($h$ is largest, and so the difference in area between the two triangles is largest). Let us compute the areas of the two sub-pieces. The larger of the two pieces will have area

$$ h \cdot \frac{1 - \epsilon + h\epsilon}{2} = \frac{\epsilon}{2} (1 + \frac{h^2}{2}) $$

by (h). The quadratic formula for (h) implies

$$ h = \frac{1}{\epsilon} \left( \sqrt{1 - 2\epsilon + 3\epsilon^2} - (1-\epsilon)\right) \implies h < \frac{\epsilon}{(1-\epsilon)} = \frac{2}{2k-1}$$

and hence

$$ 1 + \frac{h^2}{2} < \frac{(2k-1)^2 + 2}{(2k-1)^2} $$

For $k = 2$ ($n = 5$) this implies that the largest piece in this decomposition has area

$$ \frac{\epsilon}{2}(1 + \frac{h^2}2) < \frac{1}{5} \frac{11}{9} < \frac{11}{44} = \frac14 $$

So your estimate is not sharp.

Note also that asymptotically the upper bound to the correction term

$$ 1 + \frac{h^2}{2} < 1 + \frac{2}{(2k-1)^2} < 1 + \frac{1}{2k} $$

for all $k> 2$. In fact, the correction decays much faster than the desired correction $1/2k$. So as $n$ gets large the difference between $f(n)$ and $1/(n-1)$ get proportionally bigger. The above example also shows that asymptotically $f(n)$ should approach $1/n$, with a correction that is of order $O(1/n^3)$.

Answer 4

The following picture easily generalizes to show that $f(n)$ asymptotically approaches $1/n$.

The two triangles of area $1/5$ can clearly each be made larger at the expense of the other triangles, in particular decreasing the two of area $21/100$, until those four triangles have equal area. How this compares to Willie Wong's estimates, I haven't worked out. (In case it's not clear, for $n=2k+1$, the generalization has $k$ equal triangles generalizing the two of size $21/100$ and $k-1$ generalizing the one of size $9/50$.)

Added 6/12/13: Aaron Meyerowitz has shown that the construction I gave above is asymptotically kind of crummy compared to the approach described by Tapio Rajala and Willie Wong, and certainly worse than what's implied by the discrepancy results in the paper by Bernd Schulze linked to by Gregor Samsa and Günter M. Ziegler. Its excess over $1/n$ is $O(1/n^2)$, as opposed to $O(1/n^3)$. (Even before the quadratic tweaking to make the largest triangles as small as possible, they have area $(1-4/n^2)/(n-1)$, which is also $O(1/n^2)$ away from $1/n$.)

For $n=5$, however, the construction I gave does give a smaller largest triangle than the alternative, with area

$${\sqrt2-1\over2}\approx0.2071\ldots < {\sqrt{13}-1\over12}\approx0.2171\ldots $$

according to Aaron. (Indeed, even the untweaked area, $21/100$, is smaller.) So I wonder:

Does my (tweaked) construction give the smallest largest triangle for $n=5$?

Note, however, that my (tweaked) construction for $n=5$ does not minimize the discrepancy. That is, while it may minimize the size of the largest triangle for $n=5$, it does not minimize the difference between the largest and smallest triangle. When the four large triangles have area $(\sqrt2-1)/2$, the small triangle has area $3-2\sqrt2$, so the discrepancy is

$${\sqrt2-1\over2}-(3-2\sqrt2) = {5\sqrt2-7\over2}\approx0.0355\ldots \gt 0.03 = {21\over100}-{9\over50}. $$

(I.e., the tweaking made the largest triangle a little bit smaller, but it made the smallest triangle a lot smaller.) My reason for mentioning this is to illustrate the following:

While minimizing discrepancy has obvious implications for minimizing the size of the largest triangle, the two problems are not the same.

To be sure, it's possible this point has already been made. In particular, I haven't looked through the Schulze paper closely. But I thought it might be worth making explicit.

Answer 5

For Barry's construction with two triangle sizes and $n=2k+1$, the $k+1$ large triangles have area $A_k=\frac{1}{k+\sqrt{k^2+4}}$ with $$\frac{1}{2k+\frac{2}{k}} \lt A_k \lt \frac{1}{2k+\frac{2}{k}-\frac{2}{k^3}}.$$ So except for the first few cases, it is much closer to $\frac{1}{2k}$ than to $\frac{1}{2k+1}=\frac1n$.

---

The construction by Tapio and Willie can be tweaked a bit by shifting the lines so as to have $n-1$ equal area large triangles and one small one. Here is an illustration for $n=7$ (oriented for my convenience.) The triangle including $(1,1)$ is going to be the small triangle. Also, the two thin lines are vertical.

The typical triangle with a side on the top clearly has area $$\frac{(x_{j+2}-x_j)(1-mx_{j+1})}{2}$$ for $j$ even. Slightly less obvious is that the same formula with $j$ odd gives the area of triangles with only one corner on the top. Setting the bottom triangle and the $n-3$ leftmost triangles to have equal area determines (for example) each of the $x_i$ in terms of $m$ starting with

${ x1}=m\ $ , ${ x2}={\frac {m}{1-{m}^{2}}}$ , ${ x3}={ \frac {m \left( 2-3{m}^{2} \right) }{1-2{m}^{2}}}$ , ${ x4}={ \frac {m\left( 2-5{m}^{2} \right) }{ \left( 1-m^2\right) \left( 1-3{m}^{2} \right) }}.$ Later values are more complex. For example (for $n \ge 11)$ one has

$ x8=-\frac {m \left( 279m^6-224m^4+54m^2-4 \right) }{ \left(1-m^2 \right) \left( 1-3m^2 \right) \left( 1-5m^2 \right) \left(1-7m^2 \right) }.$

Setting the rightmost large triangle equal to the rest makes $m$ the root of a polynomial with degree $n-3$. At that stage I decided to suffice (for $n \gt 5$) with a numerical solution.

The area of the large triangles for $n=5$ is $\frac{\sqrt{13}-1}{12} \approx 0.2171 \gt \frac{1}{2+\sqrt{8}}=0.2071\cdots$ . For $n=7$ it is approximately $0.148564 \lt \frac{1}{3+\sqrt{3}}=0.1514\cdots.$ And for $n=9$ it is $0.11374 \lt \frac{1}{4+\sqrt{20}} \approx 0.118.$