The problem is the following:
Alex and Anna play a game. Alex picks n distinct real numbers a1,a2,… ,an and a bijective function
f : {1,2,…,n} -> {a1,a2,… ,an}. Anna, which only knows the number n, has to guess the function. For that, at each step, she picks a proper subset A of the domain and Alex tells her the elements of the set f(A). Find the minimum number of steps after which Anna can determine the function f.
I've encountered this problem in a math magazine and I have no idea how to solve it, so I was hoping that you could give me a hint. I first thought of an induction proof but i don't know how to start.
I don't know how to prove that this is optimal but I have a method that can determine the function in $\lfloor log_{2}(n) \rfloor + 1$ steps.
First, convert the numbers in $\{1,2,\dots, n\}$ into their binary representation, e.g., $9_{10} = 1001_{2}$ where the subscript represents the base of the number system used. Then at step $j$ you select the numbers that have a $1$ at the $j$-th position on the binary representation of the number, e.g., $11_{10} = 1011_{2}$ you select the number $11_{10}$ on the first, second and fourth step. For example, if $n=16$ the binary represenation of the numbers $1,\dots, n$ are \begin{align} 1_{10} &= 00001_{2} \\ 2_{10} &= 00010_{2} \\ 3_{10} &= 00011_{2} \\ 4_{10} &= 00100_{2} \\ 5_{10} &= 00101_{2} \\ 6_{10} &= 00110_{2} \\ 7_{10} &= 00111_{2} \\ 8_{10} &= 01000_{2} \\ 9_{10} &= 01001_{2} \\ 10_{10} &= 01010_{2} \\ 11_{10} &= 01011_{2} \\ 12_{10} &= 01100_{2} \\ 13_{10} &= 01101_{2} \\ 14_{10} &= 01110_{2} \\ 15_{10} &= 01111_{2} \\ 16_{10} &= 10000_{2} \\ \end{align} and the sequence of guesses are: \begin{align} \text{step 1: }& A=\{1,3,5,7,9,11,13,15\} \\ \text{step 2: }& A=\{2,3,6,7,10,11,14,15\} \\ \text{step 3: }& A=\{4,5,6,7,12,13,14,15\} \\ \text{step 4: }& A=\{8,9,10,11,12,13,14,15\} \\ \text{step 5: }& A=\{16\} \end{align} As an example, let us assume that after our guesses Alex told us that number $x$ appears in steps 2,3,4 and not in steps 1 and 5. Since $f$ is a bijection this can only occur if the number we selected was in steps 2,3,4 and not in steps 1 and 5. We can uniquely determine that number to be $01110_{2} = 13_{10}$ and therefore we know that $f(13_{10}) = x$. The same reasoning holds for all the other numbers. The number of steps needed is the number of digits of $n$ in base $2$ which is equal to $\lfloor log_{2}(n) \rfloor + 1$.