1
$\begingroup$

Let me put this into an example.

We have an array of the first $r$ (example $r=7$) natural numbers;

$1, 2, 3, 4, 5, 6, 7$

and given $k=3$, so you get to select any three integers from the pool above. Taken $1$, $6$ and $7$, we have their sum $14$. We get to partition this number ($14$) such that its $k$ parts all appear in the array above, like $14=2+5+7=3+4+7$ and so on

In this manner, which $k$ numbers' sum do you think can be partitioned into the most number of $k$ integers, in which any part can be at most $r$ from that array? Let me guess, this should be the sum of the last $k$ integers in the pool, right?

BTW I've used the terms pool and array, and integer and natural number in their same contexts. Sorry for that.


Edit:

Yes, I guess it involves partitioning of the numbers' sum into distinct $k$ parts of which the largest part $r$ is the largest number in the array. Therefore, reinstating my previous example, we have $Q(14, 3:7)$ where 7 is the largest number in the array, consequently no part among the $k(=3)$ parts can exceed the number 7.

By the way, I remember having seen an asymptotic formula for $Q(n, k:r)$. I don't remember where that was. I'll let everyone know as soon as I find out.

To put this question in another way, which $k$ numbers' sum from the array (of the first $r$ natural numbers, in ascending order) will have the greatest number of $k$ distinct partitions with each part equal to or lesser than $r$?

  • 1
    You didn't state whether the integers need to be different, but it seems that you're assuming they are. In that case: No, certainly not the last $k$; in fact their sum is unique since every other sum is necessarily smaller. If the integers need not be different, then the most central sum (in this case $4+4+4=12$) would have the most representations, and I strongly suspect that this is also the case if they have to be different.2012-03-13
  • 0
    Remember the example of tossing two dice (so $k=2$). It is a familiar fact that the sum of $7$ occurs in the largest number of ways.2012-03-13
  • 0
    @joriki: Yes, that's right. As a matter of fact,what I've posted above is (I guess) an expansion of your post. So, can it be the first $k$ integers (probably not)? Or the $k$ integers in the middle?2012-03-14
  • 0
    @André Nicolas: I don't understand what you're getting at.2012-03-14
  • 0
    @Mach9: I have merged your account "Xorra" into your account "Mach9". However I don't see an account named "Sushruth". Can you provide a link to the account page?2012-03-14
  • 0
    @Mach: I was trying to use a more familiar example to persuade the OP that the answer would be "in the middle," not at the large end.2012-03-14
  • 0
    @André Nicolas: I see...2012-03-14
  • 0
    @Zev Chonoles: Find my previous account [here](http://math.stackexchange.com/users/24023/sushruth)2012-03-14
  • 0
    Your edit appears to be contradictory. The first sentence seems to require that the largest part is the largest number in the "array" whereas the last paragraph says "at most". Also it's not clear to me what it means to put "at most" in parentheses. Is it at most or not?2012-03-14
  • 0
    @joriki At most $r$, well, that's what I meant.2012-03-14
  • 1
    @Mach9: Please edit the question accordingly. People shouldn't have to burrow to the end of the comments in order to understand the question.2012-03-14
  • 0
    I theorize that the number must either be a sum of the $k$ natural numbers from the $k$th number (i.e. in the example $(k=3)$, from the $3$rd number, consequently the sum of $3, 4, 5 (=12)$ in the array) else the middle $k$ numbers. Are any one of these a right conjecture?2012-03-14
  • 0
    I'm not adding this comment to my previous as an edit, as I want this comment to be distinct from the above. In any case, I believe the first conjecture about the sum of the $k$ natural numbers from the $k$th number in the array is wrong, as when (in the example) $k=5$ there are only three numbers left to select. So, this must be a false conjecture, and in this case, the answer must be the other conjecture (see my post above).2012-03-14
  • 0
    @Mach9: I'm afraid I don't understand the request you made in your flag to the moderators. The original *answer* post you made, that consisted of the material that became an edit to the question as well as two comments, has already been deleted.2012-03-15
  • 0
    @Zev Chonoles: Whoops, I didn't realise that post had been deleted.2012-03-20
  • 0
    Is Theorem 4 [here](http://journals.cambridge.org/download.php?file=%2FBAZ%2FBAZ36_01%2FS0004972700026320a.pdf&code=6758d66661b32275c3e652438a6bb5dd) the right asymptotic equation for this post, (assuming, as per my conjecture on March 14, 18:40, with slight modification) that $n$ (in the equation) is $(r+1)k/2$ (from my example in question) (floor/ceiling of given expression for the smaller or greater value). However, the smaller or greater values don't seem to as both yield the same result.2012-03-20

0 Answers 0