Maths Olympiad Prep

Library / /1232 of 1394

, 2018

Combinatorics Difficulty 5.8 AIME, harder Prove it United States

Problem:

Suppose there are 100 cookies arranged in a circle, and 53 of them are chocolate chip, with the remainder being oatmeal. Pearl wants to choose a contiguous subsegment of exactly 67 cookies and wants this subsegment to have exactly kk chocolate chip cookies. Find the sum of the kk for which Pearl is guaranteed to succeed regardless of how the cookies are arranged.

Solution

Solution:

We claim that the only values of kk are 35 and 36.

WLOG assume that the cookies are labelled 0 through 99 around the circle. Consider the following arrangement: cookies 0 through 17, 34 through 50, and 67 through 84 are chocolate chip, and the remaining are oatmeal. (The cookies form six alternating blocks around the circle of length 18,16,17,16,18,1518, 16, 17, 16, 18, 15.) Consider the block of 33 cookies that are not chosen. It is not difficult to see that since the sum of the lengths of each two adjacent block is always at least 33 and at most 34, this block of unchosen cookies always contains at least one complete block of cookies of the same type (and no other cookies of this type). So this block contains 17 or 18 or 3316=1733-16=17 or 3315=1833-15=18 chocolate chip cookies. Therefore, the block of 67 chosen cookies can only have 5317=3653-17=36 or 5318=3553-18=35 chocolate chip cookies.

Now we show that 35 and 36 can always be obtained. Consider all possible ways to choose 67 cookies: cookies 0 through 66, 1 through 67, \ldots, 99 through 65. It is not difficult to see that the number of chocolate chip cookies in the block changes by at most 1 as we advance from one way to the next.

Moreover, each cookie will be chosen 67 times, so on average there will be 6753100=35.51\frac{67 \cdot 53}{100} = 35.51 chocolate chip cookies in each block. Since not all blocks are below average and not all blocks are above average, there must be a point where a block below average transitions into a block above average. The difference of these two blocks is at most 1, so one must be 35 and one must be 36.

Therefore, the sum of all possible values of kk is 35+36=7135 + 36 = 71.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.