Let $n \geq 3$ and $k \geq 1$. Determine the smallest integer $\ell$ with the following property:

For any convex polygon $\mathcal{P}$ with $n$ vertices and $A$ a set of $k$ points inside $\mathcal{P}$, there exists an $\ell$-gon whose vertices are vertices of $\mathcal{P}$ and which contains all the points of $A$.
The answer is $\ell=3$ if $k=1$, $\ell=2k$ if $2 \leq k \leq \frac{k}{2}$, and $\ell=n$ if $k>\frac{n}{2}$. For $k=1$, a triangle is necessary and is always sufficient (it suffices to triangulate the polygon).

For $k>\frac{n}{2}$, it is possible to take a point from $A$ just next to every other side: we are then forced to take the two endpoints of each of these sides, thus taking all the vertices. Of course, $n$ vertices are always sufficient.

Similarly, for $2 \leq k \leq \frac{n}{2}$, we can take in $A$ vertices "stuck" to $k$ different non-adjacent sides of $\mathcal{P}$, which forces us to take at least $2k$ vertices to enclose them all. It remains to show that $2k$ vertices are always sufficient.

For this, we reason by induction on $k$: for $k=2$, we draw the line passing through the two points of $A$. It intersects two sides of $\mathcal{P}$, which we denote as $\left[P_{i} P_{i+1}\right]$ and $\left[P_{j} P_{j+1}\right]$. We then take the quadrilateral (it might be a triangle) with vertices $P_{i}, P_{i+1}, P_{j}$, and $P_{j+1}$.

If the result is true for $k$, let $A$ be a set of $k+1$ points inside $\mathcal{P}$ and let $x$ be a point in $A$. Applying the induction hypothesis to $A \backslash\{x\}$ gives a $2k$-gon. If $x$ is inside the $2k$-gon, we are done. Otherwise, let $y \neq x \in A$: we draw the line connecting $x$ to $y$. It intersects $\mathcal{P}$ at two points. We focus on the one that is "on the side of $x$ " (relative to $y$). It is on the side $P_{\ell} P_{\ell+1}$. We then add $P_{\ell}$ and $P_{\ell+1}$ to our $2k$-gon.