49
$\begingroup$

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$?

$\endgroup$
3
  • 4
    $\begingroup$ It seems Bernd Schulze has published related results, see maths.lancs.ac.uk/~schulzeb/index_dateien/… $\endgroup$ Jun 10, 2013 at 19:57
  • 1
    $\begingroup$ The above paper also gives only upper bounds, apparently the same as Willie got. It seems that Gunter Ziegler has already posed a similar question to mine in 2003 but there is no citation for it. $\endgroup$
    – domotorp
    Jun 11, 2013 at 7:45
  • 2
    $\begingroup$ You should add the link to Monsky's theorem and mention that the proof (if I correctly remember) is using 2-adic numbers. $\endgroup$ May 3, 2018 at 13:24

5 Answers 5

33
$\begingroup$

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

$\endgroup$
3
  • 4
    $\begingroup$ So there are some known lower bounds! Could you give some reference to what kind of gap-theorems you have in mind? I know practically nothing about this topic... $\endgroup$
    – domotorp
    Jun 12, 2013 at 14:36
  • 6
    $\begingroup$ Finally Jean-Philippe Labbé, Günter Rote and I have finished our paper on area difference bounds for subdivisions into an odd number of triangles -- including doubly-exponential lower bounds and superexponential lower bounds: See arxiv.org/abs/1708.02891 $\endgroup$ Sep 8, 2017 at 6:10
  • 1
    $\begingroup$ That paper has been published as Area difference bounds for dissections of a square into an odd number of triangles, Experimental Mathematics, May 2018, pp 1 to 23. DOI: 10.1080/10586458.2018.1459961 $\endgroup$ May 17, 2018 at 0:00
22
$\begingroup$

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.

dissection

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.

$\endgroup$
1
  • $\begingroup$ Good point, I did not analyze n=5 careful enough... $\endgroup$
    – domotorp
    Jun 10, 2013 at 10:37
11
$\begingroup$

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)$.

$\endgroup$
2
  • $\begingroup$ Thank you, in fact Tapio also gave a similar counterexample, but without calculating the bounds. $\endgroup$
    – domotorp
    Jun 10, 2013 at 13:47
  • $\begingroup$ Yes, I noticed. :-) I started writing before he posted and took a lunch break in between. Fortunately I forgot that MO is still not on the SE2 network and I won't get notified if someone else writes an answer while I am composing mine; otherwise you may not have seen the bounds. $\endgroup$ Jun 10, 2013 at 13:55
9
$\begingroup$

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

dissection

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.

$\endgroup$
8
$\begingroup$

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.

enter image description here

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.