Let $n\ge 3$ be an integer. Consider $n$ points in the plane, no three lying on the same line, and a squirrel in each one of them. Alex wants to give hazelnuts to the squirrels, so he proceeds as follows: for each convex polygon with vertices among the n points, he identifies the squirrels which lie on its sides or in its interior and gives to each of these squirrels q hazelnuts, where q is their number. At the end of the process, a squirrel with the least number of hazelnuts is called unlucky. Determine the maximum number of hazelnuts an unlucky squirrel can get. (proposed by Cristi Savesku)
Problem
Source: Bulgarian Autumn Tournament 2024, p11.3
Tags: combinatorics
20.11.2024 18:43
I am Anaphylactic to them
21.11.2024 20:04
I might be very foolish right now but is there a reason that taking a regular $n$-gon gives the construction and taking a squirrel on the convex hull gives the bound.
21.11.2024 23:27
@above: So, what's the question? I didn't get it.
05.12.2024 00:49
tyrantfire4 wrote: I am Anaphylactic to them
20.12.2024 17:37
I posted the official (author's) solution in my blog. Here is another approach used by a contestant, unfortunately he didn't finish this idea. So, we want to get an upper bound for the number of hazelnuts that an unlucky squirrel gets. Let $X$ be a set of $n$ points on the plane. Let us take a point $A\in X$, which is a vertex of the convex hull of $X$. Let $Q_A$ be the number of hazelnuts received by the squirrel at $A$. Note that $A$ is a vertex in any convex polygon $P$ with vertices in $X$ that covers $A$. Let $P'$ be the set of other vertices of $P$ (excluding $A$). The number $k$ of possible vertices of $P'$ is $k=2,3,\dots, n-1$. We have $$Q_A\le \sum_{k=2}^{n-1}(k+1)\binom{n-1}{k}=(n+2)2^{n-2}-2n+1\qquad(1).$$Let $m$ be the number of hazelnuts that an unlucky squirrel gets. Obviously, $m\le A_A$. Therefore $$m\le (n+2)2^{n-2}-2n+1 \qquad(2).$$Let's dispose the squirrels at vertices of a regular $n$-gon. By the symmetry, each squirrel gets equal number of hazelnuts. Observe that in this case we have equality in (1), so each squirrel gets $m=(n+2)2^{n-2}-2n+1$ hazelnuts, which together with (2) shows that this is the maximum possible number of hazelnuts that an unlucky squirrel can get.