1
$\begingroup$

I found this problem:

There are 2n people seated around a circular table, and m cookies are distributed among them. The cookies may be passed around under the following rules:

• Each person may only pass cookies to his or her neighbours.

• 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 to begin with, there is a strategy to pass cookies so that A receives at least one cookie.

What I'm looking for is just an example, like a small case verification ( say n = 3 or 4 ), because What I see is that for n=3, taking m=6 is sufficient so that everyone gets a cookie, but they claim that the minimum is $2^n$. Can someone explain where I am wrong ?

$\endgroup$
  • $\begingroup$ I think the issue is that you cannot pass stacks of cookies $\endgroup$ – Peter Woolfitt Nov 28 '15 at 20:30
  • $\begingroup$ @PeterWoolfitt: from the answer of "Brazillian Cérebro" , I understand that to pass n cookies you have to eat n cookies. I thought that to pass whatever amount of cookies, you just have to eat one cookie. $\endgroup$ – Michael Heidelberg Nov 28 '15 at 20:39
1
$\begingroup$

Suppose that we have the persons $1,2,3,4,5,6$ sitting next to eachother, with $1$ sitting next to $6$. Suppose person $1$ has six cookies and he wants them to pass to person $4$. He needs three times two cookies to pass three cookies to to person $2$. So now person $6$ doesn't have any cookies and person $2$ now has three cookies. Person $2$ can pass only one cookie to person $3$, and is left with one cookie. So now person $2$ and $3$ both only have one cookie, so they can't pass anything.

Because it doesn't help to pass cookies from person $1$ to $6$ in the beginning, we see that six cookies is not sufficient.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.