2025 USAMO Problems/Problem 6
Contents
[hide]Problem
Let 
and 
be positive integers with 
. There are cupcakes of different flavors arranged around a circle and 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 
, it is possible to partition the circle of cupcakes into groups of consecutive cupcakes so that the sum of 's scores of the cupcakes in each group is at least 
. Prove that it is possible to distribute the cupcakes to the people so that each person receives cupcakes of total score at least with respect to .
Solution 1
https://artofproblemsolving.com/wiki/index.php/File:2025_USAMO_PROBLEM_6.jpeg
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 G between the people and the arcs for Pip. We now consider the following algorithm, which takes several steps. If a perfect matching of G exists, we’re done! We’re probably not that lucky. Per Hall’s condition, this means there is a bad set B1 of people, who are compatible with fewer than |B1| of the arcs. Then delete B1 and the neighbors of B1, then try to find a matching on the remaining graph. If a matching exists now, terminate the algorithm. Otherwise, that means there’s another bad set B2 for the remaining graph. We again delete B2 and the fewer than B2 neighbors. Repeat until some perfect matching 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 M. We commit to assigning each of person in 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 M. To see why this deletion-induction works, consider any particular person Quinn not in M. By definition, Quinn is not happy with any of the arcs in M. So when an arc A of 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 A. When this happens, this causes two arcs of Quinn to merge, and the merged value is (≥ 1) + (≥ 1) − (≤ 1) ≥ 1 meaning the induction is OK.
Remark. This deletion argument can be thought of in some special cases even before the realization of Hall, in the case where 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.
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: “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.” 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.
See Also
| 2025 USAMO (Problems • Resources) | ||
| Preceded by Problem 5 |
Followed by Last Problem | |
| 1 • 2 • 3 • 4 • 5 • 6 | ||
| All USAMO Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
