This is a curiosity question.
Recently I stumbled across the following problem :
Given three integers $k,m, n$ such that $m+k\leq n$. A friend chooses a subset $S\subseteq\lbrace1,\ldots,N\rbrace$ with $k$ elements, and you have to guess what it is. You can ask him specific questions of the form: for each question you choose a subset $G \subseteq\lbrace1,\ldots,N\rbrace$ with $m$ elements and ask him does it have elements in common with $G$?, and you get an answer "Yes" or "No". How many questions do you need to find the subset?
Attempt
I was working on this question for some time without any breakthrough, let $f(n,m,k)$ be the minimal number of questions needed. I was particularly interested in $f(8,4,4)$. I managed to find a formula for very specific cases for example :
- Obviously $f(n,m,0)=0$
- $f(n,n-1,1)=n-1$ and $f(n,1,k)=n-1$
- $f(n,n-2,1)=f(n,2,1)=\lfloor \frac n 2 \rfloor+1$
- Some complicated formulas for $k=2$ but I am not sure if they are correct nothing for $k\geq 3$.
- It seems that $f(n,m,k)=f(n,n-m,k)$ but I could not prove it.
I added the condition $m+k\leq n$ because sometimes, it's not possible to find the subset (I think it's sufficient to ensure the existence of a solution, but I am not sure if it's necessary ).
Question : Is there an algorithm to solve the problem ? to compute $f(n,m,k)$ ? or just any formulas for $k=3,4$?