Newsgroups: rec.puzzles
From: hoey@aic.nrl.navy.mil (Dan Hoey)
Date: 1995/06/26
Subject: Re: A cute counting problem <yaSPOILER>

[ Please excuse the previous, slightly mistaken version of this
  message. ]

Kanad Chakraborty <ka...@quip.eecs.umich.edu> wrote:
>If there are b boxes, b >= 3, arranged in a circle and we place m
>marbles, m < b, in the boxes in any arbitrary manner, prove that
>there will exist a box without any marbles that is flanked by boxes
>which together contain at most three marbles.

Barry Wolk gives a hint and David Karr gives a solution; here's
a different approach.

<SPOILER>

If there are no marbles, the solution is immediate.  Otherwise, group
the circle into alternating sequences of empty boxes and a like number
of sequences of occupied boxes--there must be at least one of each
kind, since 0 < m < b.  Now whenever there are two adjacent occupied
boxes, remove the less populous box and its marbles; remove either box
in case of a tie.  This removes at least as many marbles as boxes, so
m < b is preserved; it also doesn't decrease the number of marbles in
the empty boxes' neighbors, so it doesn't add any new solutions.

Eventually the occupied sequences will be reduced to singletons.  So
there are exactly as many occupied boxes as there are sequences of
occupied boxes, which are as many as the sequences of empty boxes,
which are no more than e, the number of empty boxes.  Thus e >= b/2.
Count up all the empty boxes' neighbors' marbles.  This counts the
contents of each occupied box twice, since it is the neighbor of two
empties, so we get 2m.  Since 2m < 2b <= 4e, there are fewer than four
times as many marbles in empty boxes' neighbors as there are empty
boxes.  Therefore one of the empties must have neighbors with fewer
than four marbles between them.

OMAR has surely noticed this argument becomes pathological in the case
that there is exactly one empty box.  Of course, the difficulty can be
resolved in a number of ways, perhaps most easily by noting that in
this case each occupied box contains a single marble.

ObPuzzle 1:  So what was Barry's solution, with the lemma of four
boxes containing at least three marbles?

ObPuzzle 2:  Any more neat essentially different solutions?

ObPuzzle 3:  If there are b boxes containing fewer than kb marbles
between them, show an upper bound for the minimum number of marbles in
the neighbors of a box containing fewer than k marbles.  Or should we
be bounding the marbles in that box together with its neighbors?

Dan
Hoey@AIC.NRL.Navy.Mil