JEE Challenger
More from Permutations and Combinations
MathHardAdv 2014 • Paper 1

Distinct Ordered Tuples of Positive Integers Summing to Twenty

Let n1<n2<n3<n4<n5n_1 < n_2 < n_3 < n_4 < n_5 be positive integers satisfying the condition n1+n2+n3+n4+n5=20n_1 + n_2 + n_3 + n_4 + n_5 = 20. Determine the total number of such unique 5-tuples (n1,n2,n3,n4,n5)(n_1, n_2, n_3, n_4, n_5).

Official Numerical Answer7

Topics & Concepts

Permutations and CombinationsCombinations

Step-by-Step Solution

To find the total number of unique 5-tuples of positive integers (n1,n2,n3,n4,n5)(n_1, n_2, n_3, n_4, n_5) such that: 1≤n1<n2<n3<n4<n5andn1+n2+n3+n4+n5=201 \le n_1 < n_2 < n_3 < n_4 < n_5 \quad \text{and} \quad n_1 + n_2 + n_3 + n_4 + n_5 = 20

Method 1: Partitioning Method

The smallest set of 5 distinct positive integers is {1,2,3,4,5}\{1, 2, 3, 4, 5\}, which has a sum of: 1+2+3+4+5=151 + 2 + 3 + 4 + 5 = 15

We can express each nin_i as: ni=i+yin_i = i + y_i where yiy_i are non-negative integers.

To maintain the strict inequality n1<n2<n3<n4<n5n_1 < n_2 < n_3 < n_4 < n_5, we must have: 1+y1<2+y2<3+y3<4+y4<5+y5  ⟹  0≤y1≤y2≤y3≤y4≤y51 + y_1 < 2 + y_2 < 3 + y_3 < 4 + y_4 < 5 + y_5 \implies 0 \le y_1 \le y_2 \le y_3 \le y_4 \le y_5

Substituting ni=i+yin_i = i + y_i into the sum condition: ∑i=15ni=∑i=15(i+yi)=15+∑i=15yi=20  ⟹  ∑i=15yi=5\sum_{i=1}^{5} n_i = \sum_{i=1}^{5} (i + y_i) = 15 + \sum_{i=1}^{5} y_i = 20 \implies \sum_{i=1}^{5} y_i = 5

Thus, the problem reduces to finding the number of non-decreasing sequences of non-negative integers (y1,y2,y3,y4,y5)(y_1, y_2, y_3, y_4, y_5) such that ∑i=15yi=5\sum_{i=1}^5 y_i = 5. This is equivalent to finding the number of integer partitions of 55 into at most 5 parts.

The partitions of the integer 55 are:

  1. 55
  2. 4+14 + 1
  3. 3+23 + 2
  4. 3+1+13 + 1 + 1
  5. 2+2+12 + 2 + 1
  6. 2+1+1+12 + 1 + 1 + 1
  7. 1+1+1+1+11 + 1 + 1 + 1 + 1

There are 77 such partitions.

Method 2: Explicit Listing of 5-Tuples

Corresponding to each partition above, we construct the tuple (n1,n2,n3,n4,n5)=(1+y1,2+y2,3+y3,4+y4,5+y5)(n_1, n_2, n_3, n_4, n_5) = (1+y_1, 2+y_2, 3+y_3, 4+y_4, 5+y_5):

  1. (y1,y2,y3,y4,y5)=(0,0,0,0,5)  ⟹  (1,2,3,4,10)(y_1, y_2, y_3, y_4, y_5) = (0, 0, 0, 0, 5) \implies (1, 2, 3, 4, 10)
  2. (y1,y2,y3,y4,y5)=(0,0,0,1,4)  ⟹  (1,2,3,5,9)(y_1, y_2, y_3, y_4, y_5) = (0, 0, 0, 1, 4) \implies (1, 2, 3, 5, 9)
  3. (y1,y2,y3,y4,y5)=(0,0,0,2,3)  ⟹  (1,2,3,6,8)(y_1, y_2, y_3, y_4, y_5) = (0, 0, 0, 2, 3) \implies (1, 2, 3, 6, 8)
  4. (y1,y2,y3,y4,y5)=(0,0,1,1,3)  ⟹  (1,2,4,5,8)(y_1, y_2, y_3, y_4, y_5) = (0, 0, 1, 1, 3) \implies (1, 2, 4, 5, 8)
  5. (y1,y2,y3,y4,y5)=(0,0,1,2,2)  ⟹  (1,2,4,6,7)(y_1, y_2, y_3, y_4, y_5) = (0, 0, 1, 2, 2) \implies (1, 2, 4, 6, 7)
  6. (y1,y2,y3,y4,y5)=(0,1,1,1,2)  ⟹  (1,3,4,5,7)(y_1, y_2, y_3, y_4, y_5) = (0, 1, 1, 1, 2) \implies (1, 3, 4, 5, 7)
  7. (y1,y2,y3,y4,y5)=(1,1,1,1,1)  ⟹  (2,3,4,5,6)(y_1, y_2, y_3, y_4, y_5) = (1, 1, 1, 1, 1) \implies (2, 3, 4, 5, 6)

Each tuple clearly satisfies n1<n2<n3<n4<n5n_1 < n_2 < n_3 < n_4 < n_5 and ∑i=15ni=20\sum_{i=1}^5 n_i = 20.

Hence, the total number of such unique 5-tuples is 7.

PreviousNext