JEE Mathematics Permutations and Combinations MCQs Set 26

Answer: (c) 31

Explanation:
1. The exponent of 2 in \( 33! \) is \( \left\lfloor\frac{33}2\right\rfloor+\left\lfloor\frac{33}4\right\rfloor+\left\lfloor\frac{33}8\right\rfloor+\left\lfloor\frac{33}{16}\right\rfloor+\left\lfloor\frac{33}{32}\right\rfloor \).
2. \( =16+8+4+2+1=31 \).

Teacher's Note:
1. Legendre's formula gives the exponent of a prime in a factorial.
2. Stop when \( p^k>n \).

Answer: (a) 165

Explanation:
1. Write \( a=2p+1,\ b=2q+1,\ c=2r+1,\ d=2s+1 \) with \( p,q,r,s\ge0 \).
2. Then \( 2(p+q+r+s)+4=20 \), so \( p+q+r+s=8 \).
3. The number of non-negative integral solutions is \( {}^{8+4-1}C_{4-1}={}^{11}C_3=165 \).

Teacher's Note:
1. Substituting \( 2p+1 \) for odd numbers reduces the problem to non-negative solutions.
2. Use \( {}^{m+k-1}C_{k-1} \) for \( k \) variables summing to \( m \).

Answer: (d) 5292

Explanation:
1. The middle digit \( m \) must exceed the other four digits, which are chosen from \( 0,1,\dots,m-1 \), so \( m\ge4 \).
2. For a given \( m \), arranging 4 digits chosen from the \( m \) smaller digits in the four places gives \( {}^mP_4 \) arrangements; those with 0 in the first place number \( {}^{m-1}P_3 \) and must be removed.
3. Total \( =\sum_{m=4}^{9}\left({}^mP_4-{}^{m-1}P_3\right)=18+96+300+720+1470+2688=5292 \).

Teacher's Note:
1. A number cannot begin with 0, so subtract arrangements with 0 in the first place.
2. Option (a) forgets this subtraction.

Answer: (d) \( 36\times55^3 \)

Explanation:
1. Consider the columns separately. In a column that is not the thousands, the two digits \( (x,y) \) with \( x+y\le9 \) (no carry) can be chosen in \( 10+9+\dots+1=55 \) ways.
2. In the thousands column both digits must be at least 1 (each number has 4 digits) and \( x+y\le9 \): \( 8+7+\dots+1=36 \) ways.
3. The total number of ways is \( 55\times55\times55\times36=36\times55^3 \).

Teacher's Note:
1. Treat each column independently, since there is no carry.
2. The leading digits cannot be 0.

Answer: (d) \( \frac{(n-1)^2}4 \)

Explanation:
1. For three numbers \( a,b,c \) in A.P., \( a+c=2b \), so \( a \) and \( c \) have the same parity (both odd or both even).
2. With \( n=2m+1 \) there are \( m+1 \) odd and \( m \) even numbers. Choosing 2 numbers of the same parity gives \( {}^{m+1}C_2+{}^mC_2=\frac{(m+1)m}2+\frac{m(m-1)}2=m^2 \) ways, and the middle term is then fixed.
3. So the number of A.P.s is \( m^2=\left(\frac{n-1}2\right)^2=\frac{(n-1)^2}4 \). Check \( n=3 \): only \( 1,2,3 \), and \( \frac{4}4=1 \).

Teacher's Note:
1. A pair of numbers of equal parity determines the middle term.
2. Test with a small odd \( n \).

Answer: (d) All of (i), (ii), (iii) and (iv)

Explanation:
1. If \( z=k+1 \), then \( x \) and \( y \) can each be any of \( 1,\dots,k \), giving \( k^2 \) choices. Summing over \( k=1,\dots,n \): \( 1^2+2^2+\dots+n^2=\frac{n(n+1)(2n+1)}6 \). So (iii) is correct.
2. Alternatively, count by the cases \( x=y<z \) (\( {}^{n+1}C_2 \) ways), and \( x<y<z \) or \( y<x<z \) (\( 2\cdot{}^{n+1}C_3 \) ways). This gives (ii).
3. Simplifying, \( \frac{n(n+1)(2n+1)}6 \) also equals \( {}^{n+1}C_3+{}^{n+2}C_3 \) and \( 2\,{}^{n+2}C_3-{}^{n+1}C_2 \). A check for \( n=3 \): all four expressions equal 14.

Teacher's Note:
1. Count by the value of the largest element \( z \) first.
2. Verify the closed forms with a small value such as \( n=3 \).

Answer: (a) (i), (ii) and (iii) only

Explanation:
1. Total triangles: \( {}^nC_3 \). Triangles with two sides common to the polygon: \( n \). Triangles with exactly one polygon side: \( n(n-4) \).
2. Required number \( ={}^nC_3-n-n(n-4)=\frac{n(n-1)(n-2)}6-n(n-3)=\frac n6(n-4)(n-5)=\frac n{n-3}\,{}^{n-3}C_3 \).
3. Another count gives \( {}^{n-4}C_2+{}^{n-3}C_3 \). Check for \( n=6 \) (two triangles: \( A_1A_3A_5 \) and \( A_2A_4A_6 \)): \( \frac{6\cdot2\cdot1}6=2 \) and \( {}^2C_2+{}^3C_3=2 \), whereas \( {}^{8}C_3=56 \) is wrong.

Teacher's Note:
1. Subtract triangles that use two polygon sides and those that use exactly one polygon side from the total.
2. Test with \( n=6 \): only two triangles have no common side.

Answer: (a) All of (i), (ii), (iii) and (iv)

Explanation:
1. Multiply and divide by the missing factors: \( E=\frac{(4n)!}{(2n)!\,(2n+2)(2n+4)\cdots(4n)}=\frac{(4n)!}{(2n)!\,2^n\,(n+1)(n+2)\cdots(2n)}=\frac1{2^n}\cdot\frac{(4n)!\,n!}{(2n)!\,(2n)!} \).
2. So \( 2^nE=n!\,\frac{(4n)!}{(2n)!(2n)!}=n!\,{}^{4n}C_{2n} \). Hence \( 2^nE \) is divisible by both \( {}^{4n}C_{2n} \) and \( n! \) (statements (i), (ii)).
3. \( \frac{2^nE}{n!}={}^{4n}C_{2n} \) is a positive integer (iii).
4. \( \frac{2^nE}{(4n)!}=\frac{n!}{(2n)!\,(2n)!} \), which is less than 1 for \( n>1 \), so it is not an integer (iv). All four are correct.

Teacher's Note:
1. Insert the even factors to turn the product into a ratio of factorials.
2. \( (2n+2)(2n+4)\cdots(4n)=2^n(n+1)(n+2)\cdots(2n) \).

Answer: (a) (i), (ii) and (iii)

Explanation:
1. A strictly increasing function is determined by choosing 3 distinct elements of \( B \): \( {}^7C_3=35 \). Statement (i) is true.
2. Similarly, a strictly decreasing function is determined by choosing 3 elements of \( B \), also \( {}^7C_3=35 \). Statement (iii) is true.
3. For \( f(i)\le f(j) \) count non-decreasing: all three distinct \( {}^7C_3=35 \), exactly two equal \( 2\cdot{}^7C_2=42 \), all equal \( {}^7C_1=7 \). Total \( 35+42+7=84 \), statement (ii) is true.

Teacher's Note:
1. A strict monotone function from a 3-element set is just a choice of 3 elements.
2. Non-decreasing functions can also be counted as \( {}^{7+3-1}C_3={}^9C_3=84 \).

Answer: (a) 5

Explanation:
1. The last digits of powers of 3 repeat in a cycle of 4: \( 3,9,7,1 \); those of powers of 7: \( 7,9,3,1 \).
2. The sum ends in 0 for the pairs of last digits \( (3,7),(9,1),(7,3),(1,9) \): \( (m\equiv1,n\equiv1),\ (m\equiv2,n\equiv0),\ (m\equiv3,n\equiv3),\ (m\equiv0,n\equiv2) \pmod 4 \).
3. Each residue class has 5 numbers in \( \{1,\dots,20\} \), so each pattern gives \( 5\times5=25 \) pairs. Total \( =4\times25=100=20\times5 \), so \( k=5 \).

Teacher's Note:
1. Only the last digit matters for divisibility by 10.
2. Use the 4-cycle of last digits for both bases.

Answer: (a) 1

Explanation:
1. Let \( A_i \) be the set of days on which friend \( i \) is present, \( |A_i|=7 \). Given: \( |A_i\cap A_j|=5,\ |A_i\cap A_j\cap A_k|=4,\ |\cap\text{ of 4}|=3,\ |\cap\text{ of 5}|=2,\ |\cap\text{ of 6}|=1 \).
2. By inclusion-exclusion, the number of dinners with at least one friend is \( {}^6C_1\cdot7-{}^6C_2\cdot5+{}^6C_3\cdot4-{}^6C_4\cdot3+{}^6C_5\cdot2-{}^6C_6\cdot1=42-75+80-45+12-1=13 \).
3. Each friend was present at 7 and absent at 7 dinners, so the total number of dinners is \( 7+7=14 \).
4. Dinners alone \( =14-13=1 \).

Teacher's Note:
1. Inclusion-exclusion counts the union of the presence sets.
2. Present plus absent days give the total number of dinners.

Answer: (a) 7

Explanation:
1. \( 1000=2^3\cdot5^3 \) and \( 2000=2^4\cdot5^3 \). Write \( a=2^{x_1}5^{y_1},\ b=2^{x_2}5^{y_2},\ c=2^{x_3}5^{y_3} \).
2. Powers of 2: \( \max(x_1,x_2)=3,\ \max(x_2,x_3)=\max(x_3,x_1)=4 \). So \( x_3=4 \) and \( \max(x_1,x_2)=3 \): \( (x_1,x_2) \) can be chosen in 7 ways.
3. Powers of 5: all three pairwise maxima equal 3. Either all three equal 3 (1 way), or two equal 3 and the third is 0, 1 or 2 (\( 3\times3=9 \) ways): 10 ways.
4. The total is \( 7\times10=70=10q \), so \( q=7 \).

Teacher's Note:
1. Treat each prime separately and multiply the counts.
2. For each prime, list the conditions on the exponents.

Answer: (a) 2

Explanation:
1. Alphabetical order of the letters: \( A,C,E,K,L,T \). Words starting with \( A \), \( C \), \( E \), \( K \), \( L \) each number \( 5!=120 \), so \( 5\times120=600 \) words come before those starting with \( T \).
2. Starting with \( TA \): next letter \( C \) is the smallest remaining, so no word before it; starting with \( TAC \): the next letter \( K \) is preceded by \( E \), giving \( TACE\_\_ \): \( 2!=2 \) words.
3. Starting with \( TACK \): remaining letters \( E,L \); \( TACKEL \) comes before \( TACKLE \): 1 word. So 3 words come before \( TACKLE \) with this prefix.
4. Rank \( =600+3+1=604 \), so \( a=6,\ b=4 \) and \( a-b=2 \).

Teacher's Note:
1. Count words that start with a smaller letter at the first position where the target word differs.
2. Rank is the number of words before it plus 1.

Answer: (a) 61

Explanation:
1. \( {}^{200}C_{100}=\frac{200!}{100!\,100!} \), so the exponent of \( p \) is \( E_p(200)-2E_p(100) \).
2. For a prime \( p \) with \( 67\le p<100 \): \( \lfloor200/p\rfloor=2 \) and \( \lfloor100/p\rfloor=1 \), so the exponent is \( 2-2=0 \).
3. For \( p=61 \): \( \lfloor200/61\rfloor=3 \) and \( \lfloor100/61\rfloor=1 \), so the exponent is \( 3-2=1>0 \). So 61 divides \( {}^{200}C_{100} \), and 61 is the largest such two-digit prime.

Teacher's Note:
1. Primes between 67 and 100 appear twice in 200! and twice in \( 100!\,100! \) combined, so they cancel.
2. The largest two-digit prime not exceeding \( 200/3 \) is 61.

Answer: (b) 5

Explanation:
1. The number of trailing zeros of \( n! \) is \( E_5(n) \) (since 5 is the scarcer factor).
2. \( E_5(n)<\frac n4 \), so \( E_5(n)=26 \) requires \( n>104 \). \( E_5(109)=21+4=25 \) and \( E_5(110)=22+4=26 \).
3. \( E_5(114)=22+4=26 \) but \( E_5(115)=23+4=27 \). So \( n=110,111,112,113,114 \): 5 values.

Teacher's Note:
1. Trailing zeros are determined by the power of 5 in the factorial.
2. The count jumps by one at each multiple of 5, so each value occurs for 5 consecutive \( n \).

Answer: (a) 720

Explanation:
1. The units digit must be odd: 4 choices (\( 1,3,5,7 \)).
2. The thousands digit cannot be 0: 5 choices. The hundreds and tens digits can each be any of the 6 digits.
3. Total \( =5\times6\times6\times4=720 \).

Teacher's Note:
1. Fill the restricted places first (units and thousands), then the free places.
2. With repetition allowed, each free place has all 6 choices.

Answer: (a) 72

Explanation:
1. Such numbers are four-digit numbers with the thousands digit 1, 2 or 3: 3 choices.
2. The remaining three places are filled from the other 4 digits in order: \( 4\times3\times2=24 \) ways.
3. Total \( =3\times24=72 \).

Teacher's Note:
1. The condition \( 1000<N<4000 \) fixes the thousands digit among 1, 2, 3.
2. Without repetition, each later place has one fewer choice.

Answer: (a) 216

Explanation:
1. A number is divisible by 3 when its digit sum is divisible by 3. The sum of all six digits is 15, so the omitted digit \( x \) must make \( 15-x \) divisible by 3: \( x=0 \) or \( x=3 \).
2. Digits \( 1,2,3,4,5 \): \( 5!=120 \) numbers. Digits \( 0,1,2,4,5 \): \( 5!-4!=96 \) numbers (excluding a leading 0).
3. Total \( =120+96=216 \).

Teacher's Note:
1. Choose which digit to leave out using the digit sum.
2. Subtract the numbers that begin with 0.

Answer: (a) 77

Explanation:
1. Seven digits each at least 1 give a minimum sum of 7, so the excess over 1 per digit totals 3.
2. The multiset of digits is either \( \{2,2,2,1,1,1,1\} \) (arrangements \( \frac{7!}{3!\,4!}=35 \)) or \( \{3,2,1,1,1,1,1\} \) (arrangements \( \frac{7!}{5!}=42 \)).
3. Total \( =35+42=77 \).

Teacher's Note:
1. List the possible multisets of digits with the required sum, then count arrangements of each.
2. The excess 3 can be split as \( 1+1+1 \) or \( 2+1 \).

Answer: (a) 11754

Explanation:
1. Count by the number of distinct digits used. One digit (all six equal): 9 numbers.
2. Two distinct digits (frequencies 4 and 2 or 3 and 3): not using 0 gives 1800; using 0 gives 225.
3. Three distinct digits each used twice: not using 0 gives 7560; using 0 gives 2160.
4. Total \( =9+225+1800+2160+7560=11754 \) (confirmed by direct enumeration of all six-digit numbers).

Teacher's Note:
1. Classify by the pattern of digit frequencies, and separately handle the digit 0 because the first digit cannot be 0.
2. A computer count over all six-digit numbers gives the same total.

Answer: (a) 25

Explanation:
1. Five different books are to be divided into 3 non-empty groups. The possible sizes are \( (3,1,1) \) and \( (2,2,1) \).
2. \( (3,1,1) \): \( {}^5C_3=10 \) ways. \( (2,2,1) \): \( \frac{{}^5C_2\cdot{}^3C_2}{2!}=15 \) ways (the two groups of 2 are indistinguishable).
3. Total \( =10+15=25 \) (this is the Stirling number \( S(5,3) \)).

Teacher's Note:
1. Bundles are unlabelled, so divide by the factorial of the number of equal-sized groups.
2. \( S(5,3)=25 \).

Answer: (a) 1800

Explanation:
1. Six periods and five subjects, each occurring at least once: exactly one subject is repeated, in two periods.
2. Choose the repeated subject (5 ways) and arrange the multiset of 6 items: \( \frac{6!}{2!}=360 \) ways.
3. Total \( =5\times360=1800 \).

Teacher's Note:
1. Exactly one subject must appear twice.
2. Arrange with repeated items using \( \frac{n!}{2!} \).

Answer: (a) 677

Explanation:
1. The number of different possible pairs of initials is \( 26\times26=676 \).
2. By the pigeonhole principle, with 676 students all pairs could be different.
3. Hence \( 676+1=677 \) students guarantee that two share the same pair.

Teacher's Note:
1. Pigeonhole principle: \( n+1 \) objects in \( n \) boxes force a shared box.
2. Count the boxes (possible initial pairs) carefully.

Answer: (a) 450

Explanation:
1. There are \( 9\times10\times10=900 \) three-digit numbers.
2. Fix the first two digits (90 ways). The last digit can be chosen so that the total sum is even in exactly 5 ways (5 even or 5 odd digits, depending on the parity of the first two digits).
3. So the count is \( 90\times5=450 \), which is half of 900.

Teacher's Note:
1. For any choice of the first two digits, exactly half of the units digits make the sum even.
2. Half of the 900 three-digit numbers.

Answer: (a) 54

Explanation:
1. \( 140=2^2\cdot5\cdot7 \).
2. The two factors of 2 can be distributed among \( x,y,z \) in \( {}^{4}C_2=6 \) ways; the factor 5 in 3 ways; the factor 7 in 3 ways.
3. Total \( =6\times3\times3=54 \).

Teacher's Note:
1. Distribute each prime power separately among the three variables.
2. \( a \) identical items in \( 3 \) boxes: \( {}^{a+2}C_2 \).

Answer: (a) 120

Explanation:
1. Introduce a slack variable \( t\ge0 \): \( x+y+z+t=10 \) with \( x,y,z\ge1 \).
2. Put \( x=x'+1 \), etc.: \( x'+y'+z'+t=7 \) with all variables non-negative.
3. The number of solutions is \( {}^{7+4-1}C_{3}={}^{10}C_3=120 \).

Teacher's Note:
1. An inequality becomes an equation with a slack variable.
2. Shift the positive variables by 1.