Russell's Fibonacci coin bags

We first show by induction that $F_n-1=F_{n-2}+F_{n-3}+\ldots+F_1$ for all $n \ge 3$ . The base case, $n=3$ , follows since $F_3-1=F_1$ , or $2-1=1$ . Assume the statement is true for $n$ . If we add $F_{n-1}$ to both sides, the left hand side becomes $F_n+F_{n-1}-1=F_{n+1}-1$ while the right hand side becomes $F_{n-1}+F_{n-2}+\ldots+1$ . Thus, if the statement if true for $n$ , then it is true for $n+1$ , and the claim follows.

By the claim, we see that the 2012th bag and 2013th bag must be given to different friends, because the coins in all the other bags add up to less than the number of coins in the 2013th bag. Also, from the claim, we obtain

$\begin{aligned} F_n & > F_{n-2}+F_{n-3}+F_{n-4} +\ldots+F_1\\ F_n + F_{n-2} &> F_{n-2} + F_{n-2} + F_{n-3} + F_{n-4} + \ldots + F_1\\ F_n + F_{n-2} &> F_{n-1} + F_{n-2} + F_{n-4} + F_{n-5} + \ldots + F_1\\ F_n+F_{n-2} &> F_{n-1} + F_{n-3} + F_{n-4} + F_{n-5} + \ldots + F_1. \end{aligned}$

Since the number of coins in all bags other than the 2011th bag and the 2013th bag add up to fewer than the number of coins in the 2011th bag and 2013th bag, it must be the case that the 2011th bag should go to the person with the 2012th bag. There are 2 ways to select who will get the 2011th, 2012th, and 2013th bags. Since $F_{2013} = F_{2012} + F_{2011}$ , we have reduced the problem to distributing the remaining $2010$ bags into equal parts.

Now, we can continue to reason this way for each set of three consecutive bags $\{2010, 2009, 2008\}, \{2007, 2006, 2005\},$ etc. There are 671 sets of 3 numbers, implying there are $N= 2^{671}$ ways to divide the bags. Therefore, $\log_2 N = 671.$