4
$\begingroup$

Let $n_1<n_2<n_3<n_4<n_5$ be positive integers such that $n_1+n_2+n_3+n_4+n_5=20$.Then what is the number of such distinct arrangements $(n_1,n_2,n_3,n_4,n_5)$?

My Approach :

I assumed

$n_1=t_0+1$

$n_2=n_1+t_1+1$

$n_3=n_2+t_2+1$

$n_4=n_3+t_3+1$

$n_5=n_4+t_4+1$

Where $t_0,t_1,t_2,t_3,t_4 \ge 0$

Now the sum becomes :

$5t_0+4t_1+3t_2+2t_3+t_4=5$

After this, I put the values of $t_i$s $0,1,..$ and so on, and therefore found $7$ Solutions.

My question : Is there another way to solve this question, because as this question was asked in a competitive exam (JEE Advanced), This a very long solution.

$\endgroup$
5
  • $\begingroup$ If I have to solve this fast,I use tree (graph) to separate solutions . $\endgroup$
    – Khosrotash
    Mar 9, 2017 at 17:15
  • $\begingroup$ Yes, but do you have any precise mathematical way? $\endgroup$ Mar 9, 2017 at 17:25
  • $\begingroup$ What if question was n1+n2+n3+n4+n5=50 or 100 or any bigger number, how would have you solved it? $\endgroup$ Mar 9, 2017 at 17:27
  • $\begingroup$ Are restrict variable in $5t_0+4t_1+3t_2+2t_3+t_4=5$ such as $$5t_0\leq 5 \to t_0=0,1\\4t_1\leq 5 \to t_1=0,1 \\ 3t_2\leq 5 \to t_2=0,1\\2t_3\leq5 \to t_3=0,1,2$$ to reduce the problem ? $\endgroup$
    – Khosrotash
    Mar 9, 2017 at 17:39
  • $\begingroup$ Yes, it'll help for small numbers. $\endgroup$ Mar 9, 2017 at 17:42

3 Answers 3

5
$\begingroup$

I would say that you start with $1+2+3+4+5=15$ and have to distribute 5 more. And the 5 more have to satisfy the rule that you can't distribute more to the $i$th position than the $i+1$th position.

From that I can come up with the solutions for distributing those 5 faster than I can write them down. They are obviously $(1,1,1,1,1), (0,1,1,1,2), (0,0,1,1,3), (0,0,1,2,2), (0,0,0,1,4), (0,0,0,2,3), (0,0,0,0,5)$ and I count them.

This is obviously a one-off trick and that is appropriate to the actual values chosen. However the described rule comes down to counting the number of partitions of 5. See https://en.wikipedia.org/wiki/Partition_(number_theory) for more on partitions.

As for your harder question with $n_1+n_2+n_3+n_4+n_5=50$, that can be calculated recursively. You want the number of partitions of $35$ into no more than $5$ groups. Well, define $p_{i,k}$ to be the number of partitions of $i$ into no more than $k$ groups. We have the following rules:

  1. $p_{0,k} = 1$ (just a string of 0s)
  2. $p_{i,1} = 1$ (all go into one)
  3. $p_{i,k+1} = p_{i,k} + p_{i-k,k+1}$ (add one to everything)

From here we can work out rules like:

$p_{i,1} = 1$
$p_{i,2} = i+1$
$p_{i,3} = 1 + 2 + ... + (i+1) = (i+1)(i+2)/2$

And so on until we have a formula to use. But finishing that would be harder and not appropriate for the place it appeared. :-)

$\endgroup$
4
  • $\begingroup$ Should that be 45 instead of 35. $\endgroup$ Mar 9, 2017 at 18:02
  • $\begingroup$ @JaideepKhare No, because 1+2+3+4+5 = 15. So we only have 35 more to divide. Just like for 20 we only had 5 left. $\endgroup$
    – btilly
    Mar 9, 2017 at 18:42
  • $\begingroup$ OK, understood. Thanks! $\endgroup$ Mar 9, 2017 at 18:46
  • $\begingroup$ +1. Note that if the sum had been say $25$ rather than $20$ then the answer would have been the number of partitions of $25-\frac{5(5+1)}2=10$ into up to $5$ parts which I think is $30$ $\endgroup$
    – Henry
    Sep 2, 2023 at 23:37
1
$\begingroup$

We can use casework. It is important to be organized to make sure you don't miss any cases.

  • Smallest is 1 and then 2:
    • $\{1, 2, 3, 4, 10\}$
    • $\{1, 2, 3, 5, 9\}$
    • $\{1, 2, 3, 6, 8\}$
    • $\{1, 2, 4, 5, 8\}$
    • $\{1, 2, 4, 6, 7\}$
    • We cannot have repeats so that is all
  • Smallest is 1 and then 3:
    • $\{1, 3, 4, 5, 7\}$
  • Smallest is 2
    • $\{2, 3, 4, 5, 6\}$

Total, there are $\boxed{7}$ solutions. Surprisingly easy for an JEE problem. This can be solved much faster if you just start listing all numbers.

$\endgroup$
2
  • $\begingroup$ Did you change a really big number to 20? If you did then this won't work. I just answered the given problem. $\endgroup$
    – Nairit
    Mar 9, 2017 at 17:45
  • $\begingroup$ No, I didn't. In that case even my solution won't work.I was just thinking the possibilities. $\endgroup$ Mar 9, 2017 at 17:48
1
$\begingroup$

Let $n_1<n_2<n_3<n_4<n_5$ be positive integers such that $n_1+n_2+n_3+n_4+n_5=20$.Then what is the number of such distinct arrangements $(n_1,n_2,n_3,n_4,n_5)$?

Alternative approach:

For $~i \in \{2,3,4,5\},~$ let $~y_i~$ denote $n_i - n_{i-1}.$

Then:

  • $~n_1 \geq 1.~$
  • $y_2,y_3,y_4,y_5,~$ are all required to be positive integers.
  • $~n_2 = n_1 + y_1.~$
  • $~n_3 = n_2 + y_2 = n_1 + y_1 + y_2.$
  • Similarly, $~n_4 = n_1 + y_1 + y_2 + y_3.$
  • Similarly, $~n_5 = n_1 + y_1 + y_2 + y_3 + y_4.$

Therefore, you need all positive integer solutions to

$$5n_1 + 4y_2 + 3y_3 + 2y_4 + y_5 = 20. \tag1 $$

Notice that if $~(n_1,y_2,y_3,y_4,y_5) = (1,1,1,1,1),~$ then $~x_1 + y_2 + \cdots + y_5 = 15.$

Let

  • $z_1 = n_1 - 1.$
  • $z_i = y_i - 1 ~: ~i \in \{2,3,4,5\}.$

So, the problem has been reduced to determining the number of non-negative integer solutions to

$$5z_1 + 4z_2 + 3z_3 + 2z_4 + z_5 = 5. \tag1 $$

At a glance, the possibilities for $~(z_1, \cdots, z_5)~$ are:

  • $(1,0,0,0,0).$
  • $(0,1,0,0,1).$
  • $(0,0,1,1,0).$
  • $(0,0,1,0,2).$
  • $(0,0,0,2,1).$
  • $(0,0,0,1,3).$
  • $(0,0,0,0,5).$

So, there are $~7~$ possibilities.

$\endgroup$

You must log in to answer this question.

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