Combinatorics: Selection of Candidates

CAT 1999 Slot 1 · QA · Medium · Permutations and Combinations

For a scholarship, at most nn candidates out of 2n+12n + 1 can be selected. If the number of different ways of selection of at least one candidate is 6363, the maximum number of candidates that can be selected for the scholarship is

  1. A.

    3

  2. B.

    4

  3. C.

    6

  4. D.

    5

Answer

A

Explanation

Number of ways to select 11 to nn candidates from 2n+12n+1 is: (2n+11)+(2n+12)++(2n+1n)=63\binom{2n+1}{1} + \binom{2n+1}{2} + \dots + \binom{2n+1}{n} = 63. By symmetry, k=02n+1(2n+1k)=22n+1\sum_{k=0}^{2n+1} \binom{2n+1}{k} = 2^{2n+1}. Also (2n+10)+k=1n(2n+1k)+k=n+12n+1(2n+1k)=22n+1\binom{2n+1}{0} + \sum_{k=1}^n \binom{2n+1}{k} + \sum_{k=n+1}^{2n+1} \binom{2n+1}{k} = 2^{2n+1}. Since k=1n(2n+1k)=k=n+12n(2n+1k)\sum_{k=1}^n \binom{2n+1}{k} = \sum_{k=n+1}^{2n} \binom{2n+1}{k}, we have 1+2(63)+1=22n+1    128=22n+1    2n+1=7    n=31 + 2(63) + 1 = 2^{2n+1} \implies 128 = 2^{2n+1} \implies 2n+1 = 7 \implies n = 3.

Practise this under exam conditions

Sign in to solve it with a live timer, the on-screen CAT calculator, and streak and accuracy tracking across every question you attempt.

Solve in the workspace