Minimum number of questions needed to uniquely determine an integer partition This came up in an algebra class today, but I'll phrase it a bit differently.
Let's say Alice and Bob are playing a game. Alice thinks of an integer partition, and tells Bob the sum of the partition's parts $n$. Bob can then ask Alice some questions to determine which partition she's thinking of.
For example, suppose that Alice says $n=4$. Then the possible partitions are $4, 3+1, 2+2, 2+1+1, 1+1+1+1$. If Bob asks "What is the largest part of your partition?", then Alice might answer 2 - in this case Bob cannot uniquely determine which partition Aice is thinking of as there are two possibilities, $2+2$ and $2+1+1$. Bob can then ask "How many parts does your partition have?" and complete the game in two questions for $n=4$ (this is not necessarily minimal). Note that the same strategy won't work for $n=7$, as $3+3+1$ and $3+2+2$ are both partitions with three parts and maximum part three.
So now I ask, given $n$, what is the minimum number of questions needed to determine Alice's partition?
(By "question" I mean a question relating to the partition or its parts, returning a nonnegative integer answer. So Bob could say "How many odd numbered parts are in your partition?", but he can't say "I have a list of partitions here, what number is your partition on this list?".)
 A: To avoid the 1-question solution in the comments, I will restrict questioning to these two categories of questions:


*

*Given $S\subset\Bbb{N}$, ask "How many parts of your partition are in $S$?"

*Given $k\in\Bbb{n}$, ask "what is the $k$th highest distinct part of your partition?"
A naive strategy in this case is to first ask "What is the highest distinct part of your partition", and receiving, say, $a_0$ as an answer, then ask "How many parts of your partition are equal to $a_0$?", and repeat (asking for the 2nd part, then 3rd part, and so on) until you know the whole partition. This will take at most $\frac{4}{\sqrt2}\sqrt{n+1}$ questions, because each distinct part requires $2$ questions, and the smallest $n$ that has a partition with $k$ distinct parts is $1+2+\cdots+k = \frac{n(n+1)}2$.
More refined strategies, especially regarding paying special attention to the counts of $2$s and $1$s, could reduce this number in most cases, but I can't think of anything that works better overall.
