Problem: Let $m$ and $n$ be positive integers with $m\geq n$.
There are $m$ cupcakes of different flavors arranged around a circle
and $n$ people who like cupcakes.
Each person assigns a nonnegative real number score to each cupcake,
depending on how much they like the cupcake.
Suppose that for each person $P$, it is possible to partition the circle
of $m$ cupcakes into $n$ groups of consecutive cupcakes
so that the sum of $P$'s scores of the cupcakes in each group is at least $1$.
Prove that it is possible to distribute the $m$ cupcakes to the $n$ people
so that each person $P$ receives cupcakes of total score at least $1$ with respect to $P$.

\end{enumerate}

Solution: Arbitrarily pick any one person --- call her Pip --- and her $n$ arcs.
The initial idea is to try to apply Hall's marriage lemma to match
the $n$ people with Pip's arcs (such that each such person is happy with their matched arc).
To that end, construct the obvious bipartite graph $\mathfrak{G}$
between the people and the arcs for Pip.

We now consider the following algorithm, which takes several steps.
\begin{itemize}
  \ii If a perfect matching of $\mathfrak{G}$ exists, we're done!

  \ii We're probably not that lucky.
  Per Hall's condition, this means there is a \emph{bad set} $\mathcal{B}_1$ of people,
  who are compatible with fewer than $|\mathcal{B}_1|$ of the arcs.
  Then delete $\mathcal{B}_1$ and the neighbors of $\mathcal{B}_1$,
  then try to find a matching on the remaining graph.

  \ii If a matching exists now, terminate the algorithm.
  Otherwise, that means there's another bad set $\mathcal{B}_2$
  for the remaining graph.
  We again delete $\mathcal{B}_2$ and the fewer than $\mathcal{B}_2$ neighbors.

  \ii Repeat until some perfect matching $\mathcal{M}$ is possible in the remaining graph,
  i.e.\ there are no more bad sets (and then terminate once that occurs).

  Since Pip is a universal vertex, it's impossible to delete Pip,
  so the algorithm does indeed terminate with nonempty $\mathcal{M}$.
\end{itemize}

A cartoon of this picture is shown below.
\begin{center}
\begin{asy}
  size(8cm);
  dotfactor *= 1.3;
  real w = 3;
  real eps = 0.4;
  label("People", (-w,10));
  label("Arcs of Pip", (w,10));
  filldraw(box((-w-eps, 9+eps), (-w+eps,7-eps)), opacity(0.1)+lightred, red+1.2);
  filldraw(box((-w-eps, 6+eps), (-w+eps,5-eps)), opacity(0.1)+lightred, orange+1.2);
  filldraw(box((-w-eps, 4+eps), (-w+eps,2-eps)), opacity(0.1)+lightred, brown+1.2);

  filldraw(box((w-eps, 9+eps), (w+eps,8-eps)), opacity(0.1)+lightred, red+1.2);
  filldraw(box((w-eps, 7+eps), (w+eps,7-eps)), opacity(0.1)+lightred, orange+1.2);
  filldraw(box((w-eps, 6+eps), (w+eps,5-eps)), opacity(0.1)+lightred, brown+1.2);

  draw((-w+eps, 9+eps)--(w-eps, 9+eps), red+dashed);
  draw((-w+eps, 7-eps)--(w-eps, 8-eps), red+dashed);
  draw((-w+eps, 6+eps)--(w-eps, 9+eps), orange+dashed);
  draw((-w+eps, 5-eps)--(w-eps, 7-eps), orange+dashed);
  draw((-w+eps, 4+eps)--(w-eps, 9+eps), brown+dashed);
  draw((-w+eps, 2-eps)--(w-eps, 5-eps), brown+dashed);

  label((-w-eps, 8), "Bad set $\mathcal{B}_1$", dir(180), black);
  label((-w-eps, 5.5), "Bad set $\mathcal{B}_2$", dir(180), black);
  label((-w-eps, 3), "Bad set $\mathcal{B}_3$", dir(180), black);

  draw((-w,1)--(w,1), deepgreen+1.3);
  draw((-w,0)--(w,0), deepgreen+1.3);
  label((0, 0.5), "Final perfect matching $\mathcal{M}$", deepgreen);

  for (int i=0; i<10; ++i) {
    dot((w,i), blue);
    dot((-w,i), blue);
  }
  label("Pip", (-w,0), dir(180), blue);
\end{asy}
\end{center}
We commit to assigning each of person in $\mathcal{M}$ their matched arc
(in particular if there are no bad sets at all, the problem is already solved).
Now we finish the problem by induction on $n$
(for the remaining people) by simply deleting the arcs used up by $\mathcal{M}$.

To see why this deletion-induction works,
consider any particular person Quinn not in $\mathcal{M}$.
By definition, Quinn is not happy with any of the arcs in $\mathcal{M}$.
So when an arc $\mathcal{A}$ of $\mathcal{M}$ is deleted,
it had value less than $1$ for Quinn
so in particular it couldn't contain entirely any of Quinn's arcs.
Hence at most one endpoint among Quinn's arcs was in the deleted arc $\mathcal{A}$.
When this happens, this causes two arcs of Quinn to merge, and the merged value is
\[ (\ge 1) + (\ge 1) - (\le 1) \qquad \ge \qquad 1 \]
meaning the induction is OK.
See below for a cartoon of the deletion,
where Pip's arcs are drawn in blue while Quinn's arcs and scores are drawn in red
(in this example $n=3$).
\begin{center}
\begin{asy}
  size(13cm);
  usepackage("amsmath");
  pair O = (0,0);
  picture before;
  picture after;

  real r = 1;
  real s = 0.9;
  real t = 0.65;

  draw(before, arc(O, s, -20, 80), red+1.3);
  draw(before, arc(O, s, 100, 200), red+1.3);
  draw(before, arc(O, s, 220, 320), red+1.3);

  draw(before, "Pip arc to delete", arc(O, r,  40, 140), blue+1.3);
  draw(before, rotate(-60)*"Pip arc", arc(O, r, 160, 260), blue+1.3);
  draw(before, rotate( 60)*"Pip arc", arc(O, r, 280, 380), blue+1.3);

  label(before, "$\boxed{0.2}$", t*dir(120), red);
  label(before, "$\boxed{0.3}$", t*dir( 60), red);
  label(before, "$\boxed{0.8}$", t*dir(180), red);
  label(before, "$\boxed{0.43}$", t*dir(240), red);
  label(before, "$\boxed{0.57}$", t*dir(300), red);
  label(before, "$\boxed{0.7}$", t*dir(  0), red);
  label(before, minipage("\centering Quinn's \\ values", 3cm), O, red);

  draw(after, arc(O, s, -20, 200), red+1.3);
  draw(after, arc(O, s, 220, 320), red+1.3);

  draw(after, rotate(-60)*"Pip arc", arc(O, r, 160, 260), blue+1.3);
  draw(after, rotate( 60)*"Pip arc", arc(O, r, 280, 380), blue+1.3);

  label(after, "$\boxed{0.8}$", t*dir(180), red);
  label(after, "$\boxed{0.43}$", t*dir(240), red);
  label(after, "$\boxed{0.57}$", t*dir(300), red);
  label(after, "$\boxed{0.7}$", t*dir(  0), red);
  label(after, minipage("\centering Quinn's \\ values", 3cm), O, red);

  add(before);
  add(shift(3.2,0)*after);
\end{asy}
\end{center}

\begin{remark*}
  This deletion argument can be thought of in some special cases even
  before the realization of Hall, in the case where $\mathcal{M}$ has only one person (Pip).
  This amounts to saying that if one of Pip's arcs isn't liked by anybody,
  then that arc can be deleted and the induction carries through.
\end{remark*}
\begin{remark*}
  Conversely, it should be reasonable to expect Hall's theorem to be helpful
  even before finding the deletion argument.
  While working on this problem, one of the first things I said was:
  \begin{quote}
    ``We should let Hall do the heavy lifting for us:
    find a way to make $n$ groups that satisfy Hall's condition,
    rather than an assignment of $n$ groups to $n$ people.''
  \end{quote}
  As a general heuristic, for any type of ``compatible matching'' problem,
  Hall's condition is usually the go-to tool.
  (It is much easier to verify Hall's condition than actually find the matching yourself.)
  Actually in most competition problems, if one realizes one is in a Hall setting,
  one is usually close to finishing the problem.
  This is a relatively rare example in which one needs an additional idea
  to go alongside Hall's theorem.
\end{remark*}