Editorial for Wesley's Anger Contest 6 Problem 6 (Hard Version) - Santa's Candy Factory
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
We will assume without loss of generality that . Consider a strategy where we arbitrarily assign one bowl to one colour and the other to a different colour. If we place all candy canes in their assigned bowl (and discard the remaining colour), the worst we can do is . This strategy alone however is not enough to get any points.
We can consider another strategy where we attempt to identify the colour with candy canes. We begin similar to the first strategy by arbitrarily assigning one bowl to one colour and the other to a different colour. If discarding the current candy cane would result in the total number of candy canes discarded exceeding , then it must be the colour with candy canes. We will then empty any of the two bowls, change the colour assigned to that bowl to the current candy cane's colour, and proceed as usual. If this never occurs, then it must be that one of the initial colour assignments was the colour with candy canes. We can see that in the worst case, we will collect candy canes.
By itself, neither the first nor second strategy is enough to get any points, but if we consider all possible values of , , and , we can see that is always at least , which is enough to get of the points.
We will now consider a third strategy where we attempt to identify both the colour with and candy canes. We will begin similar to the second strategy, but this time we will wait until the current candy cane being discarded would result in more than total discarded candy canes. This time, we must be careful not to change the colour of a bowl with at least candy canes in it. We will select any of the remaining bowls and change the colour assigned to that bowl to be the current candy cane's colour. We will also reset the discard counter to the number of candy canes in the bowl that is emptied. Again, if this never occurs, then it must be that the initial colour assignments were the colours with and candy canes. We will then continue placing candy canes based on their bowl assignment until discarding the current candy cane would result in the discard counter exceeding . We can then assign the colour of the bowl that has not yet been reassigned to be the current candy cane's colour, and proceed as usual. If this never occurs, then after the first reassignment, the colour assignments were the colours with and candy canes. In the worst case, this strategy will collect candy canes, which is also not enough on its own for any points.
If we combine the first and third strategies, for all values of , , and , we can collect at least candy canes.
If we combine all three strategies, we can always collect at least candy canes.
To get candy canes, we can slightly modify the third strategy. First, we should not discard any bowls that have at least candy canes instead of candy canes. Second, we should never let the discard counter exceed , rather than . With these two modifications, it can be shown that in the worst case, this strategy will collect candy canes. Thus, .
Comments