Day 10: Caroling Caroling

There are $2^{10}$ possible subsets of houses, of which ${10 \choose 0} = 1$ empty, ${10 \choose 1} = 10$ consisting of 1 house, and ${10 \choose 2} = 45$ consisting of 2 houses. So there are $1024-1-10-45=968$ subsets of houses to be visited.

Similarly, if there are n carolers, they can form $2^n -1$ nonempty subsets.

So the number of visits will be the product of these $V(n)=968×(2^n-1)$

The number of songs the carolers can remember as a group is (*) $S(n)=800×2^n$

If $n=1$ , there are 968 visits and 1600 songs, which is enough. The question an now be rephrased as: will there be a point where $S(n)<V(n)$ , and at which integer value for n does that happen for the first time?

Setting $S(n)=V(n)$ , we solve:

$968×(2^n-1)=800×2^n$

$168×2^n=968$

$n=\log_2(\frac{168}{968})=\frac{\ln(\frac{168}{968})}{\ln 2} = 2.526..$

So at the next integer, $\boxed{ n=3}$ , the number of songs is not sufficient anymore (check: $S(3)=6400, V(3)=6776$ ).

$(*)$ Note: the wording 'the carollers know a base set of 800 songs' is somewhat ambiguous. I feel the most logical interpretation would be that the 'base set of 800 songs' refers to what each individual caroler can remember on their own. After all, how can 0 people remember a base set of 800 songs? Also, the words 'addition of extra caroller' suggest that there was a non-empty group to start with. So, I initially used the expression $S(n)=400×2^n$ which led to the final answer 1. Since that was wrong I tried with the given function S(n).