CAT 2017 Slot 1 Quant Q32

  • Quantitative Aptitude
  • Modern Math › Permutation & Combination
  • Medium
  • Multiple choice
  • CAT_2017_SLOT1_QA_Q32

Question 32

In how many ways can 77 identical erasers be distributed among 44 kids in such a way that each kid gets at least one eraser but nobody gets more than 33 erasers?

  1. A

    1616

    Answer A in PrepSoc practice
  2. B

    2020

    Answer B in PrepSoc practice
  3. C

    1414

    Answer C in PrepSoc practice
  4. D

    1515

    Answer D in PrepSoc practice

Answer this questionOr tap an option. Opens in practice mode, free, no sign-in.

Show answer and solution

Answer: (A)

1616

Solution

  • Pre-allocate 1 eraser per kid: Leaves 7−4=37 - 4 = 3 erasers for 4 kids with each kid getting at most 2 extra (yi≤2y_i \le 2).

  • Unrestricted Stars & Bars: (3+4−13)=(63)=20\binom{3 + 4 - 1}{3} = \binom{6}{3} = 20 ways.

  • Subtract violation: The only violation is giving all 3 extra erasers to one kid   ⟹  4\implies 4 ways.

  • Valid ways=20−4=16\text{Valid ways} = 20 - 4 = 16 (Option 1).

Detailed explanation

Concept: Stars and Bars (Balls and Urns), Complementary Counting, and Integer Partitions under Upper-Bound Constraints.

  1. Model the problem algebraically:

    • Let x1,x2,x3,x4x_1, x_2, x_3, x_4 denote the number of erasers distributed to the 4 kids.

    • We need to find the number of integer solutions to:

      x1+x2+x3+x4=7x_1 + x_2 + x_3 + x_4 = 7

    • Subject to the constraints:

      1≤xi≤3for each i∈{1,2,3,4}1 \le x_i \le 3 \quad \text{for each } i \in \{1, 2, 3, 4\}

  2. Shift the variables to non-negative integers:

    • First give 11 eraser to each kid to guarantee the minimum requirement of at least 1 eraser per kid.

    • Let yi=xi−1y_i = x_i - 1, where yiy_i is the number of additional erasers given to kid ii.

    • The constraints on yiy_i become:

      0≤yi≤2for each i∈{1,2,3,4}0 \le y_i \le 2 \quad \text{for each } i \in \{1, 2, 3, 4\}

    • The remaining erasers to distribute:

      y1+y2+y3+y4=7−4=3y_1 + y_2 + y_3 + y_4 = 7 - 4 = 3

  3. Method 1: Stars and Bars with Complementary Counting:

    • The total number of non-negative integer solutions to y1+y2+y3+y4=3y_1 + y_2 + y_3 + y_4 = 3 without the upper-bound restriction is:

      (n+r−1r)=(3+4−13)=(63)=6×5×43×2×1=20\binom{n + r - 1}{r} = \binom{3 + 4 - 1}{3} = \binom{6}{3} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20

    • Identify invalid distributions (violating yi≤2y_i \le 2):

      • Since the sum of all four yiy_i is only 33, a violation occurs if and only if one kid receives yi≥3  ⟹  yi=3y_i \ge 3 \implies y_i = 3.

      • When one kid receives 33 additional erasers, all other three kids receive 00.

      • The kid who receives 33 can be chosen in (41)=4\binom{4}{1} = 4 ways:

        (3,0,0,0),(0,3,0,0),(0,0,3,0),(0,0,0,3)(3, 0, 0, 0), (0, 3, 0, 0), (0, 0, 3, 0), (0, 0, 0, 3)

    • Subtract invalid distributions from the total:

      Valid Ways=20−4=16\text{Valid Ways} = 20 - 4 = 16

  4. Method 2: Integer Partitions Verification:

    • Partition 77 into 44 parts where each part ∈{1,2,3}\in \{1, 2, 3\}:
Partition TypePart SizesNumber of Permutations / Arrangements
Case 13+2+1+1=73 + 2 + 1 + 1 = 74!1!×1!×2!=242=12\frac{4!}{1! \times 1! \times 2!} = \frac{24}{2} = 12
Case 22+2+2+1=72 + 2 + 2 + 1 = 74!3!×1!=246=4\frac{4!}{3! \times 1!} = \frac{24}{6} = 4
  • Total number of valid distributions =12+4=16= 12 + 4 = 16.
  1. Conclusion:

    • There are 1616 valid ways to distribute the erasers.

    • This corresponds to Option 1.

Practise similar questions

Practice 1 CAT_2017_SLOT1_QA_Q32_SQ01

In how many ways can 88 identical pencils be distributed among 44 children in such a way that each child gets at least one pencil but no child gets more than 33 pencils?

  1. A

    1919

  2. B

    2121

  3. C

    1717

  4. D

    1515

Show answer and solution

Answer: (A)

1919

Solution

  • Allocate 11 pencil per child: Remaining pencils =8−4=4= 8 - 4 = 4 with yi≤2y_i \le 2.

  • Unrestricted Stars and Bars solutions: (4+4−14)=(74)=35\binom{4 + 4 - 1}{4} = \binom{7}{4} = 35.

  • Violations with one child having yi≥3y_i \ge 3: (41)×(4−3+4−11)=4×4=16\binom{4}{1} \times \binom{4 - 3 + 4 - 1}{1} = 4 \times 4 = 16.

  • Valid distributions =35−16=19= 35 - 16 = 19 (Option 1).

Practice 2 CAT_2017_SLOT1_QA_Q32_SQ02

In how many ways can 99 identical chocolates be distributed among 44 friends in such a way that each friend receives at least one chocolate but no one receives more than 33 chocolates?

  1. A

    1414

  2. B

    1616

  3. C

    1818

  4. D

    2020

Show answer and solution

Answer: (B)

1616

Solution

  • Allocate 11 chocolate per friend: Leaves 9−4=59 - 4 = 5 extra chocolates with yi≤2y_i \le 2.

  • Unrestricted ways: (5+4−15)=(85)=56\binom{5 + 4 - 1}{5} = \binom{8}{5} = 56.

  • Single-friend violation (yi≥3y_i \ge 3): (41)×(5−3+32)=4×(52)=40\binom{4}{1} \times \binom{5 - 3 + 3}{2} = 4 \times \binom{5}{2} = 40.

  • Valid ways =56−40=16= 56 - 40 = 16 (Option 2).

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