Replace $16$ with $2n$. We claim the answer is $C_n$, proceeding by induction. Equality is at all points on a circle. Pick some point $P$ on the convex hull of $S_n$. We see that \[\chi(S_n)\ge \chi(S_0)\chi(S_{n-1})+\cdots+\chi(S_0)\chi(S_{n-1})\ge C_{n-1}C_0+\cdots+C_0C{n-1}=C_n,\]so we finish by induction. Thus, the answer is $\boxed{C_8=1430}$.

Not saying $A$ lies on the convex hull $\implies$ 3. The answer is $\boxed{1430}$. Let $C_n$ denote the minimum possible value of $\chi(S)$ when there are $2n$ points. Claim. $C_n$ and $\chi(\mathcal S)$ are related as follows: $\chi(\mathcal S)\ge C_n=\sum_{k=0}^{n-1}C_kC_{n-1-k}$. $\chi(\mathcal S)=C_n$ when $\mathcal S$ is a convex $2n$-gon. Proof. Let $A$ be a point on the convex hull of $\mathcal S$, and let $B$ be the other endpoint of the segment incident to $A$. Suppose that line $AB$ splits the plane into two half-planes containing $k$ and $n-1-k$ points respectively. If $k$ is odd, then there are clearly at least $C_kC_{n-1-k}$ ways to draw the segments, so $$\chi(\mathcal S)\ge\sum_{k=0}^{n-1}C_kC_{n-1-k},$$as requested. Equality occurs when $\mathcal S$ is a convex $2n$-gon, as nothing can cross segment $AB$ and $\overline{AB}$ splits $\mathcal S$ into two convex sets. $\blacksquare$ Since $C_0=C_1=1$, $C_n$ is the $n^\text{th}$ Catalan number, so $C_8=\tfrac19\tbinom{16}8=1430$, the answer. $\square$

Wait this is actually REALLY easy... How did this become a TST #2?

RickyJin wrote: Wait this is actually REALLY easy... How did this become a TST #2? I also agree that this is very easy problem. However some MOP graders said that this is #8 because if it would be significantly more difficult if student does not know the Catalan number. But the statistic shows that this turns out to be false as this problem received more solves than #1, #4.

MarkBcc168 wrote: However some MOP graders said that this is #8 because if it would be significantly more difficult if student does not know the Catalan number. But the statistic shows that this turns out to be false as this problem received more solves than #1, #4. My justification for putting this as #8 is that it's a problem where an unlucky student could potentially simply not see the recursion idea and thus make no progress at all no matter how much time they spent. Whereas problems like #1, #4, #7 are things that are easier to fight with and make progress on, even if not necessarily easier to solve. (And indeed there were a couple of 707's on Day 3.) In hindsight, I think I wasn't wrong about the difficulty of this problem --- it got about as many solves as I would have guessed --- but I greatly underestimated the difficulty of #1 and #4 (and #2 for that matter, which I had thought was about the same difficulty as #1). We did also consider students who didn't know Catalan, which is why we chose a small number $16$ so the recursion was tractable by hand without knowing (or proving) the closed form. Fun unrelated remark: if you replace $16$ by $6$, a pentagon with its center achieves equality too, so the equality cases are not just convex polygons.

v_Enhance wrote: My justification for putting this as #8 is that it's a problem where an unlucky student could potentially simply not see the recursion idea and thus make no progress at all no matter how much time they spent. Whereas problems like #1, #4, #7 are things that are easier to fight with and make progress on, even if not necessarily easier to solve. I agree that this problem depended mainly on seeing the recursion - however, I believe the recursion wasn't necessarily that difficult to find. Trying smaller cases of $4$ and $6$ points would lead to the idea that $\chi(S)$ would likely be minimized for a convex polygon - computing $\chi(S)$ would then require recursion if one didn't know the Catalan number, and the idea would then naturally extend to the case of points being inside the convex hull. Personally, though, I first tried to find an invariant or monovariant when points were moved from on the convex hull to inside, which clearly didn't work, and it took me perhaps 40 minutes to realize the recursion. As for #1, the issue might be that too many people (me included ) don't have enough experience with FEs. For someone experienced with FEs, it would be relatively straightforward to prove injectivity and surjectivity, and then reduce to the 1-variable FE. Then the issue becomes one of rigor - one has to know the Cauchy FE and/or a continuity argument quite thoroughly in order to earn a 7, and a slight slip-up could easily knock that to a 3 or 4 (or even 1 ). For #4, I feel that seeing the idea of gaps and/or switches wasn't easy, and other methods (fighting in the wrong direction ) would likely lead to futile attempts. I was under the misconception that $C$ would be maximized when all $\binom{99}{49}$ sets of $50$ sums involving the largest element were greater than $25$, which gave the (common?) incorrect answer of $\frac{50}{99}$. In addition, it was not immediately obvious whether engineer's induction on $4k+2$ coins would also give useful insight or whether only the $4k$ coin cases would - it turns out that the $4k+2$ cases are different, and that trying only the $2, 4, 6$ coin cases could easily lead one to believe $\frac{n}{2n-1}$ to be the correct answer instead of $\frac{n}{n+1}$. Personally I think that switching this and #4 might lead to a slightly better test in general. But again keeping this as #8 gives an all-Ankan day which is definitely worth it

v_Enhance wrote: My justification for putting this as #8 is that it's a problem where an unlucky student could potentially simply not see the recursion idea and thus make no progress at all no matter how much time they spent. Whereas problems like #1, #4, #7 are things that are easier to fight with and make progress on, even if not necessarily easier to solve. (And indeed there were a couple of 707's on Day 3.) In hindsight, I think I wasn't wrong about the difficulty of this problem --- it got about as many solves as I would have guessed --- but I greatly underestimated the difficulty of #1 and #4 (and #2 for that matter, which I had thought was about the same difficulty as #1). We did also consider students who didn't know Catalan, which is why we chose a small number $16$ so the recursion was tractable by hand without knowing (or proving) the closed form. I feel like v_Enhances's statement is pretty significant, 1/4's are supposed to be solvable by anybody as long as you keep on trying basic stuff and don't give up. However with 2/5's, you can go down the wrong path and never reach the answer. So combo 2/5s aren't necessarily that much more difficult than 1/4s, but you have to be careful if something is not working out/getting ugly to pull out. I would argue that #4's idea was not hard to reach. The fact that the sum is exactly 50 is super contrived and should hint that the solution will also have a weird flavor. Myself and a lot of other contestants(that I talked to) spent a lot of time trying stuff and eventually making our way to the solution. It is very hard to see what the solution would be like at the start, but just playing with locally optimal states should eventually point you to a solution. There are very few wrong paths that will lead you in a totally wrong direction. As long as you keep your nose sharp, you will find the solution eventually.

pandadude wrote: v_Enhance wrote: My justification for putting this as #8 is that it's a problem where an unlucky student could potentially simply not see the recursion idea and thus make no progress at all no matter how much time they spent. Whereas problems like #1, #4, #7 are things that are easier to fight with and make progress on, even if not necessarily easier to solve. (And indeed there were a couple of 707's on Day 3.) In hindsight, I think I wasn't wrong about the difficulty of this problem --- it got about as many solves as I would have guessed --- but I greatly underestimated the difficulty of #1 and #4 (and #2 for that matter, which I had thought was about the same difficulty as #1). We did also consider students who didn't know Catalan, which is why we chose a small number $16$ so the recursion was tractable by hand without knowing (or proving) the closed form. I feel like v_Enhances's statement is pretty significant, 1/4's are supposed to be solvable by anybody as long as you keep on trying basic stuff and don't give up. However with 2/5's, you can go down the wrong path and never reach the answer. So combo 2/5s aren't necessarily that much more difficult than 1/4s, but you have to be careful if something is not working out/getting ugly to pull out. I would argue that #4's idea was not hard to reach. The fact that the sum is exactly 50 is super contrived and should hint that the solution will also have a weird flavor. Myself and a lot of other contestants(that I talked to) spent a lot of time trying stuff and eventually making our way to the solution. It is very hard to see what the solution would be like at the start, but just playing with locally optimal states should eventually point you to a solution. There are very few wrong paths that will lead you in a totally wrong direction. As long as you keep your nose sharp, you will find the solution eventually. And I spent 3 hours and didn’t solve

Solution with hint from stroller. Let $f(N)$ denote the answer for this problem when $16$ is replaced by $2N$ and $8$ by $N$. Let $\mathcal{C}$ be the set of points in the convex hull of the full set of points. Let $C$ be some point in $\mathcal{C}$. Enumerate the points besides $C$ as $D_1,\dots , D_{2N-1}$ clockwise. Remark that if $C$ is connected to $D_1$, then there are at least $f(N-1)$ possibilities. Observing similar results yields that \[f(N) \ge \sum_{i=1}^{N-1} f(i)\cdot f(N-1-i).\]But this is the Catalan recursion; as $f(0)=f(1) = 1$, we must get that $f(N) \ge c_{N+1}$ for all $N$ where $c_N$ is the $N$-th Catalan Number. It is well-known that $\chi (\mathcal{S})$ when $\mathcal{S}$ is its own convex hull is $c_{N+1}$, hence the minimum of $c_{N+1}$ is attainable and \[\min_{\mathcal{S}}\chi (\mathcal{S}) = c_9 = \fbox{1430}.\]

Wrong

The answer is $1430$. Denote the answer for $2n$ points as $C_n$. Let $A$ be any point on the convex hull; consider the points $X$ such that line $AX$ splits the plane into two regions each containing an even number of points. Then summing across all choices of $X$ shows that $$C_n \ge C_0C_{n-1}+C_1C_{n-2}+ \cdots + C_{n-1}C_0.$$This is an equality when the points form a convex $2n$-gon. Computation of the recursion is left to the reader.

The answer is $1430$. Indeed, suppose there answer is $a_n$ when $16$ is replaced by $2n$. Obvioulsy $a_0=a_1=1$. We now show that $$a_n\geq\sum_{i=0}^na_ia_{n-i-1} \hspace{20pt}(1)$$Indeed, pick angle $\angle ABC$ on the convex hull of $S$. Suppose when the ray $BA$ is rotating to $BC$ it intersect the points in the order $A=V_0,V_1,...,V_{2n-1}=C$. Now we show that the number of ways where $B$ is connected with $V_{2i}$ connected is at least the right hand side of $(1)$. Indeed, the line $BV_{2i}$ will divide the remaining points into two groups of $2i$ and $2n-2-2i$ points, hence we can connect the remaining points by $a_ia_{n-i-1}$, summing over $i$ yields the result. Now, notice that if the points in $S$ formed a convex polygon, then $B$ can only connect to $V_{2i}$. Since suppose $B$ is connected to $V_i$, then $V_a$ where $a<i$ cannot connect to $V_b$ where $b>i$. Therefore, $i$ must be even. Moreover, when $V_i$ is even there are exactly $a_{2i}a_{n-i-1}$ ways, summing through $i$ yields the result. Now a easy computation show that $a_8=1430$.

Feedback would be greatly appreciated, thanks!

Lemma : $\sum C_{n-1-k}C_k = C_n$ Claim 1: $\chi(\mathcal S)\ge C_n=\sum_{k=0}^{n-1} \chi{(k)} \chi{(n-1-k)}$ Proof: Let $X$ be a point on convex hull formed, $Y$ be a point incident to $X$, then they divide into $k$ and $n-1-k$ points, the result follows. Hence the answer is $C_8 =1430$

Replacing $16$ with $2n$, we will show that the answer is the $n$th Catalan number $C_n$. We will argue inductively to show the bound. In particular, fix some point $A$ and consider any segment $\overline{AB}$ that we choose. The segment $\overline{AB}$ splits the set of points into two sets of cardinality $k$ and $2n-2-k$. Evidently, for $k$ even, it is possible to construct two such sets for each of the sets, yielding at least $C_{k/2} C_{n-1-k/2}$ ways to construct the segments. In particular, equality occurs when $\mathcal S$ is a regular $2n$-gon.

Let $f(n)$ be the answer for $2n$ points. Pick a point $X$ on the convex hull. Order the points based on the angle the segment from that point to $X$ makes. When $X$ is connected to the $2i+1$th point, the line splits the points into two groups of sizes $2i$ and $2n-2-2i$, which gives at least $f(i)f(n-1-i)$ possibilities. Therefore, $f(n)\geq\sum_{i=0}^{n-1}f(i)f(n-1-i)$, so $f(n)$ is at least the $n$th Catalan number. Equality holds when the points form a convex polygon. When $n=8$, this means $f(n)=\boxed{1430}$.