There are 2n people seated around a circular table, and m cookies are distributed among them. The cookies can be passed under the following rules:
(a) Each person can only pass cookies to his or her neighbors
(b) Each time someone passes a cookie, he or she must also eat a cookie
Let A be one of these people. Find the least m such that no matter how m cookies are distributed initially, there is a strategy to pass cookies so that A receives at least one cookie.
Let us denote the people with symbols such as A-n, A-n+1, A-n+2, ...A-1, A0, A1, ... An where A-n and An are the same person since it is a circular table.
A weight 1/2^abs(i) is assigned to each cookie held by a person Ai. Thus for example if A3 passes a cookie to A2, the cookie's weight increases from 1/8 to 1/4. Since A3 must also eat a cookie of weight 1/8 in this step, we see in this case, the sum of the weights of all the cookies has remained the same. The sum of the weight of all the cookies has remained the same. If Ai has ai cookies for each i, then the total weight of all cookies is Sum of i from -n+1 to n is ai / 2^ abs(i).
Whenever a cookie is passed towards A0, (from Ai to Ai-1 or the reverse direction), one cookie is eaten and another cookie doubles its weight, so the total weight remains invariant. If a cookie has passed away from A0, then the total weight decreases. Thus the total weight is indeed a monovariant.
If m >= 2^n, we can always ensure that the A0 gets a cookie. Any of the directions could be chosen but it should not pass A0 because the weight would reduce. In each step therefore a cookie progresses towards A0 from either side of the diametrically opposite end. We use a new quantity to indicate the direction. Let W+ be the sum of the weights of the cookies held by A0, A1 ... An and let W be the sum of the weights of cookies held by A0, A-1, A-2 ... and we can suppose W+ >= W=. Then this suggests An can pass cookies to only An-1 and we use only this semi-circle containing non-negative indices, since this is the semi-circle having more weight. In each step, as m any cookies are passed as possible to An-1 and similarly forwarded. This works only if and only if W+ is > 1 which is necessary as W+ is a monovariant.
To show that this is sufficient, we note that the algorithm leaves the W+ an invariant. The algorithm terminates when we cannot pass anymore cookies from any of the Ai with i positive, and A0 does not have any cookies.A1, A2, ... An all have at most one cookie at the end. If they had more, they would eat one and pass one and the algorithm would not have terminated. Then W+ would sum upto 1/2 + 1/4 + ... + 1/2 ^ n < 1, contradicting the fact that W+ is an invariant and >= 1. Thus W+ >= 1 is a sufficient condition for the algorithm to work. Finally we prove that we indeed have W+ > 1 We assumed W+ > W-. Now simply note that each cookie contributes at least 1 / 2 ^(n-1) to the sum(W+ and W-), because each cookie has weight at least 1/2^(n-1) except for cookies at An. However, cookies at An are counted twice since they contribute to both W+ and W-, so they also contribute 1/ 2^n-1 to the sum. Since we have at least 2 ^ n cookies, W+ and W- >= 2, so W+ >= 1 and have proved that this is both necessary and sufficient.
Note that the use of a geometric progression ensures that the cookie can be consumed and passed along and using the property of the sum of this progression we bound it at the diametrically opposite end of the table because that suffices to have everyone get a cookie.
The criteria for weights on a semi-circle to be more than 1 is therefore of a consequence of the above.
(a) Each person can only pass cookies to his or her neighbors
(b) Each time someone passes a cookie, he or she must also eat a cookie
Let A be one of these people. Find the least m such that no matter how m cookies are distributed initially, there is a strategy to pass cookies so that A receives at least one cookie.
Let us denote the people with symbols such as A-n, A-n+1, A-n+2, ...A-1, A0, A1, ... An where A-n and An are the same person since it is a circular table.
A weight 1/2^abs(i) is assigned to each cookie held by a person Ai. Thus for example if A3 passes a cookie to A2, the cookie's weight increases from 1/8 to 1/4. Since A3 must also eat a cookie of weight 1/8 in this step, we see in this case, the sum of the weights of all the cookies has remained the same. The sum of the weight of all the cookies has remained the same. If Ai has ai cookies for each i, then the total weight of all cookies is Sum of i from -n+1 to n is ai / 2^ abs(i).
Whenever a cookie is passed towards A0, (from Ai to Ai-1 or the reverse direction), one cookie is eaten and another cookie doubles its weight, so the total weight remains invariant. If a cookie has passed away from A0, then the total weight decreases. Thus the total weight is indeed a monovariant.
If m >= 2^n, we can always ensure that the A0 gets a cookie. Any of the directions could be chosen but it should not pass A0 because the weight would reduce. In each step therefore a cookie progresses towards A0 from either side of the diametrically opposite end. We use a new quantity to indicate the direction. Let W+ be the sum of the weights of the cookies held by A0, A1 ... An and let W be the sum of the weights of cookies held by A0, A-1, A-2 ... and we can suppose W+ >= W=. Then this suggests An can pass cookies to only An-1 and we use only this semi-circle containing non-negative indices, since this is the semi-circle having more weight. In each step, as m any cookies are passed as possible to An-1 and similarly forwarded. This works only if and only if W+ is > 1 which is necessary as W+ is a monovariant.
To show that this is sufficient, we note that the algorithm leaves the W+ an invariant. The algorithm terminates when we cannot pass anymore cookies from any of the Ai with i positive, and A0 does not have any cookies.A1, A2, ... An all have at most one cookie at the end. If they had more, they would eat one and pass one and the algorithm would not have terminated. Then W+ would sum upto 1/2 + 1/4 + ... + 1/2 ^ n < 1, contradicting the fact that W+ is an invariant and >= 1. Thus W+ >= 1 is a sufficient condition for the algorithm to work. Finally we prove that we indeed have W+ > 1 We assumed W+ > W-. Now simply note that each cookie contributes at least 1 / 2 ^(n-1) to the sum(W+ and W-), because each cookie has weight at least 1/2^(n-1) except for cookies at An. However, cookies at An are counted twice since they contribute to both W+ and W-, so they also contribute 1/ 2^n-1 to the sum. Since we have at least 2 ^ n cookies, W+ and W- >= 2, so W+ >= 1 and have proved that this is both necessary and sufficient.
Note that the use of a geometric progression ensures that the cookie can be consumed and passed along and using the property of the sum of this progression we bound it at the diametrically opposite end of the table because that suffices to have everyone get a cookie.
The criteria for weights on a semi-circle to be more than 1 is therefore of a consequence of the above.
No comments:
Post a Comment