1

I would like some hints about how solve this kind of problems. I am not asking a detailed solution, just how the problem is classified (if it is) and what part of math I should take a look.

Given positive integer $n$ and $s$, we want to construct a sequence of positive integers $a_1 > a_2 \ge a_3 \ge ...\ge a_n$ such that their sum is $s$. Note that we require that the maximum, $a_1$, is unique, while other values can have duplicates.

Problem: What is the minimum value of $a_1$? Let this minimum be $f(n,s)$.

Example: if $n=10$ integers and $s=100$, I can find by eye this: $11, 10, 10, 10, 10, 10, 10, 10, 10, 9$. So the answer is $f(10,100)=11$.

It's easy, but in general? I imagine some method exists. I do not need it explained here, I want just know where to look (what to look) to solve this kind of problems.

I think it is probably some sort of optimization problem, but more precise details are welcome.

(this is not homework or job related or anything, in case it is necessary specify it)

Benjamin Wang
  • 3,920
john_smith
  • 13
  • I interpret that your problem is to find the maximum of a list. You can do this by first sorting the list. Have you studied algorithms like quicksort? However, if you only want the job done, most programming languages have built-in sorting algorithms. By the way, I don't see how the knowledge of the sum is relevant. – Benjamin Wang Oct 01 '23 at 19:34
  • 1
    @benjamin-wang thanks for the comment but your interpretation is not correct. Please tell me if I could claryfy the post. I have a list but I do not know the individual values, only their sum and how many they are. – john_smith Oct 01 '23 at 19:50
  • I've clarified your problem. See if you like it. – Benjamin Wang Oct 01 '23 at 20:52
  • @benjamin-wang Surely now it seems much more professional. I had no idea "bucket" was a math term. It feels like it was written by someone else because I am not a mathematician, but the important thing is obtain some hint for the problem; and if this format attracts more attention, so be it. – john_smith Oct 01 '23 at 21:54
  • Thanks. Now you see that even non mathematicians can benefit from precise communication. And sorry, "bucket" is not a standardised math term :) (although "partition" is) – Benjamin Wang Oct 01 '23 at 22:15

2 Answers2

1

Trying $n=10$ and $s=100$ and getting $f=11$ is already a good first step. You can already see that $f(n,s)$ is probably close to $k:=\lfloor s/n\rfloor$ (I used the floor function notation).

Try $s=101$. What about $s=102$ (and other cases)? Can you see some patterns and turn this into a proof for a general formula?

Don't forget to take care of invalid cases like $n>s$ (and other cases).

In your problem, the minimum increment is always $1$. However, in a harder version, parallel task scheduling, the minimum increment is variable according to how long the "task" takes.

Benjamin Wang
  • 3,920
  • 1
    Well I had already an idea to solve it by writing a program, first divide sum by number of integers and if it is fractionary, regroup the decimal part in the first integers of the list, and if there are more than 1 just increase the 1st and decrease the last of the increased bloc (or something similar). But this is empiric, I would like to know how this kind of problem is called and which part of math studies it. – john_smith Oct 01 '23 at 21:59
1

You can solve the problem via integer linear programming. The problem is to minimize $a_1$ subject to linear constraints \begin{align} a_1 &\ge a_2 + 1 \\ a_i &\ge a_{i+1} &&\text{for $i\in\{2,\dots,n-1\}$} \\ a_n &\ge 0 \\ \sum_{i=1}^n a_i &= s \end{align}

RobPratt
  • 45,619