MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose you have a partition p of n into atmost k parts, say $$\{i_1, i_2, ..., i_j, ..., i_{k-1}\}$$ For example $\{1, 4\}$ is a partition of 10 into 3 parts (in this notation i am specifying the partition points, not the part lengths, i.e {1} , {2,3,4}, {5,6,7,8,9,10} are the three partitions)

Consider $$I(n, k) = min_p \sum_j {\frac {(i_{j+1} - i_j)} {2^{j}}}$$

Can we say anything meaningful about a lower bound on $I(n, k)$? I am specifically interested in the question when k is a function of n that grows slowly, like $log \ n$, or slower than $n^{1/{\epsilon}}$ for any ${\epsilon} > 0$.

I'm actually not sure if anything meaningful can be said here, so any ideas on how to approach this question would be very welcome

Any pointers to literature in this regard or a counter example showing no meaningful bound exists will be great. Intuitively, it seems like if i pick a partition of size $log \ n$ for example, no matter how i choose such a partition I cannot have $I(n, k) = O(1)$ for example. So I would probably guess $I(n,O(log\ n)) = O(log \ n)$.

share|cite|improve this question
It seems your question is not about partitions of integers but just about sequences $1\le i_1\lt\cdots\lt i_{k-1}\lt n$. For given $k$, the minimum occurs when the sequence is $1,2,\ldots,k{-}1$. But one of us must be missing something. – Brendan McKay Apr 22 '14 at 5:13
I think the problem statement was confusing. Your solution is right as stated. – Ram Apr 22 '14 at 7:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.