2
$\begingroup$

Let $k$ be a fixed positive integer. Let a sequence of positive integers with odd sum $(a_1,\ldots,a_n)$ be called good if for all integers $1 \leq i \leq n$, we have $\sum_{j \neq i} a_j \geq k$

Now let a good sequence be minimally good if it does not dominate any other good sequence. By dominate, I mean sequence $(a_1,a_2,\ldots,a_n)$ dominates $(b_1,b_2,\ldots,b_n)$. If $a_i \geq b_i$ for all $i$.

Is there anything interesting we can say about minimally good sequences? In particular, for a given $n$ and $k$, how many MSGs are there? Is there a formula for calculating MSGs? Is there a good algorithm for finding MSGs and what is its time-complexity?

$\endgroup$
4
  • 1
    $\begingroup$ Can you provide an example of a minimally good sequence for a small $k$, say $k=5$? $\endgroup$
    – rywit
    Sep 9, 2015 at 12:58
  • $\begingroup$ For $k = 5$, we have $(5,6)$. I modified by definition of a good sequence. I realized I misstated it. $\endgroup$
    – Halbort
    Sep 9, 2015 at 13:15
  • 1
    $\begingroup$ The odd sum makes it come out rather messy. If you like, I could post a solution to the problem without that restriction, and you could take it from there and work out the messy details? $\endgroup$
    – joriki
    Sep 9, 2015 at 16:29
  • $\begingroup$ OK that is fine. Thank you joriki. :-) $\endgroup$
    – Halbort
    Sep 9, 2015 at 18:47

1 Answer 1

Reset to default
1
$\begingroup$

As discussed in the comments, here's a solution to the problem without the restriction to odd sums.

If a sequence is minimally good, we cannot reduce any of the $a_i$, so there must be at least one sum that exactly equals $k$. Then the element not included in that sum must equal the greatest element included in the sum: If it were greater, we could reduce it by $1$ without harm, and if it were lesser, the sum that includes it instead of the greatest element would be less than $k$.

Thus, a minimally good sequence has $n-1$ elements that add up to $k$, and then another copy of the greatest of those elements. The tricky part is how to count such sequences without double-counting.

Let $j\ge2$ be the number of times the greatest element $m$ occurs. Then the remaining elements must sum to $k-(j-1)m$. There are $\binom nj$ positions for the greatest elements, and the possibilities for the remaining elements, which must all be less than $m$, can be calculated using the formula for balls in bins with limited capacity (which can be derived via inclusion-exclusion). Then the number of minimally good sequences is

$$ \sum_{m=1}^k\sum_{j=2}^n\binom nj\sum_{t=0}^{n-j}(-1)^t\binom{n-j}t\binom{n-j-1+k-(t+j-1)m}{n-j-1}\;, $$

where, following the page linked to above and contrary to convention, the binomial coefficients are taken to vanish when the upper index is less than the lower index.

If you add the restriction to odd sums, things get messy, since the sum can now be $k$ or $k+1$, and depending on details the element not included in the sum can be equal to the greatest element included in the sum or one more or one less than that.

$\endgroup$
2
  • $\begingroup$ How would I find an algorithm for computing MSGs. $\endgroup$
    – Halbort
    Sep 10, 2015 at 2:30
  • $\begingroup$ @Halbort: I thought that was implicit in the counting -- just turn each sum into a loop: For all $m$, for all $j\ge2$, find all sequences of $n-j$ elements less than $m$ that sum to $k-(j-1)m$, and insert $m$ at all possible sets of $j$ positions. $\endgroup$
    – joriki
    Sep 10, 2015 at 4:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .