0
$\begingroup$

Find the number of all finite sequences of integers $n_1, n_2, \ldots, n_k$, such that $$ n_1 + n_2 + ⋯ + n_k = 100 $$ and such that for every $i \in \{1,\ldots,k\}$ we have $n_i \ge i$.

I have been thinking about this for days but I still do not understand how to begin. Please help.

$\endgroup$
9
  • 1
    $\begingroup$ title and body seem different -- do you want monotone sequences or $n_i \ge i$? E.g. the sequence $40,60$ is both but $60,40$ is ok for (2) but not ok for (1) $\endgroup$
    – gt6989b
    Commented Sep 18, 2020 at 14:55
  • $\begingroup$ My bad for the title $\endgroup$
    – Donovan
    Commented Sep 18, 2020 at 14:56
  • 1
    $\begingroup$ It's fine if you don't know how a nice and finished solution begins. That's why you're here in the first place. However, that doesn't mean you don't know where you should begin. There are always things you can do. Answer small parts of the problem, for instance. If we, say, fix $k=4$, can you solve the problem? How many solutions are there to $n_1+n_2+n_3+n_4=100$ if each $n_i\geq i$? What's the largest possible $k$? These kinds of questions are usually easier to answer and has the added bonus of taking you a step closer a finished solution. $\endgroup$
    – Arthur
    Commented Sep 18, 2020 at 15:03
  • 1
    $\begingroup$ In short, when you say you don't know where to begin, I don't believe you. $\endgroup$
    – Arthur
    Commented Sep 18, 2020 at 15:05
  • 1
    $\begingroup$ You can begin by trying to list them all, hundred $1$s, then ninety-eight $1$s and a $2$, the ninety-seven $1$ and a $3$, and so on. Maybe do a simple case of all the sequences that add to a small number like $5$. ($1,1,1,1,1$:$1,1,1,2$:$1,1,3$:$1,4$.$1,2,2$:$2,3$:$5$ seven of them.Then another number such as $6$.. if we start with $1$ the rest must add to $5$ we already know there are $7$. then if we start with $2$ we have $2,2,2$ or $2,4$ and $3,3$ so there are $10$. Can we figure a pattern. $\endgroup$
    – fleablood
    Commented Sep 18, 2020 at 15:11

1 Answer 1

Reset to default
2
$\begingroup$

Possible approach / might not be the fastest way.

Fix a certain $k$, then the problem becomes finding non-negative integers $a_i = n_i - i$ s.t.

$$\sum a_i = 100 - \frac{k(k+1)}{2}$$

which can be solved by stars and bars. Then just loop through all possible values of $k$. Can you finish from here (if this approach is OK with you)?

$\endgroup$
3
  • $\begingroup$ +1 beat me by 30 secs :) $\endgroup$
    – gt6989b
    Commented Sep 18, 2020 at 15:02
  • $\begingroup$ @gt6989b oh i'm sorry! :D you deleted answer is a very nice writeup. feel free to revive it. i only beat you because i left out all the nice details in your answer! $\endgroup$
    – antkam
    Commented Sep 18, 2020 at 16:10
  • $\begingroup$ Great solution! $\endgroup$
    – Donovan
    Commented Sep 19, 2020 at 23:24

You must log in to answer this question.

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