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?".)

  • 2
    $\begingroup$ Definitely not what you want, but "What is the sum of your first partition times $n^0$, your second partition times $n^1$, your third partition times $n^2$, up to your last partition times $n^{m-1}$, if $m$ is the number of parts in your partition?" $\endgroup$ – peterwhy Oct 7 '13 at 23:55
  • $\begingroup$ Ahaha yeah, amusing but not what I want :). The topic we covered was Jordan normal form, and we were discussing the decomposition of a matrix into a direct sum of (left-shift + dilation) blocks. He then started listing the possibilities for the block sizes and mentioned that the minimal polynomial (analogous to max part) and dimension of the 0-eigenspace (analogous to number of parts) can't be used to determine uniquely what all the block sizes will be. And that got me wondering. $\endgroup$ – Sp3000 Oct 8 '13 at 0:19
  • $\begingroup$ In terms of the Jordan form, knowing the algebraic, geometric multiplicities and the minimal polynomial is sufficient to determine the Jordan form up to $6\times 6$ matrices. Past that, we need more information (precisely because of the partition example you gave for $n=7$). $\endgroup$ – EuYu Oct 8 '13 at 0:37

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.