A plane has a special point $O$ called the origin. Let $P$ be a set of 2021 points in the plane such that no three points in $P$ lie on a line and no two points in $P$ lie on a line through the origin. A triangle with vertices in $P$ is fat if $O$ is strictly inside the triangle. Find the maximum number of fat triangles.
Problem
Source: 2021 EGMO P5
Tags: EGMO 2021, geometry, combinatorial geometry, EGMO, Triangles
13.04.2021 15:18
Note, that $\measuredangle{}$ refers to a directed angle. We instead try to minimize the number of non-fat triangles. Let's consider a non-fat triangle $ABC$, we must have the property that $A,B,C$ are on the same side or on the line for exactly $2$ of the lines $OA,OB,OC$. Now, we can count this is in two ways. Now, let the $2021$ points be $P_1,P_2,\cdots P_{2021}$. For $P_i$, let $a_i$ be the number of points $X$ such that $\measuredangle{P_iOX}$ is not reflex. So, the total number of non-fat triangles is $\frac{\sum\limits_{i=1}^{2021} \binom{a_i}{2}+\binom{2020-a_i}{2}}{2}\ge \sum\limits_{i=1}^{2021}\binom{1010}{2}=2021\cdot \binom{1010}{2}$. Thus, the maximum number of fat triangles are $\binom{2021}{3}-2021\binom{1010}{2} $. Now, we just need to construct a set of points that satisfy these criterion, but that is easy as we can inductively place points so they always have equal number of points on each side of $OP_i$.
13.04.2021 16:12
anser wrote: A plane has a special point $O$ called the origin. Let $P$ be a set of 2021 points in the plane such that no three points in $P$ lie on a line and no two points in $P$ lie on a line through the origin. A triangle with vertices in $P$ is fat if $O$ is strictly inside the triangle. Find the maximum number of fat triangles. Answer - $$ \binom{2021}{3} - \frac{2021 \times 1009\times 1010}{2}$$ Solution - Consider a circle centered at $O$ which contains all points of $P$. Now project all points of $P$ onto this circle and note that the set of fat triangles is exactly same. Now let the points on the circle be $P_1,P_2,\cdots P_{2021}$ , note that a triangle is not fat if and only if it is obtuse. Now we count the obtuse triangles, we do so by taking their largest side. Consider indices mod $2021$. Claim - If $t\leq 1010$ then there are atleast $t-1$ obtuse triangles with largest side $P_i,P_{i+t}$ Proof - There are $t-1$ points on one side of $P_i,P_{i+t}$ and $2021-(t+1)\geq 1010 > t-1$ . So the side of $P_i,P_{i+t}$ not containing $O$ has atleast $t-1$ points but all these give an obtuse triangle. Now we simply sum it up over all $2\leq t \leq 1010$ , note that for each $t$ , $i$ can take any value between $1$ to $2021$ and all those sides are distinct. So we have number of obtuse angled triangles is $\geq 2021(1+2+\cdots +1009) = \frac{2021 \times 1009\times 1010}{2}$ And hence number of fat triangles is $\leq \binom{2021}{3} - \frac{2021 \times 1009\times 1010}{2}$ This bound can be seen to be attained when $P_i$ are vertices of a regular $2021-gon$ Hence proved
13.04.2021 16:28
We claim that the answer is $$\binom{2021}{3} - 2021 \cdot \binom{1010}{2}$$ For any point $A$, consider the line joining $OA$. This partitions the plane into two halves; let there be $k$ points in one half and $2020-k$ points in the other half. If we take two points $B$ and $C$ from the same half, then $\Delta ABC$ cannot contain $O$. Therefore $A$ is a part of at least $$\binom{a}{2} + \binom{2020-a}{2} \ge 2 \cdot \binom{1010}{2}$$non-fat triangles. So we should have at least $2021 \cdot 2 \cdot \binom{1010}{2}$ non-fat triangles. However, this overcounts, and we now adjust it. Now, for each non-fat triangle $XYZ$, exactly two of the vertices $X,Y,Z$ have the property that if we join $O$ to that vertex, thhen the other two vertices are on the same side of this line. Therefore, each non-fat triangle counted above was counted twice, so a true lower bound for the number of non-fat triangles is $2021 \cdot \binom{1010}{2}$. This finishes the proof, except we need to provide an example. A regular $2021$-gon with $O$ as its centre works.
13.04.2021 17:14
13.04.2021 17:27
The answer is $\frac{2020\cdot 2021\cdot 2022}{24}$. We will show that the maximum number of fat triangles with $n$ points is $\frac{(n-1)n(n+1)}{24}$ for odd $n\ge 3$. For the rest of the proof, assume $n$ is odd and $\ge 3$. Part 1: $\frac{(n-1)n(n+1)}{24}$ is achievable with $n$ points. Draw a circle centered at $O$ and place $n$ points on the circle evenly spaced. Call one of the points $A$ and the remaining points $A_1, \dots, A_{n-1}$ going counterclockwise around the circle. We will count the number of fat triangles $A$ is in, multiply by $n$ because all points are symmetric, and divide by 3 because we counted each fat triangle 3 times (once per vertex). Note that a fat triangle containing $A$ must contain exactly one of $A_1, \dots, A_{\frac{n-1}{2}}$ and one of $A_{\frac{n+1}{2}}, \dots, A_{n-1}$. Now suppose $O$ lies inside $AA_iA_j$ for $1\le i\le \frac{n-1}{2}$ and $j > \frac{n-1}{2}$. Also $\angle A_iOA_j = (j-i)\cdot\frac{2\pi}{n} < \pi\iff j\le \frac{n-1}{2} + i$, so there are $i$ possibilities for $j$: the integers in $\left(\frac{n-1}{2}, \frac{n-1}{2} + i\right]$. Now summing over $i$ from 1 to $\frac{n-1}{2}$, there are $1 + 2 + \cdots + \frac{n-1}{2} = \frac{(n-1)(n+1)}{8}$ fat triangles including $A$ and $\frac{(n-1)n(n+1)}{24}$ fat triangles total. Part 2: $\frac{(n-1)n(n+1)}{24}$ is the maximum with $n$ points. We induct on odd $n\ge 3$ with the base case of $n = 3$ clear. Now assume it is true for $n$, and we consider $n+2$. From the set $P$, choose 2 points $X$ and $Y$ such that the acute angle $\angle XOY$ is closest to $\pi$ (if there are multiple possibilities, choose one). As a result, there are no points on lines $OX, OY$ or in the 2 exterior angles of acute $\angle XOY$, or that would contradict $\angle XOY$ closest to $\pi$. Suppose $A$ is the set of $a$ points "contained" on the acute side of $\angle XOY$ and $B$ is the set of $b$ points on the opposite side, where $a+b = n$. The number of fat triangles containing $X$ and $Y$ is at most $b$ because none of the points in $A$ will form a fat triangle with $X$ and $Y$. If a fat triangle contains exactly one of $X$ or $Y$, it must contain a point from $A$ and a point from $B$. For a point $S\in A$ and a point $T\in B$, in order for $XST$ to be fat, $ST$ must intersect line $XO$ on the opposite side of $O$ as $X$, and in order for $YST$ to be fat, $ST$ must intersect line $YO$ on the opposite side of $O$ as $Y$. At most one of these can happen, so there are at most $ab$ fat triangles including exactly one of $X$ or $Y$. All together there are at most $ab + b$ fat triangles with $X$ or $Y$. Since $a+b = n$, $b(a+1)\le \left(\frac{a+b+1}{2}\right)^2 = \left(\frac{n+1}{2}\right)^2$ by AM-GM, with equality possible when $a = \frac{n-1}{2}, b = \frac{n+1}{2}$. Now using the inductive hypothesis on the remaining $n$ points, there are at most $\frac{(n-1)n(n+1)}{24} + \frac{(n+1)^2}{4} = \frac{(n+1)(n+2)(n+3)}{24}$ fat triangles on $n+2$ points, completing the induction.
13.04.2021 19:32
As in other solutions let $A_1,\ldots,A_{2n+1}$ be the points of $P$ in this order around the unit circle. For $i \neq j$ let $\vartheta_{ij}$ be the length of the arc from $A_i$ to $A_j$ going anticlockwise. Let also $\vartheta_{ij}^{\ast}$ be equal to $\vartheta_{ij}$ if $\vartheta_{ij} \in (0,\pi)$ and be equal to $\vartheta_{ij}-2\pi$ otherwise. Observe that $\vartheta_{ij}^{\ast}+ \vartheta_{ji}^{\ast} = 0$ and that for each $i < j < k$ the quantity $\vartheta_{ij}^{\ast} + \vartheta_{jk}^{\ast} + \vartheta_{ki}^{\ast}$ is equal to $2\pi$ or $0$ depending on whether the triangle $A_iA_jA_k$ is fat or not. So if $F$ is the number of fat triangles then \[ 2\pi F = \sum_{i < j < k} (\vartheta_{ij}^{\ast} + \vartheta_{jk}^{\ast} + \vartheta_{ki}^{\ast}) \] Note that with indices modulo $2n+1$, for each $1 \leqslant r \leqslant n$, we have that $\vartheta_{k+r,k}^{\ast} $ occurs $r-1$ times in the above sum and therefore $\vartheta_{k,k+r}^{\ast} $ occurs $(2n-1) - (r-1) = 2n-r$ times. Summing over all those we get $(2n+1-2r)\vartheta_{k,k+r}^{\ast}$. So \[ 2\pi F = \sum_{r=1}^n (2n+1-2r) \sum_{k=1}^{2n+1} \vartheta_{k,k+r}^{\ast} \sum_{r=1}^n\leqslant (2n+1-2r) \sum_{k=1}^{2n+1} \vartheta_{k,k+r} = 2\pi \sum_{r=1}^n r(2n+1-2r) = 2\pi \frac{n(n+1)(2n+1)}{6} \] This is because in $\sum_{k=1}^{2n+1} \vartheta_{k,k+r}$ we go $r$ times around the circle. So $F \leqslant \frac{n(n+1)(2n+1)}{6} $. We have equality if and only if $\vartheta_{k,k+r}^{\ast} = \vartheta_{k,k+r}$ whenever $1 \leqslant r \leqslant k$, i.e. whenever we move $r$ points forwards the angle formed is less than $\pi$. This is the case when e.g. the points of $P$ form a regular $(2n+1)$-gon. One can rephrase the above proof using complex analysis by integrating $1/z$ along all triangles and then summing up. In fact this was the original way in which I discovered this proof but here I tried to make it more accessible omitting any reference to complex analysis.
13.04.2021 19:49
anser wrote: A plane has a special point $O$ called the origin. Let $P$ be a set of 2021 points in the plane such that no three points in $P$ lie on a line and no two points in $P$ lie on a line through the origin. A triangle with vertices in $P$ is fat if $O$ is strictly inside the triangle. Find the maximum number of fat triangles. For every pair of points $P$ and $Q$, draw a directed arrow $P \to Q$ if $\angle POQ$ is labeled clockwise. This gives a tournament on $2021$ vertices, and a triangle is fat if its three edges form a directed cycle. Consequently, by Canada 2006/4, there are at most $\tfrac16 n(n+1)(2n+1)$ fat triangles, where $n = 1010$. Equality occurs if the set of points are the vertices of a regular $2021$-gon containing $O$.
14.04.2021 02:37
14.04.2021 20:36
WLOG, project all to points on $P$ onto a circle centered at $O$ and let this set be $S$. Color all the points in $S$ blue and all the points antipodal to a point in $S$ orange. Call a pair of blue and orange points corresponding if they are antipodal. We claim that the number of fat triangles is maximized when orange and blue points are alternating around the circle. Lemma: Blue points $XYZ$ contain the center iff $Z$ lies in between the corresponding points of $X$ and $Y$. Left as an exercise for the reader I guess. $\square$ Now, assume the orange and blue points are not alternating. Consider a set $T$ of $>1$ consecutive blue points with one orange point directly clockwise to the set of consecutive blue points. Notice that the corresponding points of $T$ is a set of orange points with one blue point. Clearly, swapping corresponding points of $T$ to make both $T$ and the points corresponding to $T$ alternating increases the number of fat triangles. Thus, for every non-alternating arrangement of all the points, the alternating arrangement has more fat triangles. Implying the alternating case is maximal. Noticing that all alternating arrangements have $\binom{2021}{3}-\dfrac{(2021)(1009)(1010)}{2}$ fat triangles, we are done. $\blacksquare$
04.07.2021 13:42
We call a triangle bad if it is not good. Suppose the points in $P$ formed a regular $2021$-gon $V_1V_2...V_{2021}$ with centre $O$. Now notice that each bad triangle are of the form $V_iV_jV_{i+m}$, where $2\leq m\leq 1010$, and $j$ lies between $i+m$. For each $m$, there are $2021$ ways to hoose $i$ and $m-1$ ways to choose $j$, hence the number of bad triangles are $$\sum_{i=1}^{1009}2021i=2021\times\frac{1009\times 1010}{2}\hspace{20pt}(1)$$Therefore, the number of good triangles are $$\binom{2021}{3}-2021\times\frac{1009\times 1010}{2}=\frac{2021}{6}\times\left(2020 \times 2019-3\times 1010\times 1009\right)=\frac{2021\times 1010\times 1009}{6}$$ We now prove the upper bound. The proof of the upper bound is largely inspired by the construction. Indeed, we claim that the number of bad triangles are no less than that in the right hand side of $(1)$. Consider a bad triangle $ABC$, suppose $O$ lies inside $\angle ABC$, we call $A,C$ the good vertices. Now we bound the number of bad triangles with $P_i\in P$ as a good vertex. Indeed, construct the line $P_iO$ and suppose there are $a$ and $b$ points in $P$ lie on the two sides of the line $P_iO$, then $a+b=2020$. Meanwhile, $P_iBC$ is a bad triangle with $P_i\in P$ as a good vertex if and only if $B,C$ lies on different sides of $P_iO$. Therefore, the number of bad triangle with $P_i\in P$ as a good vertex is $$\binom{a}{2}+\binom{b}{2}\geq 2\binom{\frac{a+b}{2}}{2}=2\binom{1010}{2}$$Now notice that each bad triangle is counted twice, so the total number of bad triangles is at least $$\frac{1}{2}\times 2\times 2021\times\binom{1010}{2}$$which is exactly the right hand side of $(1)$ so we are done.
26.08.2021 21:53
Let $P_1,P_2,...,P_{2021}$ be all the points. For each $1 \leq i \leq 2021$, suppose that there are $x_i$ points on the same semiplane WRT $OP_i$ and $y_i$ points on the other semiplane WRT $OP_i$. Clearly, $x_i+y_i=2020 \quad \forall i=1,2,...,2021$. Observe that if $A,B$ are points on the same side WRT $OP_i$, then $ABP_i$ is not a fat triangle. Thus, for each $P_i$, there are at least $\binom{x_i}{2}+\binom{y_i}{2}$ triangles $P_iP_jP_k$ which are not fat. $(*)$ Furthermore, if $ABC$ is a non-fat triangle, there exists an $X \in \{A,B,C\}$ such that the other $2$ vertices in $\{A,B,C\}$ \ $\{X\}$ are on different sides of $OX$, since $O$ is outside $ABC$. $\implies$ from $(*)$, the amount of non-fat triangles is at least $$\sum_{i=1}^{2021} \frac{\binom{x_i}{2}+ \binom{y_i}{2}}{2}$$which by Jensen's Inequality (well-known that $\binom{x}{2}$ is convex) is at least $\sum_{i=1}^{2021} \binom{\frac{2020}{2}}{2}=2021 \binom{1010}{2}$ Therefore, there are at least $2021 \binom{1010}{2}$ non-fat triangles, so there are at most $\binom{2021}{3} - 2021 \binom{1010}{2}$, and for the example we can take a regular $2021-$agon with $O$ as its center, which clearly works.
31.08.2021 01:12
We are able to normalize the lengths $OP_i$ for $P_i \in P$ to magnitude $1$, since it is easy to see that if $P_iP_jP_k$ is fat, then if we scale factor $P_i, P_j, P_k$ down so that $OP_i' = OP_j' = OP_k' = 1$, then $P_i'P_j'P_k'$ is also fat (this is true because whether $O$ lies inside a triangle $ABC$ is only determined by the angles formed between rays $OA, OB, OC$. So WLOG assume $O$ is the origin and all $2021$ points are on the unit circle. Now we count the minimum possible number of non-fat triangles. Note that non-fat triangles have two acute angles and one non-acute angle. We double count based on acute angles. Let $P_i$ be a point, and we count the number of non-fat triangles with it as an acute angle. Say the diameter containing $P_i$ divides the points into two halves, one (for consistency, say the CW side) containing $a_i$ points and the other (for consistency, say the CCW side) $2020 - a_i$ points. There are $\tbinom{a_i}{2} + \tbinom{2020 - a_i}{2}$ non-fat triangles with $P_i$ as one of the two acute angles. Summing over all $P_i \in P$ and finally halving to account for the fact that each non-fat triangle has two acute angles, the total number of non-fat triangles is\[\tfrac12\sum_{i = 1}^{2021} \left[\binom{a_i}{2} + \binom{2020 - a_i}{2}\right].\]Note that each point is on the CW side of $1010$ possible diameters induced by $P_i$, and there are $2021$ points, so $a_1 + \ldots + a_{2021} = 1010 \cdot 2021$. By Jensen's, it follows that$$\tfrac12\sum_{i = 1}^{2021} \left[\binom{a_i}{2} + \binom{2020 - a_i}{2}\right] \geq 2021\cdot\binom{1010}{2}.$$Therefore, our final answer is a maximum number of $\tbinom{2021}{3} - 2021 \cdot \tbinom{1010}{2}$ fat triangles, where equality is achieved when the $2021$ points are equally spaced around the unit circle.
28.12.2022 06:19
Brief Sketch: Minimize non-fat triangles. Select any of the 2021 points, let $x$ and $2020-x$ be the number of points on the two sides of the line joining the selected point with the origin. We can get that there are at least $$\binom{x}{2} + \binom{2020-x}{2}$$nonfat triangles with the selected point as a vertex. Minimize this by Jensens, do this to all $2021$ points, and then divide by $2$, as we counted each nonfat triangle $2$ times. This gives a maximum of $\boxed{\binom{2021}{3} - 2021 \binom{1010}{2}.}$ Construction is a regular 2021-gon centered at $O$.
25.02.2024 10:05
We claim the answer is $\binom{2021}{3}-2021\binom{1010}{2}$. Consider drawing line $\overline{AO}$. Suppose there are $x$ points on one side of the line and $2020-x$ points on the other side. Then there are at least \[\binom{x}{2}+\binom{2020-x}{2}\ge 2\binom{1010}{2}\]bad triangles by Jensen. Note if we sum over all vertices we are counting each bad triangle two times for the two ``outer'' vertices of each triplet. Hence, there are at most $\binom{2021}{3}-\frac12\cdot 2021\cdot 2\binom{1010}{2}$ good triangles, with equality when the points are the vertices of a regular $2021$-gon. $\square$
02.03.2024 11:49
We claim that the answer is $\binom{2021}{3}-2021\binom{1010}{2}$. Construction:Assume that all $2021$ points are on a circle with center $O$.The key here is to notice that all fat triangles are acute,so if we find the minimum number of obtuse triangles we're done.None of the points lie on a diameter,so take point $X$ and let $Y,Z$ be points right next to antipode of $X$.Let the left side have $s$ points and the right side $2018-s$.Then the number of obtuse triangles will be $(s-1009)^2+1009\cdot 1010$ which will be minimum when $s=1009$.Do the same for all other vertices and we get $2021\cdot 505 \cdot 1009$ is the is the minimal amount.So the answer is $\binom{2021}{3}-\frac12\cdot 2021\cdot 2\binom{1010}{2}$.
17.03.2024 23:28
Define the $A$-divider as the line through $O$ and $A$ and let a divided triangle be a triangle $\triangle XYZ$ so that $YZ$ lie on the same side of the $X$-divider. Notice that $\triangle XYZ$ must be non-fat(and vice versa) and that also that $X$ and $Y$ lie on the same side of the $Z$-divider. Then consider some point $A$. Draw the $A$-divider, which divides the plane into $x$ and $2020-x$ points. Then there are $\binom{x}{2} + \binom{2020-x}{2}$ divided triangles that have $A$ as a vertex. By Jensen's, this is at least $2\binom{1010}{2}$. Summing this over all vertices and dividing by $2$(since the triangles are counted twice) we get at least $2021\binom{1010}{2}$. So our answer is $\binom{2021}{3} - 2021\binom{1010}{2}$. This is achieved when $P$ is a regular $2021-$gon centered at $O$.
17.09.2024 04:27
We count the minimum amount of non-fat triangles. Note that for three points $A,B,C$ only the clockwise angles of $OA,OB,OC$ matter. Thus place all $2021$ points on a circle. Note that if there are $x$ points on one side of $OA$ there must be $2020-x$ on the other. Thus the minimum number of non-fat triangles is $\binom{x}{2}+\binom{2020-x}{2}\geq 2\binom{1010}{2}.$ Therefore as each obtuse triangle is counted twice the minimum number of non-fat triangles is $\frac12 \cdot 2021 \cdot 2\binom{1010}{2}=2021 \cdot \binom{1010}{2}.$ Thus our answer is $\binom{2021}{3}-2021\binom{1010}{2},$ which can be achieved by having all points have the quality that there are $1010$ points on each side of that point's diameter$.\blacksquare$
18.10.2024 04:43
We may assume that all the points lie on a circle, from where it suffices to consider the acute triangles. Count pairs $(\mathcal T, A)$ where $\mathcal T$ is an obtuse triangle and $A$ is a point such that the longest side of $\mathcal T$ has $A$ as an endpoint. For each triangle $\mathcal T$, there are two such points $A$, and for each point $A$, there are at least ${1010 \choose 2}$ such triangles $\mathcal T$, as the remaining vertices $B$ and $C$ must be on the same side of $\overline{OA}$. Thus the number of obtuse triangles $\mathcal T$ is at most $2021 {1010 \choose 2}$, and the number of fat triangles is thus at least ${2021 \choose 3} - 2021 {1010 \choose 2}$. Equality occurs at a regular $2021$-gon.
29.12.2024 17:42
a bit messy and could be done simpler but essentially the same as the above ones