Problem Link
Difficulty:
CAKEWALK
Pre-requirements:
Simple Arithmetic
Problem:
Chef has N cupcakes, which he wishes to package. He makes as many packages of a fixed size as possible from the N cupcakes. After he has made these packages, he eats the remaining. Find what size of package (A) will ensure that he gets to eat the maximum possible number of cupcakes. If there is a tie, determine the largest such package-size.
Quick Explanation:
Given the size of the package A, the number of cupcakes Chef will get to eat will be N % A. Let us denote the optimal size by A#. A# is then [N/2]+1, where [x] is floor(x).
To see the proof of this, firstly note that [N/A#] = 1. If not, let k = [N/A#] > 1. Assuming that Chef uses size A#, he gets N - k * A#. If Chef had used A = k * A#, then too he would have got N - k * A#. And in deciding between these two which to choose, he would choose the larger, this means that he would have rather chosen “k * A#” instead of A#, thus contradicting that [N/A#] > 1.
Now, [N/A#] = 1 <=> A# > N/2, and that the amount Chef gets to eat = N - A#.
This is maximum for A# = “least integer > N/2” = [N/2] + 1.
Detailed Explanation:
In order to solve this question, we first need to ask ourselves, “if I were the Chef, and I were to use a package-size of A, how many cupcakes would I get to eat?”
If we can answer this question, it will give us an idea of what could possibly be the optimal A. In fact, the answer to the above question, is merely N A. This is because Chef keeps on taking out cupcakes in groups of A to package, so the number of cupcakes he has left follows the sequence N, N-A, N-2A, …, N - k * A, where after taking out k packages, we have N - k * A < A. This is precisely N A.
Approach 1:
This approach is exactly as described under “Quick Explanation”.
Claim: Chef will make only a single package in the optimal size (after getting rid of ties).
To illustrate the proof as given earlier, let us assume N = 15.
Now,
- A = 2, chef uses up 14 cupcakes in his package. He might as well have chosen his package size as A=14 here.
- A = 3, chef uses up 15 cupcakes in his package. He might as well have chosen his package size as A=15 here.
- A = 4, chef uses up 12 cupcakes in his package. He might as well have chosen his package size as A=12 here.
In this manner, so long as his chosen package size allows for more than 1 package, then he might as well have chosen his package size correspondingly larger : [N/A]*A to be precise.
The above puts a lower-bound on the optimal package size (A#), namely > N/2. Also, given this size A#, the remaining cupcakes is exactly N-A#. Maximizing this quantity subject to A# > N/2 gives us A# = “least integer > N/2” = [N/2] + 1.
Approach 2:
In this approach, let us first investigate what happens to the number of remaining cupcakes (lets denote it by f(A)) as a function of A.
If we were to try simple values of A to see what happens, we get
- for A = 1, Chef has 0 cupcakes left.
- for A = N, Chef has 0 cupcakes left.
- for A = 2, Chef has 0 or 1 cupcakes left (depending on whether N is even or odd).
- for A = N-1, Chef has 1 cupcake left.
and so on.
The above discussion qualitatively gives us the following ideas:
If A is too small, then f(A) is also small (bounded by A).
If A is too large, then f(A) is again small since we’ve already used up cupcakes in the package itself.
Formally,
- f(A) < A (N % A < A always)
- f(A) <= N - A (since A <= N, we take out at least one package).
Armed with the above two observations, we get that f(A) < N/2 irrespective of whatever size we choose: this is seen by summing the 2 inequalities above, giving us 2 * f(A) < N => f(A) < N/2.
Further, the bounds given above suggest that they will be weakest when A ~ N/2: the bounds can be written as f(A) <= min(A-1, N-A), where the term on the RHS is largest when A = (N+1)/2.
The above shows us a Necessary condition on the number of remaining cupcakes: f(A) < N/2.
Finally, if A <= N/2, then the bound “remaining <= N-A” wouldn’t be strong, since we could take out 2 packages, giving us remaining <= N-2A; however if A > N/2, then we get that f(A) = N - A. Thus, choosing A = [N/2] + 1, which is the least integer > N/2, we would get f(A) = (N-1)/2 (for odd N), = N/2 - 1 (for even N) which are in both cases the largest integer < N/2.
This shows us a Sufficient condition on the number of remaining cupcakes: that it is Possible to get “the largest integer < N/2” as our answer.
In other words, we have found a necessary and sufficient condition proving that A = [N/2] + 1 is the optimal package size.
Author’s Solution:
Can be found here
Tester’s Solution:
Can be found here
