There will always be adjacent slices summing to 9 on pentagon

Question

Consider a circle divided into $5$ parts radially.

Suppose we have $21$ beads that we place, distributing however we like among the $5$ regions.

The claim is that there is always a pair of adjacent sectors whose union has $9$ or more beads.

My work

I took an experimental approach to this:

I begin by simplifying the problem greatly if we consider a circle split into $3$ parts with $3$ beads, then there is always a pair of adjacent sectors that sum to $2$ (this can be checked by casework)

If we increase the bead count to $4$ beads, then case work again can verify that there is always a pair of adjacent sectors that sum to $3$.

If we increase to $5$ beads, it seems that we can always form adjacent sectors that sum to $4$. This hints at a proof by induction that given $3$ sectors, and $K$ beads its always possible to find a pair of adjacent sectors that sum to $\left\lceil \dfrac{2}{3} K \right\rceil$ (consider the case where we take the largest multiple of $3$ less than $K$, split evenly by it (clearly $\dfrac{2}{3}K$ is possible here) Then distribute the remainder beads, giving $+1$ either way if we attempt to minimize the sum of pairs of adjacent sides)

Now we consider splitting into $4$ parts instead of $5$, but I realized if I continue this analysis this way it was getting messy, and certainly not a $30$ second aha! that one would expect from the math GRE subject test.

Is there some way to use pigeonhole to do this quickly?

Answer 1

Label the regions as $A_1, A_2, A_3, A_4, A_5$ in order of appearance. We then have the constraints:

$A_1 + A_2 \le 8$

$A_2 + A_3 \le 8$

$A_3 + A_4 \le 8$

$A_4 + A_5 \le 8$

$A_5 + A_1 \le 8$

Adding these up, we get that $2 \times (A_1 + A_2 + A_3 + A_4 + A_5) \le40$, but we know that the sum of the number of beads in all the regions is $21$, and $2$ times that is $42$, which allows us to see that it's not possible.

Answer 2

Yes, pigeonhole works super quickly: how can you maximize the number of beads to not get 9 beads in adjacent regions? By putting $4$ in each ... (putting more than $4$ in one region and having $8$ maximum for adjacent doesn't even get you to $20$ when going around)

Answer 3

Let $x_1,\dots,x_5$ be the number of beads in each sector. If there are at most $8$ beads in any two adjacent sectors, then $\sum_i (x_i+x_{i+1 \bmod 5})\leq 40$ and so $\sum_i x_i \leq 20$.

Answer 4

This goes along the lines of the solution by @Green, but with an explicit use of pigeonhole principle.

Let $A_1$ through $A_5$ denote number of beads in five sectors.
Let in turn $B_i=A_i+A_{i+1}$ (with $B_5=A_5+A_1$of course) denote sums considered.

Then $\sum_iB_i = 2\cdot\sum_iA_i = a\cdot 21=42$

Now we have $42$ beads distributed among five $B$ pigeonholes.
Of course not all such distributions are possible. Every bead in any $A_i$ hole counts into two $B$ holes, namely to $B_i$ and to $B_{i-1}$ (with $B_0$ being the same as $B_5$), so, for example, we can't have $B_3=10$ with $B_2=B_4=0$. Anyway each possible distribution of $21$ beads over $A_1,\dots A_5$ generates one of possible distributions of $42$ among $B_1,\dots B_5$.

And from the generalized pigeonhole principle, if we distribute $N=42$ beads over $k=5$ holes, then there is at least one hole containing at least $$\left\lceil\frac Nk\right\rceil = \left\lceil\frac {42}5\right\rceil = \left\lceil 8.4\right\rceil = 9$$ beads. $\blacksquare$