CAT 2018 Slot 1 Quant Q31

  • Quantitative Aptitude
  • Modern Math › Permutation & Combination
  • Medium
  • Type in the answer (TITA)
  • CAT_2018_SLOT1_QA_Q31

Question 31

How many numbers with two or more digits can be formed with the digits 1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9, so that in every such number, each digit is used at most once and the digits appear in the ascending order?

Type-in-the-answer (TITA) question: no options are given; enter the value.

Answer this question Opens in practice mode, free, no sign-in.

Show answer and solution

Answer:

502

Solution

  • No arrangement needed: Choosing any subset of digits automatically fixes their ascending order (e.g., {7,2,5}→257\{7, 2, 5\} \to 257).

  • Every subset of size k≥2k \ge 2 forms exactly 1 valid number.

  • Total subsets of 9 digits = 29=5122^9 = 512.

  • Exclude invalid subsets:

    • Empty set (00 digits): (90)=1\binom{9}{0} = 1

    • Singletons (11 digit): (91)=9\binom{9}{1} = 9

  • Answer: 512−1−9=502512 - 1 - 9 = 502.

Detailed explanation

Concept: Combinations & Binomial Identity ∑(nk)=2n\sum \binom{n}{k} = 2^n.

  1. We have 99 available non-zero digits: {1,2,3,4,5,6,7,8,9}\{1, 2, 3, 4, 5, 6, 7, 8, 9\}.

  2. The problem requires numbers where:

    • Each digit is used at most once.

    • Digits appear in strictly ascending order.

    • The number has 22 or more digits (k≥2k \ge 2).

  3. Key Mathematical Property:

    • Any selection of kk distinct digits from {1,2,…,9}\{1, 2, \dots, 9\} can be arranged in ascending order in exactly one unique way.

    • For example, choosing {4,1,8}\{4, 1, 8\} uniquely gives the 3-digit number 148148.

  4. Therefore, the number of valid kk-digit numbers is simply (9k)\binom{9}{k}.

  5. We need to sum over all allowed lengths k∈{2,3,4,5,6,7,8,9}k \in \{2, 3, 4, 5, 6, 7, 8, 9\}:

    Total=(92)+(93)+(94)+(95)+(96)+(97)+(98)+(99)\text{Total} = \binom{9}{2} + \binom{9}{3} + \binom{9}{4} + \binom{9}{5} + \binom{9}{6} + \binom{9}{7} + \binom{9}{8} + \binom{9}{9}

  6. Recall the total sum of binomial coefficients:

    ∑k=09(9k)=29=512\sum_{k=0}^{9} \binom{9}{k} = 2^9 = 512

  7. Subtract the excluded terms (k=0k = 0 and k=1k = 1):

    • (90)=1\binom{9}{0} = 1 (no digits selected)

    • (91)=9\binom{9}{1} = 9 (1-digit numbers)

  8. Evaluate the total count:

    Total=29−[(90)+(91)]=512−(1+9)=512−10=502\text{Total} = 2^9 - \left[\binom{9}{0} + \binom{9}{1}\right] = 512 - (1 + 9) = 512 - 10 = 502

Practise similar questions

Practice 1 CAT_2018_SLOT1_QA_Q31_SQ01

How many numbers with two or more digits can be formed with the digits 1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8, so that in every such number, each digit is used at most once and the digits appear in the ascending order?

Type-in-the-answer (TITA) question: no options are given; enter the value.

Show answer and solution

Answer:

247

Solution

  • Any subset of digits automatically arranges in ascending order in exactly 11 way.

  • Each subset of size k≥2k \ge 2 from the 88 digits forms a unique valid number.

  • Total number of subsets of 88 elements is 28=2562^8 = 256.

  • Exclude subsets of size 00 and size 11:

    Size 0:(80)=1\text{Size } 0: \binom{8}{0} = 1

    Size 1:(81)=8\text{Size } 1: \binom{8}{1} = 8

  • Total valid numbers: 256−1−8=247256 - 1 - 8 = 247.

Practice 2 CAT_2018_SLOT1_QA_Q31_SQ02

How many numbers with three or more digits can be formed with the digits 1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9, so that in every such number, each digit is used at most once and the digits appear in the ascending order?

Type-in-the-answer (TITA) question: no options are given; enter the value.

Show answer and solution

Answer:

466

Solution

  • Choosing any subset of kk digits uniquely determines an ascending number.

  • For lengths k≥3k \ge 3, valid numbers equal ∑k=39(9k)\sum_{k=3}^{9} \binom{9}{k}.

  • Total subsets of 99 digits is 29=5122^9 = 512.

  • Subtract excluded lengths (k=0,1,2k = 0, 1, 2):

    (90)+(91)+(92)=1+9+36=46\binom{9}{0} + \binom{9}{1} + \binom{9}{2} = 1 + 9 + 36 = 46

  • Answer: 512−46=466512 - 46 = 466.

Permutation & Combination questions from other CAT papers

  1. CAT 2025 Slot 1 Quant Q8
    A cafeteria offers 5 types of sandwiches. Moreover, for each type of sandwich, a customer can choose one of…
  2. CAT 2024 Slot 1 Quant Q4
    The sum of all four-digit numbers that can be formed with the distinct non-zero digits a, b, c, and d , with…
  3. CAT 2024 Slot 2 Quant Q18
    P, Q, R and S are four towns. One can travel between P and Q along 3 direct paths, between Q and S along 4…
  4. CAT 2024 Slot 3 Quant Q18
    The number of all positive integers up to 500 with non-repeating digits is
  5. CAT 2023 Slot 1 Quant Q21
    The number of all natural numbers up to 1000 with non-repeating digits is

Practise this question with timing, notes and your mistake notebook.

Practise in PrepSoc