Olympiad Maths Prep

Library / /4 of 4

Combinatorics Difficulty 7.7 National olympiad, round 2 Prove it South Korea

Around a table 2n2n people are seated and mm cookies are distributed to them. These people can pass cookies under the following rules:

- One can only pass cookies to his/her neighbors.
- One can pass a cookie only if he or she eats one cookie.

Let AA be one of these people. Find the minimum mm such that no matter how mm cookies were distributed, there is a strategy to pass cookies so that AA has at least one cookie.

Solution

We will prove that the minimum number mm of cookies is 2n2^n. Let us write An+1,,A0(=A),A1,A2,,An1,AnA_{-n+1}, \dots, A_0(= A), A_1, A_2, \dots, A_{n-1}, A_n to denote the 2n2n people in the counterclockwise order.

First let us show that if m<2nm < 2^n, then there is a way to distribute mm cookies so that AA cannot get a cookie. Let aia_i be the amount of cookies given to AiA_i. Let N=i=n+1nai2iN = \sum_{i=-n+1}^{n} a_i 2^{|i|}. Note that the value of NN is non-increasing when one passes a cookie to the neighbors. So let us initially give all mm cookies to AnA_n. Then N=m2n<1N = m2^{-n} < 1. This means that even if we allow the people to pass cookies under the given rules, we still have N<1N < 1 and therefore it is impossible for AA to have a cookie.

Now let us show that if m=2nm = 2^n, then there is a strategy to make AA have a cookie. Let aia_i be the amount of cookies given to AiA_i. By symmetry, we may assume that i=0n1aii=0n1ai\sum_{i=0}^{n-1} a_i \ge \sum_{i=0}^{n-1} a_{-i}.

We ask AnA_n to pass an/2\lfloor a_n/2 \rfloor cookies to An1A_{n-1} by eating an/2\lfloor a_n/2 \rfloor cookies by himself. This allows us to assume that A0,A1,A2,,An1A_0, A_1, A_2, \dots, A_{n-1} have at least m/2=2n1m/2 = 2^{n-1} cookies. (If ana_n is even, then this is O.K. because they will have at least (man)/2+an/2(m-a_n)/2 + a_n/2 cookies. If ana_n was odd, then they will have at least (man)/2+(an1)/2=m/21/2(m-a_n)/2 + (a_n-1)/2 = m/2 - 1/2 cookies. Since mm is even, we can still conclude that A0,A1,A2,,An1A_0, A_1, A_2, \dots, A_{n-1} have at least m/2m/2 cookies.)

Now we claim that for k=1,2,,n1k = 1, 2, \dots, n-1, if A0,A1,A2,,AkA_0, A_1, A_2, \dots, A_k have at least 2k2^k cookies, then by passing cookies of AkA_k to Ak1A_{k-1}, we may assume that A0,A1,A2,,Ak1A_0, A_1, A_2, \dots, A_{k-1} have at least 2k12^{k-1} cookies. We may assume that ak>2k1a_k > 2^{k-1}. If ak=2ka_k = 2^k, then we simply let AkA_k pass 2k12^{k-1} cookies to Ak1A_{k-1} by eating 2k12^{k-1} cookies. So we may assume ak<2k1+2k1a_k < 2^{k-1} + 2^{k-1}. Therefore there exists an integer i{1,2,3,,k1}i \in \{1, 2, 3, \dots, k-1\} such that
2k1+2k2++2ki<ak2k1+2k2++2ki1. 2^{k-1} + 2^{k-2} + \dots + 2^{k-i} < a_k \le 2^{k-1} + 2^{k-2} + \dots + 2^{k-i-1}.

Note that
i=0k1ai2kak2k(2k12k2++2ki1). \sum_{i=0}^{k-1} a_i \ge 2^k - a_k \ge 2^k - (2^{k-1} - 2^{k-2} + \dots + 2^{k-i-1}).

Now if AkA_k passes his cookies to Ak1A_{k-1} as many as he can, then he can pass at least 2k2+2k3++2ki12^{k-2} + 2^{k-3} + \dots + 2^{k-i-1} cookies.

Then A0,A1,,Ak1A_0, A_1, \dots, A_{k-1} have at least i=0k1ai+(2k2++2ki1)2k1\sum_{i=0}^{k-1} a_i + (2^{k-2} + \dots + 2^{k-i-1}) \ge 2^{k-1} cookies. This proves the claim.

By the above claim we can inductively make A0A_0 have at least 20=12^0 = 1 cookies. \square

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.