Let \(a\), \(b\), and \(n\) be positive integers. A lemonade stand owns \(n\) cups, all of which are initially empty. The lemonade stand has a filling machine and an emptying machine, which operate according to the following rules: If at any moment, \(a\) completely empty cups are available, the filling machine spends the next \(a\) minutes filling those \(a\) cups simultaneously and doing nothing else. If at any moment, \(b\) completely full cups are available, the emptying machine spends the next \(b\) minutes emptying those \(b\) cups simultaneously and doing nothing else. Suppose that after a sufficiently long time has passed, both the filling machine and emptying machine work without pausing. Find, in terms of \(a\) and \(b\), the least possible value of \(n\). Proposed by Raymond Feng
Problem
Source: ELMO 2023/2
Tags: Elmo, number theory, combinatorics
26.06.2023 10:46
The answer is $n=2(a+b-gcd(a,b))$… btw this is my first every IMO 2 level combo solve, and I couldn't be happier because when i read the problem i was almost sure i wouldn't even understand it, let alone solve it, but still i did : ) Let me outline the basic points of the solution here (the full solution is in the pdf below) First, only care about coprime integers, because the extension to other gcd is trivial... Also, let EM=emptying machine and FM=filling machine First to prove $n \ge 2(a+b-1)$ notice that if the machines are to work together without pausing there must have been an instant when they started to work together (since the state of rest or work of a machine does not change while the other machine is working.) So they will start working together again for $t=lcm(a,b)=ab$ minutes. If at the instant they started working together, there were $e$ empty glasses and $f$ full glasses, the number of glasses at a future time (latexing this solution is a work in progress)
Attachments:
p2.pdf (367kb)
26.06.2023 11:13
There are a few facts which solve the problem after some analysis:
26.06.2023 15:04
26.06.2023 21:13
how many points would just stating the answer and lowerbound proof get?
27.06.2023 00:12
ihatemath123 wrote: how many points would just stating the answer and lowerbound proof get? It turns out that my proof for reaching equality (equilibrium) was complete overkill — the uniqueness of the final state, and there being a cycle within infinite iterations of states is enough to show that part. So probably a decent partial.
01.07.2023 00:55
The answer is \(2(a+b-\gcd(a,b))\). We view the problem through two models: the discrete model, where cups are filled instantly at the end of each \(a\)-minute period, and cups are emptied instantly at the end of each \(b\)-minute period; and the continuous model, where cups are filled at a constant rate during each \(a\)-minute period, and cups are emptied at a constant rate during each \(b\)-minute period. We begin by assuming \(\gcd(a,b)=1\). Lower bound for \(\gcd(a,b)=1\): Assume that at some time, say \(t=0\), both the filling machine and the emptying machine are starting their next cycle. Suppose that \(c\) cups are filled at \(t=0\). Using the discrete model, it suffices to consider when \(t\) is a multiple of \(a\) or \(b\). At \(t=ka\), the number of full cups is \(c+(ka\bmod b)\), whose maximum value is \(c+b-1\). For the machines to continue working without pausing, we must have \(n\ge(c+b-1)+a\). At \(t=\ell b\), the number of full cups is \(c-(\ell b\bmod a)\), whose minimum value is \(c-a+1\). For the machines to continue working without pausing, we must have \(0\le(c-a+1)-b\). Thus \(n\ge2(a+b-1)\). Upper bound for \(\gcd(a,b)=1\): Assume \(n=2(a+b-1)\), and consider the continuous model. Let \(t\) be the time and \(L\) be the total amount of liquid in the cups. When \(t\) is an integer and \(L\ge a+b-1\), there is at most \(a-1\) total liquid in (at most \(a\)) cups being filled and thus at least \(b\) totally filled cups. Hence the emptying machine is active and decreases \(L\) by 1 per minute. When \(t\) is an integer and \(L\le a+b-1\), there is at least 1 total liquid (i.e.\ at most \(b-1\) empty space) in (at most \(b\)) cups being emptied and thus at least \(a\) totally empty cups. Hence the filling machine is active and increases \(L\) by 1 per minute. Each minute, either both machines are active, or \(L\) gets 1 closer closer to \(a+b-1\) (if it is not equal to \(a+b-1\) already). The latter can only occur finitely many times, so \(L\) is eventually constant. Finish for \(\gcd(a,b)>1\): From the perspective of the discrete model, events only happen when time is a multiple of \(\gcd(a,b)\), and moreover the amount of total liquid is always a multiple of \(\gcd(a,b)\). Hence the problem for \((a,b)\) is the problem for \((a/\gcd(a,b),b/\gcd(a,b))\), with time and liquid scaled up by \(\gcd(a,b)\). It readily follows that the general answer is \(2(a+b-\gcd(a,b))\).
18.07.2023 07:08
Im honestly extremely surprised this solution got a 7, my construction was kinda sus my sol here