Problem: Every day, the detective can invite one or more of $80$ people, including a criminal and a witness to the crime, to the office and talk to them about the case. The detective knows that if there is the witness among those invited but the criminal is not in the group, the witness will say who the criminal is. In at least how many days can the detective following this method find the criminal with certainty?
My Attempt for The Solution: The detective can definitively find the criminal in $80$ days. He calls one person every day, and in the worst case, the witness may end up at the bottom of the list of testifiers.
So what would happen if we formed $40$ groups of $2$ each? Let $\{ a_1, b_1\}, \{ a_2, b_2\}, \dots , \{ a_{40}, b_{40}\}$ be the groups. It takes $40$ days to investigate them. If no results can be obtained from these groups, it means that the witness and the criminal are in the same group. Let's create groups in a different way: $ \{ a_1, a_2\}, \{ a_3, a_4\}, \dots ,\{ a_{39}, a_{40}\}, \{ b_1, b_2\}, \{ b_3, b_4\}, \dots ,\{ b_{39}, b_{40}\}$. Now the criminal and the witness are in different groups. The investigating of these groups also takes $40$ days. Again, $40+40=80$ days are needed.
Can the criminal be identified in fewer days? Maybe more successful results can be obtained with different grouping methods, I am not sure. Thank you for your interest.
Let $S_1,S_2,\dots,S_n$ be your daily selected people.
Then for each person $i,$ let $T_i=\{j\mid i\in S_j\}.$ That is $T_i$ is the list of days when person $i$ is invited.
Now, given $i_1\neq i_2,$ if $T_{i_1}\subseteq T_{i_2},$ you'd invite person $i_2$ every day you invited person $i_1.$ So you wouldn't have solved the problem when $i_1$ was the witness and $i_2$ is the criminal
So to have a solution, the $T_i$ must be an antichain on the set of subsets of $\{1,2,\dots,n\}.$ But by Sperner's theorem, the largest such antichain is of size $\binom{n}{\lfloor n/2\rfloor}.$
So you can't do it in fewer than $9$ days since $\binom94\geq 80>\binom84.$
But we can do the above in reverse, to get an answer from an antichain of $80$ elements.
Let $\mathcal U=\mathcal U_{9,4}$ be the set of subsets of $\{1,\dots,9\}$ of size $4.$ It is an antichain and $|\mathcal U|>80,$ For each of $j=1,\dots,80$ pick a distinct $T_j\in \mathcal U.$ Then $T_1,\dots,T_{80}$ is an antichain.
Then let $S_i=\{j\mid i\in T_j\},$ $i=1,\dots,9.$
Show that $S_1,\dots, S_9$ works.
Turns out, since $\binom93=84>80,$ we can use $\mathcal U_{9,3}$ instead. We just need an antichain of size $80.$ This does not reduce the total number of days, but each person only has to come in three days, rather than four.
In general, for a population of $N$ people, the number of days is the smallest $n$ such that $\binom n{\lfloor n/2\rfloor}\geq N.$
For example, with $10$ people, you have $n=5$ and the $$(T_i)_{i=1}^{10}=12,13,14,15,23,24,25,34,35,45$$ and: $$\begin{align} S_1&=\{1,2,3,4\}\\ S_2&=\{1,5,6,7\}\\ S_3&=\{2,5,8,9\}\\ S_4&=\{3,6,8,10\}\\ S_5&=\{4,7,9,10\} \end{align}$$