Let $\triangle ABC$ be a triangle, and let $P_1,\cdots,P_n$ be points inside where no three given points are collinear. Prove that we can partition $\triangle ABC$ into $2n+1$ triangles such that their vertices are among $A,B,C,P_1,\cdots,P_n$, and at least $n+\sqrt{n}+1$ of them contain at least one of $A,B,C$.
Problem
Source: 2023 China TST Problem 5
Tags: geometry, combinatorics, China TST
15.03.2023 03:45
15.03.2023 18:19
Was it given that any three points cannot lie on the same line?
19.03.2023 05:31
19.03.2023 17:28
I believe your solution is incomplete, because having sqrt(n) points in increasing order left to right doesn’t necessarily mean that you can connect them like you did in your example.
19.03.2023 19:29
R8kt wrote: I believe your solution is incomplete, because having sqrt(n) points in increasing order left to right doesn’t necessarily mean that you can connect them like you did in your example. Sorry, what is the problem in such a connection?
19.03.2023 20:00
I assumed he used Erdos to get that the points are in increasing order. But this doesn’t work on examples like this:
Attachments:

20.03.2023 01:31
But you can first label the points by looking at them from A, i.e.WLOG $\angle P_iAB<\angle P_{i+1}AB$
20.03.2023 01:49
Ok. I understand now. Great solution.
28.10.2024 04:58
I believe E-S is not that natural, equivilantly using Dilworth Theorem is better to understand. Let $V=\{P_1,\ldots ,P_n\}.$ The poset $P=(V,\preceq)$ is defined as follows: $\forall v\in V,$ $v\preceq v.$ For $v\neq w\in V,$ $v\preceq w$ iff ${\triangle}AvC\subseteq \triangle AwC.$ ow by Mirsky Theorem or by Dilworth Theorem we can both get $L\cdot A\ge |V|=n,$ where $L$ is the length of longest chain, and $A$ is the size of maximum antichain. Therefore $\max\{L,A\}\ge\sqrt n.$ Note that an antichain becomes a chain after swapping $B,C,$ so we only need to consider a chain with length at least $\sqrt n.$ And this is just using @a22886 graph, There are $2L+1$ good triangles now and every other point adds at least one good triangle so there are at least$$(2L+1)+(n-L)=n+L+1\ge n+\sqrt{n}+1$$good triangles.$\Box$