Distributing cupcakes

Art of Problem Solving

AoPS Online

Contests & Programs AMC and other contests, summer programs, etc.

AMC and other contests, summer programs, etc.

3 M G

BBookmark VNew Topic kLocked

Contests & Programs AMC and other contests, summer programs, etc.

AMC and other contests, summer programs, etc.

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Distributing cupcakes

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: USAMO 2025/6

The post below has been deleted. Click to close.

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

407 posts

#1 h Friday at 12:00 PM • 3 Y

Y by ihatemath123, lpieleanu, RoyalPrince

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$ .

Z K Y

The post below has been deleted. Click to close.

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

176 posts

#2 h Friday at 12:08 PM • 32 Y

Y by arfekete, Equinox8, balllightning37, Pengu14, EpicBird08, Ilikeminecraft, Awesomeness_in_a_bun, OronSH, KevinYang2.71, ihatemath123, lpieleanu, Amkan2022, BS2012, GrantStar, aidan0626, ninjaforce, tediousbear, the_math_prodigy, megarnie, mathfan2020, Sedro, LostDreams, GeronimoStilton, github, Marcus_Zhang, Toinfinity, elasticwealth, centslordm, DreamineYT, MathRook7817, Exponent11, williamxiao

how many partials for throwing up 2 mins into the test then leaving

Z K Y

The post below has been deleted. Click to close.

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

1497 posts

#3 h Friday at 1:05 PM • 3 Y

Y by peace09, KevinYang2.71, centslordm

Communicated to me by the orz orz orz jatloe.

Define the $P$ person's partitions as bubbles. Then we get a matching between the $n$ people $P$ and the first person's $n$ bubbles $B$ . Connect a person to a bubble if they value that bubble as more than $1$ , so one person is connected to all the bubbles on this bipartite graph $G \subset P \times B$ . If Hall's condition is satisfied on these people, take that matching to win. Else, there exists some set $X$ of people such that they match less than $|X|$ bubbles. Remove that set, and repeatedly remove any set with $|N_G(X)| < |X|$ . We must end up with some non-empty set of people $M$ such that $M$ and $N_G(M)$ have a matching, and no person in $P \setminus M$ matches any bubble in $N_G(M)$ . In this case, we may take a matching on $M$ and $N_G(M)$ , and remove this matching and the corresponding bubbles; since the remaining people aren't connected to these bubbles, this inductively preserves the score condition for them.

This post has been edited 1 time. Last edited by YaoAOPS, Friday at 1:13 PM

Z K Y

The post below has been deleted. Click to close.

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

8857 posts

#4 h Friday at 1:23 PM • 3 Y

Y by krithikrokcs, bjump, centslordm

This problem is ultra cool. Here is a solution communicated to me by (the goat himself) Lerchen Zhong. We perform a strong induction on $n$ .

We call a continuous arc of cupcakes $\mathcal A$ delicious for person $P_i$ if the sum of $P_i$ 's scores across the cupcakes in that arc is at least $1$ . Consider a partition of the circle $\mathcal C$ into disjoint counterclockwise-oriented arcs $\mathcal A_1, \mathcal A_2, \dots, \mathcal A_n$ such that

$\mathcal A_1$ is the shortest arc starting at some cupcake $C$ that is delicious for someone;
for each $i$ , $\mathcal A_i$ is the shortest arc starting at the first cupcake counterclockwise of $\mathcal A_{i-1}$ that is delicious for someone.

By the given condition, we can always perform such a partition. Fix these arcs $\mathcal A_1, \dots, \mathcal A_n$ now. For each arc $\mathcal A_i$ , define the set $S_i$ to consist of all the people for which $\mathcal A_i$ is delicious. Then $S_i$ is nonempty for every $i$ . In fact, this is all the information we need to solve the problem.

We call a complete family $\mathcal F$ of the sets $S_i$ a family of subsets such that there exists a positive integer $k$ with

the union $\left|\bigcup_{S_i \in \mathcal F} S_i\right| = k$ ;
a perfect matching from $P_1, \dots, P_k$ (indexed without loss of generality) to the sets in $\mathcal F$ (under the obvious condition).

If there exists a complete family $\mathcal F$ , we can simply distribute the cupcakes in $S_i$ according to the matching and induct down. Otherwise, assume for the sake of contradiction that the result is not true; then there is no perfect matching between the $S_i$ and $P_i$ , so by the converse of Hall's marriage lemma, Hall's condition should fail.

Thus, take a minimal $k \geq 2$ such that $|S_1 \cup \cdots \cup S_k| < k$ . But then Hall's condition holds for $k-1$ , i.e. we can take that perfect matching (which notably contains only $k-1$ elements in the union) and induct down. This completes the proof.

Remark: [Rambling] I think Hall's marriage lemma is a natural idea to apply here: you have some sort of condition that says that there are ``enough" cupcakes for each person individually, so there should be a perfect matching. I found the difficulty of the problem to be the splitting into arcs $\mathcal A_i$ then realizing that this is sufficient to solve the problem. While the later Hall arguments are nontrivial, they are also quite unexpected (you want some kind of perfect matching and also a tight union set to induct, and those just sort of come together!), and while I did write down the $\mathcal A_i$ partition, I didn't think much of it. So in a sense this problem has a similar pitfall as USAMO2: you have to be confident that once you do have the $S_i$ reformulation that this information is sufficient to solve the problem.

This post has been edited 1 time. Last edited by HamstPan38825, Friday at 1:24 PM

Z K Y

The post below has been deleted. Click to close.

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

328 posts

#5 h Friday at 3:00 PM

Y by

YaoAOPS wrote:

Communicated to me by the orz orz orz jatloe.

Define the $P$ person's partitions as bubbles. Then we get a matching between the $n$ people $P$ and the first person's $n$ bubbles $B$ . Connect a person to a bubble if they value that bubble as more than $1$ , so one person is connected to all the bubbles on this bipartite graph $G \subset P \times B$ . If Hall's condition is satisfied on these people, take that matching to win. Else, there exists some set $X$ of people such that they match less than $|X|$ bubbles. Remove that set, and repeatedly remove any set with $|N_G(X)| < |X|$ . We must end up with some non-empty set of people $M$ such that $M$ and $N_G(M)$ have a matching, and no person in $P \setminus M$ matches any bubble in $N_G(M)$ . In this case, we may take a matching on $M$ and $N_G(M)$ , and remove this matching and the corresponding bubbles; since the remaining people aren't connected to these bubbles, this inductively preserves the score condition for them.

How many points for getting up to the Hall’s graph, but with flawed, kinda flipped sign of hall’s: I said if there exists $|N_G(X)| > |X|$ we can remove them and induct down (which is false) otherwise (this case doesn’t even exist??) there exists a bubble not matched with anyone which we can induct down on preserving score. I missed the immediate match and win case and I think my second case is a subset of my first which is skullers. Like I’m pretty sure I have a solve if in my first case instead of matching and winning I match and consider the complement which eventually reduces to something like my second case.

This is what happens when you figure out how p6 works with 20 minutes left, not having any time to recall Hall’s correctly or write down detailed proof, since you misread p5 and made it harder than it asked for

This post has been edited 1 time. Last edited by plang2008, Friday at 3:01 PM

Z K Y

The post below has been deleted. Click to close.

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

530 posts

USJL

#6 h Friday at 3:18 PM • 4 Y

Y by ihatemath123, NaturalSelection, aidan0626, Exponent11

This is proposed by me and Cheng-Yin Chang. Probably the whackiest hall's I've ever done.

Z K Y

The post below has been deleted. Click to close.

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

720 posts

#7 h Friday at 3:46 PM • 9 Y

Y by peace09, YaoAOPS, aidan0626, megarnie, Sedro, KevinYang2.71, EpicBird08, balllightning37, LostDreams

In all seriousness though I was planning on reviewing hall but forgot so it is 100% my own fault I missed this. Posting this just because it aged humorously

Attachments:

This post has been edited 1 time. Last edited by Mathandski, Friday at 3:47 PM

Z K Y

The post below has been deleted. Click to close.

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

328 posts

#8 h Friday at 4:22 PM

Y by

Mathandski wrote:

In all seriousness though I was planning on reviewing hall but forgot so it is 100% my own fault I missed this. Posting this just because it aged humorously

I learned Hall’s for the first time at Mathcamp but never did the provided hw so when the idea of Hall’s came to me on P6 I couldn’t formulate it fast enough because I just 1) have never applied it and 2) don’t have the condition ingrained in my head.

Maybe this is a sign to do your homework guys

Z K Y

The post below has been deleted. Click to close.

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

407 posts

#9 h Friday at 5:31 PM

Y by

then theres me who read Diestel so i know Hall and Konig and Tutte and literally every matching theorem there exists
but i still couldnt solve this problem with 50 minutes left (i didnt try)

This post has been edited 1 time. Last edited by KevinYang2.71, Friday at 5:31 PM

Z K Y

The post below has been deleted. Click to close.

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

3440 posts

#10 h Friday at 6:14 PM • 3 Y

Y by peace09, Mintylemon66, centslordm

FWIW, the posts in #3 and #4 gloss over the exact deletion process, and even though the Hall's lemma is the actual hard part of the proof, it's not a complete solution unless you explain how the deletion works too. Unless I'm going crazy, it's not just a trivial thing you can say in one sentence?

(Btw, I didn't solve this problem either. The solution was communicated to me by Andrew Carratu, who heard it from Lerchen I think. Or maybe Apra?)

Call the $s$ people who you are about to delete settled. For the people who aren't settled, you need to make sure they lose exactly $s$ groups in the deletion, and that each of their remaining groups still has value at least 1. For each of the $s$ settled people, delete the group they match with one at a time. Call the group we are about to delete $G$ . By the hypothesis (this is what the Hall's was for), the $n-s$ unsettled people value $G$ at most $1$ . In particular, none of these unsettled people will possess a group that is contained strictly within $G$ . They either own two adjacent groups whose border lies inside $G$ , or they own one group that contains $G$ (or is equal to $G$ ).

Suppose an unsettled person falls under the former case. Before, the two adjacent groups had a total value of at least $2$ , and after deleting $G$ , at most $1$ total value of cupcake was deleted from the union of those groups. Gluing the remains of those two groups together thus creates a new group with total value at least $1$ , maintaining the condition. In particular, gluing these groups together decreases this unsettled person's total number of groups by one, which is what we want.
Suppose an unsettled person falls under the latter case. So, by deleting $G$ , we put a hole in this unsettled person's group. Then, they simply glue the two remains of this group together with another group to the left. The value of this new group is at least $1$ (in fact, equality holds only when there the remains of the group totaled $0$ in value).

We obviously don't need to worry about regrouping the settled people. So, repeating this process $s$ times on each of the settled people will leave us with only the $n-s$ unsettled people remaining, each of whom have $n-s$ groups.

Notably, the deletion process is the only part of the problem where you use (a) the fact that the value of a group is determined by the sum of its individual cupcake values, and not some other function of the values, and (b) the fact that the groups are contiguous. It's important to find a maximal set of settled people to delete at once, since we take advantage of the fact that we don't need to regroup the settled people.

This post has been edited 5 times. Last edited by ihatemath123, Friday at 7:41 PM

Z K Y

The post below has been deleted. Click to close.

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

328 posts

#13 h Friday at 11:04 PM • 1 Y

Y by eg4334

Ok here’s an attempt. I’m still crashing out over how many wrong statements I wrote about hall’s yet have the right idea all along

Call each person's consecutive group of cupcakes their bubbles. WLOG each bubble has a total score of $1$ by scaling down; clearly we can scale back up later.

Consider a specific person $P$ . Let $X$ be the set of the other $n - 1$ people and $Y$ be the set of bubbles of $P$ . Match a person with a bubble if the bubble's score for that person is greater than $1$ . We have a bipartite graph.

Now we consider a reduction step. Suppose we give $P$ a bubble $B$ , then $P$ is happy. If no other person $Q$ matches with $B$ , then $Q$ is happy too, and since $B$ does not fully contain any bubbles of $Q$ , so we can join the up to two bubbles of $Q$ that was split by $B$ , preserving the score condition. If someone matches with $B$ , then we may run into issues.

Now apply Hall's. If Hall's condition is satisfied, then we can easily match all $n-1$ people with a bubble and give $P$ their last bubble. This reduces the problem to a smaller $n$ . If Hall's condition is not satisfied, this means there is some subset $S$ such that if the set of its matches is $N(S)$ , then $|S| > |N(S)|$ .

Thus consider $X \setminus S$ and $Y \setminus N(S)$ . Since $|X| < |Y|$ , clearly $|X \setminus S| < |Y \setminus N(S)|$ still. Additionally, note that no person in $S$ matches with any bubble in $Y \setminus N(S)$ . Thus, we return to our original hypothesis.

Thus we can continue reducing until Hall's condition is satisfied (in which case we match and reduce), or until $X \setminus S = \emptyset$ . In this case, clearly $Y \setminus N(S) \neq \emptyset$ , so there is indeed an empty bubble. Apply the reduction step mentioned earlier. This concludes the reduction.

And of course, $n = 1$ is trivial.

This post has been edited 2 times. Last edited by plang2008, Friday at 11:08 PM

Z K Y

The post below has been deleted. Click to close.

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

706 posts

#14 h Friday at 11:07 PM • 1 Y

Y by elasticwealth

plang2008 wrote:

Ok here’s an attempt. I’m still crashing out over how many wrong statements I wrote about hall’s yet have the right idea all along

Call each person's consuective group of cupcakes their bubbles. WLOG each bubble has a total score of $1$ by scaling down; clearly we can scale back up later.

Consider a specific person $P$ . Let $X$ be the set of the other $n - 1$ people and $Y$ be the set of bubbles of $P$ . Match a person with a bubble if the bubble's score for that person is greater than $1$ . We have a bipartite graph.

Now we consider a reduction step. Suppose we give $P$ a bubble $B$ , then $P$ is happy. If no other person $Q$ matches with $B$ , then $Q$ is happy too, and since $B$ does not fully contain any bubbles of $Q$ , so we can join the up to two bubbles of $Q$ that was split by $B$ , preserving the score condition. If someone matches with $B$ , then we may run into issues.

Now apply Hall's. If Hall's condition is satisfied, then we can easily match all $n-1$ people with a bubble and give $P$ their last bubble. If Hall's condition is not satifisfied, this means there is some subset $S$ such that if the set of its matches is $N(S)$ , then $|S| > |N(S)|$ .

Thus consider $X \setminus S$ and $Y \setminus N(S)$ . Since $|X| < |Y|$ , clearly $|X \setminus S| < |Y \setminus N(S)|$ still. Additionally, note that no person in $S$ matches with any bubble in $Y \setminus N(S)$ . Thus, we return to our original hypothesis.

Thus we can continue reducing until Hall's condition is satisfied (in which case we match and win), or until $X \setminus S = \emptyset$ . In this case, clearly $Y \setminus N(S) \neq \emptyset$ , so there is indeed an empty bubble. Apply the reduction step mentioned earlier. This concludes the reduction.

And of course, $n = 1$ is trivial.

0/7, you spelled consecutive wrong

Z K Y

The post below has been deleted. Click to close.

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

328 posts

#15 h Friday at 11:08 PM

Y by

S.Das93 wrote:

0/7, you spelled consecutive wrong

well i’m already 0/7 for writing hall’s condition wrong

Z K Y

The post below has been deleted. Click to close.

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

706 posts

#16 h Friday at 11:09 PM

Y by

hall's divorce

Z K Y

The post below has been deleted. Click to close.

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

6869 posts

#17 h 2 hours ago • 5 Y

Y by H_Taken, Exponent11, aidan0626, ihatemath123, EpicBird08

Amazing problem. Here's my write-up of it. When working on it myself, I had the idea to match one person's arcs with Hall but didn't see the deletion argument.

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.

If a perfect matching of $\mathfrak{G}$ exists, we're done!
We're probably not that lucky. Per Hall's condition, this means there is a bad set $\mathcal{B}_1$ of people, who are compatible with fewer than $|\mathcal{B}_1|$ of the arcs. Let's imagine deleting $\mathcal{B}_1$ and those neighbors of $\mathcal{B}_1$ , then try to find a matching on the remaining graph.
If a matching exists, 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.
Repeat until some perfect matching $\mathfrak{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}$ .

A cartoon of this picture is shown below.
$[asy]usepackage("amssymb"); 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)), invisible, red+1.2); filldraw(box((-w-eps, 6+eps), (-w+eps,5-eps)), invisible, orange+1.2); filldraw(box((-w-eps, 4+eps), (-w+eps,2-eps)), invisible, brown+1.2); filldraw(box((w-eps, 9+eps), (w+eps,8-eps)), invisible, red+1.2); filldraw(box((w-eps, 7+eps), (w+eps,7-eps)), invisible, orange+1.2); filldraw(box((w-eps, 6+eps), (w+eps,5-eps)), invisible, 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 $\mathfrak{M}$", deepgreen); for (int i=0; i<10; ++i) { dot((w,i), blue); dot((-w,i), blue); } label("Pip", (-w,0), dir(180), blue); [/asy]$
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 $Q$ not in $\mathcal{M}$ . By definition, $Q$ is not happy with any of the arcs in $\mathcal{M}$ So when an arc $\mathcal{A}$ of $\mathfrak{M}$ is deleted, it had value less than $1$ for $Q$ , so in particular it couldn't contain entirely any of $Q$ 's arcs. Hence exactly one endpoint among $Q$ 's arcs was in the deleted arc $\mathcal{A}$ . This causes two arcs of $Q$ 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 $Q$ 's arcs and scores are drawn in red (in this example $n=3$ ).
$[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, "$Q$'s values", 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, "$Q$'s values", O, red); add(before); add(shift(3.2,0)*after); [/asy]$

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.

Z K Y

The post below has been deleted. Click to close.

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

3440 posts

#19 h an hour ago

Y by

@above in the deletion process, isn't it also possible for $Q$ to contain the deleted arc entirely? (so zero of the endpoints are in the deleted arc)

Z K Y

The post below has been deleted. Click to close.

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

328 posts

#20 h an hour ago

Y by

ihatemath123 wrote:

@above in the deletion process, isn't it also possible for $Q$ to contain the deleted arc entirely? (so zero of the endpoints are in the deleted arc)

then you can just arbitrarily join that arc of $Q$ with a neighboring one (which is valid since $1 + (\geq0) \geq 1$ )

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a