Distribution of hazelnuts in a special convex way

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Distribution of hazelnuts in a special convex way

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Bulgarian Autumn Tournament 2024, p11.3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2459 posts

#1 h Nov 20, 2024, 3:35 PM • 1 Y

Y by Rounak_iitr

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)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1022 posts

#2 h Nov 20, 2024, 3:43 PM

Y by

I am Anaphylactic to them

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1482 posts

#3 h Nov 21, 2024, 5:04 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2459 posts

#4 h Nov 21, 2024, 8:27 PM

Y by

@above: So, what's the question? I didn't get it.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1022 posts

#7 h Dec 4, 2024, 9:49 PM

Y by

tyrantfire4 wrote:

I am Anaphylactic to them

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2459 posts

#8 h Dec 20, 2024, 2:37 PM

Y by

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.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a