Investigation

Writing a solution for this one would take some time, hope someone can do it for me :)

This isn't a 100% full solution, but it got me the answer:

My first idea was to give everyone a 7-bit binary number, on day 1 invite everyone with a 0 in their 1-bit and then on day 2 invite everyone with a 1 in the 1-bit. Then do the 2-bits, then the 3-bits, and so on. This got me to 14 days, but it seemed possible to do better.

The next realization was that if I had an optimal strategy, I could give each person a number based on which days they were brought in. If the optimal strategy was $n$ days, then everyone would end up with an $n$ -bit number with a 1 for the $2^i$ bit if they were brought in on day $i+1$ . But it's not enough just to get everyone a unique number, which can be done in 7 bits, because if two people, $A$ and $B$ , get numbers such that $A$ 's set bits include all of $B$ 's set bits, then $B$ is never called in without $A$ . If $B$ is the witness and $A$ the criminal, this doesn't work.

So how to ensure that we never have two people get numbers like that? One simple solution, make sure everyone has the same number of set bits. This works nicely for symmetry as well, meaning that everyone is called in on the same number of days. Now, letting $n$ be the number of days for the optimal solution and $k$ the number of days each person is called in, we can solve for up to ${n \choose k}$ people in our $n$ days. This is maximized for $k = \tfrac{n}{2}$ , so we want ${n \choose \lfloor\tfrac{n}{2}\rfloor} \ge 80$ . ${8 \choose 4} = 70$ is too small but ${9 \choose 4} = 126$ is good enough.

So this shows that 9 is possible, and also that 8 is not possible if everyone is brought in the same number of times . But that's as much as I thought through.