Christmas Streak 36/88: Wrapping Some Candies!

First off, how many ways are there if I didn't have a girlfriend and didn't care about the last bag?

Let's define the number of ways of doing this for $n$ candies as $a_n.$

Of course $a_0=1$ and $a_1=1.$

Let's consider the last bag of candies. There can be $n,~(n-1),~(n-2),~\cdots,~3,~2,$ or $1$ candies in that bag.

Then completing the rest of the bags would equal $a_0+a_1+a_2+a_3+\cdots+a_{n-3}+a_{n-2}+a_{n-1}.$

So $\displaystyle a_n=\sum_{k=1}^{n-1} a_k.$ Solving this yields $a_n=2a_{n-1},$ proving that this sequence is geometric.

Therefore $a_n=2^{n-1}~(n\ge2),$ and the number of ways of doing this is $a_{12}=2^{11}=2048.$

---

Nextly, how many ways are there if I still didn't care about the last bag and was being a mean guy and didn't make any bags that contain 2 candies?

Let's define the number of ways of doing this for $n$ candies as $b_n.$

Of course $b_0=1$ and $b_1=1$ and $b_2=1.$

Let's, again, consider the last bag of candies. There can be $n,~(n-1),~(n-2),~\cdots,~5,~4,~3,$ or $1$ candies in that bag since we can't have $2$ candies in a bag.

Then completing the rest of the bags would equal $b_0+b_1+b_2+b_3+\cdots+b_{n-4}+b_{n-3}+b_{n-1}.$

So $\displaystyle b_n=\sum_{k=1}^{n-1}b_k-b_{n-2}.$ Solving this yields $b_n=2b_{n-1}-b_{n-2}+b_{n-3}.$

Computing with this linear recurrence relation, we get $b_3=2,~b_4=4,~b_5=7,~b_6=12,~b_7=21,~b_8=37,~b_9=65,~b_{10}=114,~b_{11}=200,~b_{12}=351.$

---

Then from above, if I was a nice guy but didn't care about the last bag, there are $2048-351=1697$ ways of doing this.

There are three possible cases that makes the last bag contain 9 or more candies: (1, 2, 9), (2, 1, 9), (2, 10).

And thus, the number of ways of doing this is $1697-3=\boxed{1694}.$

Let $f(n,k)$ denote the number of ways to wrap the first $n$ candies where if $k=0$ , then no bag contains exactly $2$ candies, otherwise $k=1$ .

We have

$\displaystyle f(n,0) = (\sum_{i=n-1}^{0}f(i,0)) - f(n-2,0) = f(n-1,0)+f(n-2,0)+f(n-4,0)$

Thus we can easily calculate up to $f(12,0)$ .

Moreover, we have

$\displaystyle f(n,1) = (\sum_{i=n-1}^{0}f(i,1)) + f(n-2,0) = 2f(n-1,1)+f(n-2,0)-f(n-3,0)$

Thus we can also easily calculate up to $f(12,1)$ .

$f(12,1)$ included the cases where the size of last bag is $\ge 9$ , so we simply need to subtract $f(i,1)$ where $0 \le i \le 3$ to get the desired answer, which is

$1697 - 0 - 0 - 1 - 2 = \boxed{1694}$

Let $N_n$ be the number of ways of bagging and lining up $n$ candies, if we do not have to worry about having a bag containing two candies. Then $N_0=1$ and, thinking about the number $j$ of candies in the first bag in the line, we have $N_n \; = \; \sum_{j=1}^{n}N_{n-j} \; = \; \sum_{k=0}^{n-1} N_k$ It is a simple induction to show that $N_n \; = \; \left\{ \begin{array}{lll} 2^{n-1} & \qquad & n \ge 1 \\ 1 & & n= 0 \end{array} \right.$ Now let $T_n$ be the number of ways of bagging and lining up $n$ candies, if at least one of the bags has to contain two candies. Then $T_0 = T_1 = 0$ , $T_2 = 1$ . Thinking about the number $j$ of candies in the first bag in the line, we see that $\begin{aligned} T_3 & = \; T_2 + N_1 + T_0\\ T_4 & = \; T_3 + N_2 + T_1 + T_0\\ T_5 & = \; T_4 + N_3 + T_2 + T_1 + T_0 \\ T_n & = \; \sum_{j=1}^{n} T_{n-j} + (N_{n-2} - T_{n-2}) \end{aligned}$ Once we have a bag with two candies in it, we do not have to keep on looking out for two-candy bags, and so we replace $T_{n-2}$ by $N_{n-2}$ .

Iterating this recurrence relation, we obtain $T_3 = 2$ , $T_4 = 4$ , $T_5 = 9$ , $T_6 = 20$ , $T_7 = 43$ , $T_8 = 91$ , $T_9 = 191$ , $T_{10} = 398$ , $T_{11} = 824$ and $T_{12} = 1697$ .

Of the $T_{12}$ ways of bagging and lining up twelve candies, three of these, $(1,2,9)$ , $(2,1,9)$ , $(2,10)$ , have nine or more candies in the last bag. Thus the answer is $\boxed{1694}$ .