Alice, Bob and Carol, and many cookies

Question

Alice, Bob and Carol sit around a round table. Initially Alice has $n$ cookies, while Bob and Carol have none. Alice divides her cookies evenly between Bob and Carol; if there is a leftover cookie (as $n$ is odd) then Alice eats it. Then Bob does the same with his cookies, then Carol does the same with hers. And so on, and so on, and so on. The process continues forever: in a round-robin fashion, everybody divides his/her cookies evenly between the other two persons and eats leftovers if there are any.

Question: For which starting values of $n\ge1$ does the process continue forever WITHOUT a single cookie being eaten?

Answer 1

The answer is:

there is no such number.

Let's define the amount of cookies at the beginning as $1$, and look at the fractions everyone has after each round:

$\frac{1}{2}\space\frac{1}{2}$

$\frac{3}{4}\space\frac{1}{4}$

$\frac{5}{8}\space\frac{3}{8}$

$\frac{11}{16}\space\frac{5}{16}$

$\frac{21}{32}\space\frac{11}{32}$

$\frac{43}{64}\space\frac{21}{64}$

$...$

$\frac{n}{n+m}\space\frac{m}{n+m}$

$\frac{n+2*m}{2(n+m)}\space\frac{n}{2(n+m)}$

As can be seen above all numerators are odd, and all denominators are a power of $2$. And this will stay that way, because every new numerator is $2*previous \space numerator$ which gives an even number and after adding another odd numerator it becomes odd again. That way the fraction can never be reduced, and we never get a loop which would be required for this to work.

Extension to 4 friends (requested by ghosts_in_the_code):

The proof works similar to the above case, we start with $1$ again:

$\frac{1}{3}\space\frac{1}{3}\space\frac{1}{3}$

$\frac{4}{9}\space\frac{4}{9}\space\frac{1}{9}$

$\frac{16}{27}\space\frac{7}{27}\space\frac{4}{27}$

$\frac{37}{81}\space\frac{28}{81}\space\frac{16}{81}$

$\frac{121}{243}\space\frac{85}{243}\space\frac{37}{243}$

$...$

$\frac{n}{n+m+o}\space\frac{m}{n+m+o}\space\frac{o}{n+m+o}$

$\frac{n+3*m}{3(n+m+o)}\space\frac{n+3*o}{3(n+m+o)}\space\frac{n}{3(n+m+o)}$

None of the numerators in the example is divisible by $3$. New numerators are created by $3*previous \space numerator$ which is obviously divisible by $3$, and adding of another numerator (not divisible by $3$) which makes the new numerator not divisible by $3$ again.

This can be extended to any number of friends.

Answer 2

The answer, as already others have said, is

there are no $n$ for which this is true.

Here is another proof why. Assume a cookie is never eaten. We can think of the situation as a series of states, $s_0,s_1,s_2,\dots$, where each $s_i$ is a triple $(a,b,c)$ of how many cookies each person has.

Eventually, a state must repeat. Suppose that $s_i$ is the first repeated state, and the first time it repeats is at step number $j$ (so $j>i$ and $s_j=s_i$). There are two possibilities:

• CASE 1: $i\ge1$. This means that $s_{i-1}$ and $s_{j-1}$ are distinct states which both lead to state $s_i$. This is impossible: when no cookies are eaten, each state has a unique state which leads to it. For example, the unique state leading to $(a,b,0)$ is $(a-b,0,2b)$.

• CASE 2: $i=0$. This means that the state $s_{j-1}$ leads to the state $s_j=s_0=(n,0,0)$. Again, this is impossible: as long as no cookies are eaten, then after each move, there will be two people who have cookies, so no state can lead to $(n,0,0)$.

Either way, assuming no cookies are eaten leads to a contradiction.

Answer 3

There are no such solutions!

To see this explicitly we can calculate how many cookies the 3 people ( A, B and C ) have at a given stage. To do this I altered the problem by assuming that after person A (Alice) shares their cookies for the first time, everyone gives their cookies to the person alphabetically before them: so C gives to B, B gives to A and A gives to C. In practice this gives the following for the first 2 stages:

At stage 1: A has n, B has 0 and C has 0

At stage 2: A has n/2, B has n/2 and C has 0

We can repeat this procedure of A halving the cookies and then the cookies being shifted along (so now only Alice halves her cookies). This generates the same fractions to appear at each stage as the original problem yet different people will have different fractions. (The shift essentially changes A into person B on stages that are 2 mod 3, C on 0 mod 3 stages and A on 1 mod 3 stages)

(note C will always have 0 cookies)

From this we can calculate how many cookies people have at a given stage in the new altered problem (and this will be a permutation of the solution to the original problem as discussed above).

Let A(i),B(i) denote the cookies A and B have a stage i. We have $A(1) = n$ and $B(1) = 0 $

We now consider how A(i) changes in the altered problem, we deduce:

$A(i+1) = B(i) + \frac {A(i)} {2} $

and $B(i+1) = \frac{A(i)} {2} $

Therefore $B(i) = \frac{A(i-1)} {2}$ from that second equation

Substituting this back in to the first gives (after arranging): $2A(i+2) - A(i+1) - A(i) = 0$

This is a standard difference equation which we can solve with the initial conditions I wrote above. I'll leave out the algebra. This gives:

$ A(i) = \frac {2n}{3} \frac{2^i - (-1)^i} {2^i}$ and since no cookies are eaten B(i) = n - A(i)

And from this we know how many cookies A has in the altered problem which implies someone in the original problem has A(i) cookie at a given stage. We now note that A(i) must always be an integer for the cookies to be halved correctly without one being eaten.

However it is clear that $(2^i - (-1)^i)$ is always an odd number so for A(i) to be an integer for all i, 2^i must divide n for all positive intgers i. This is not possible unless we are in the trival case in which n=0.

(note it is possible to calculate exactly how many cookies each person has at a stage by combining the solution to the difference equation with my comment :'(The shift essentially changes A into person B on stages that are 2 mod 3, C on 0 mod 3 stages and A on 1 mod 3 stages)')

Answer 4

The number of cookies a person receives is halved at each round, until eventually it becomes 1. At this time the cookie can't be shared anymore and must be eaten. So, for the process to continue forever, $n$ must be an infinitely large power of two.