GATE CS Chapter Practice

**Step 1: Formulate the generating function.** Let $c_1, c_2, c_3$ be the number of candies received by Child 1, Child 2, and Child 3, respectively. We are looking for the number of integer solutions to $c_1 + c_2 + c_3 = n$ subject to the given conditions. The generating function for the number of candies for Child 1 (even number) is: The generating function for the number of candies for Child 2 (at least one) is: The generating function for the number of candies for Child 3 (at most two) is: The combined generating function $G(x)$ for $a_n$ is the product of these individual generating functions: **Step 2: Simplify the generating function.** We can rewrite $1-x^2$ as $(1-x)(1+x)$. We need to find $a_5$, which is the coefficient of $x^5$ in $G(x)$, i.e., $[x^5]G(x)$. Let $F(x) = \frac{1+x+x^2}{(1-x)^2(1+x)}$. We will use partial fraction decomposition for $F(x)$. **Step 3: Perform partial fraction decomposition.** Let Multiplying by $(1-x)^2(1+x)$, we get: To find $B$, set $x=1$: To find $C$, set $x=-1$: To find $A$, equate coefficients of $x^2$: So, **Step 4: Extract the coefficient of $x^4$.** We use the following standard series expansions: (using generalized binomial theorem $\binom{n+k-1}{k-1}$ with $k=2$) Now, we find $[x^4]F(x)$: Thus, $a_5 = 7$. Answer: $\boxed{7}$

**Step 1: Formulate the characteristic equation.** The given linear homogeneous recurrence relation with constant coefficients is To find the characteristic equation, we assume a solution of the form $a_n = r^n$. Substituting this into the recurrence relation yields: Dividing by $r^{n-3}$ (since $r \neq 0$), we get: Rearranging, the characteristic equation is: **Step 2: Find the roots of the characteristic equation.** We can test for integer roots by checking divisors of the constant term (4), i.e., $\pm 1$, $\pm 2$, $\pm 4$. For $r=1$: So, $r=1$ is a root. This implies $(r-1)$ is a factor of the characteristic polynomial. We can perform polynomial division or synthetic division to find the remaining factors. Using synthetic division with $r=1$: ```text 1 | 1 -5 8 -4 | 1 -4 4 ---------------- 1 -4 4 0 ``` The resulting quadratic equation is This quadratic equation is a perfect square: So, the roots of the characteristic equation are $r_1=1$ (with multiplicity 1) and $r_2=2$ (with multiplicity 2). **Step 3: Write the general solution.** For a distinct root $r_1$, the term in the general solution is $\alpha_1 r_1^n$. For a root $r_2$ with multiplicity $m$, the term is $(\alpha_2 + \alpha_3 n + \dots + \alpha_m n^{m-1}) r_2^n$. In this case, with $r_1=1$ (multiplicity 1) and $r_2=2$ (multiplicity 2), the general solution is: **Step 4: Use the initial conditions to determine the constants $\alpha_1, \alpha_2, \alpha_3$.** Given $a_0 = 1$, $a_1 = 3$, $a_2 = 9$. For $n=0$: For $n=1$: For $n=2$: From Equation 1, $\alpha_1 = 1 - \alpha_2$. Substitute $\alpha_1$ into Equation 2: Substitute $\alpha_1$ into Equation 3: Now solve the system of equations (Equation 4 and Equation 5) for $\alpha_2$ and $\alpha_3$. From Equation 4, $\alpha_2 = 2 - 2\alpha_3$. Substitute this into Equation 5: Substitute $\alpha_3 = 1$ back into $\alpha_2 = 2 - 2\alpha_3$: Substitute $\alpha_2 = 0$ back into $\alpha_1 = 1 - \alpha_2$: So the constants are $\alpha_1 = 1$, $\alpha_2 = 0$, and $\alpha_3 = 1$. **Step 5: Write the closed-form solution and calculate $a_5$.** Substitute the constants back into the general solution: Now, calculate $a_5$ by setting $n=5$: The final answer is $\boxed{161}$.

**Step 1: Formulate the characteristic equation.** The given recurrence relation is $a_n = 4a_{n-1} - 4a_{n-2}$. Rearranging the terms, we get $a_n - 4a_{n-1} + 4a_{n-2} = 0$. Assuming a solution of the form $a_n = r^n$, the characteristic equation is: **Step 2: Find the roots of the characteristic equation.** The characteristic equation can be factored as $(r-2)^2 = 0$. This equation has a single root $r=2$ with multiplicity 2. **Step 3: Write the general solution.** For a linear homogeneous recurrence relation with constant coefficients and a repeated root $r$ of multiplicity 2, the general solution takes the form: Substituting $r=2$ into this form: **Step 4: Use initial conditions to find the constants $\alpha_1$ and $\alpha_2$.** Using the initial condition $a_0 = 1$: Using the initial condition $a_1 = 6$: Substitute the value of $\alpha_1 = 1$ into this equation: Thus, the closed-form solution for the recurrence relation is: **Step 5: Calculate $a_4$.** Substitute $n=4$ into the closed-form solution: **Answer:** \boxed{144}

**Step 1: Determine the number of available characters for each type.** There are 5 distinct uppercase English letters available: $\{A, B, C, D, E\}$. There are 10 distinct digits available: $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$. **Step 2: Choose the 3 distinct uppercase English letters.** From the 5 available letters, we need to choose 3. Since the order of selection does not matter at this stage (we will arrange them later), we use combinations: **Step 3: Choose the 4 distinct digits.** From the 10 available digits, we need to choose 4. Similar to the letters, the order of selection does not matter here: **Step 4: Arrange the chosen characters.** After choosing 3 distinct letters and 4 distinct digits, we have a total of $3 + 4 = 7$ distinct characters. These $7$ distinct characters must be arranged to form a password of length $7$. The number of ways to arrange $7$ distinct items is given by $7!$ (7 factorial): **Step 5: Calculate the total number of distinct passwords.** By the Rule of Product, the total number of distinct passwords is the product of the number of ways to perform each independent step: Answer: \boxed{10,584,000}

**Step 1: Choose the 3 distinct uppercase letters.** We need to select 3 distinct uppercase letters from the 26 available uppercase English letters. The number of ways to do this is given by the combination formula: **Step 2: Choose the 3 distinct digits.** We need to select 3 distinct digits from the 10 available digits (0-9). The number of ways to do this is: **Step 3: Arrange the chosen 3 letters and 3 digits such that no two letters are adjacent.** Let the 3 chosen distinct letters be $L_1, L_2, L_3$ and the 3 chosen distinct digits be $D_1, D_2, D_3$. To ensure no two letters are adjacent, we first arrange the digits and then place the letters in the spaces created by the digits. First, arrange the 3 distinct digits. The number of ways to arrange 3 distinct items is $3!$: When the 3 digits are arranged, they create 4 possible slots where the letters can be placed (before the first digit, between any two digits, and after the last digit). For example, if the digits are arranged as $D_1 D_2 D_3$, the slots are represented by underscores: We need to place the 3 distinct letters into these 4 slots such that each slot gets at most one letter. This is equivalent to choosing 3 of the 4 available slots and then arranging the 3 distinct letters in those chosen slots. The number of ways to do this is given by the permutation formula $P(n, k)$: Therefore, the total number of ways to arrange the 6 chosen characters (3 letters and 3 digits) such that no two letters are adjacent is the product of the ways to arrange the digits and the ways to place the letters: **Step 4: Calculate the total number of distinct passwords.** Multiply the results from Step 1, Step 2, and Step 3: Thus, there are 44,928,000 such distinct passwords that can be formed. Answer: $\boxed{44,928,000}$

**Step 1: Find the characteristic equation and its roots.** The given recurrence relation is: Assuming a solution of the form: we substitute it into the recurrence relation: Dividing by $r^{n-2}$ (since $r \neq 0$), we get the characteristic equation: Factoring the quadratic equation: This equation has a single repeated root $r_1 = r_2 = 2$. **Step 2: Determine the general solution.** For a linear homogeneous recurrence relation with constant coefficients and a repeated root $r$ of multiplicity $k$, the general solution is of the form: In this case, the root $r=2$ has a multiplicity of 2. So, the general solution is: **Step 3: Use initial conditions to find constants $\alpha_1$ and $\alpha_2$.** Given initial conditions: $a_0 = 1$ and $a_1 = 6$. For $n=0$: Since $a_0 = 1$, we have $\alpha_1 = 1$. For $n=1$: Since $a_1 = 6$, we have: Substitute $\alpha_1 = 1$: **Step 4: Write the closed-form solution and evaluate options.** The closed-form solution is: * **Option 1: The characteristic equation of the recurrence relation has two distinct real roots.** The characteristic equation is $(r-2)^2 = 0$, which has a single repeated root $r=2$. Thus, this statement is **false**. * **Option 2: The closed-form solution for $a_n$ is $a_n = (1+2n)2^n$.** As derived in Step 3, this statement is **true**. * **Option 3: The value of $a_3$ is $56$.** Using the closed-form solution $a_n = (1+2n)2^n$, for $n=3$: This statement is **true**. * **Option 4: The asymptotic complexity of $a_n$ is $\Theta(n 2^n)$.** The closed-form solution is: As $n \to \infty$, the term $n2^{n+1}$ dominates $2^n$. Therefore, $a_n$ grows proportionally to $n2^n$. More formally, $a_n = (1+2n)2^n$. For $n \ge 1$: So, $c_1 n 2^n \le a_n \le c_2 n 2^n$ for appropriate constants $c_1 = 1/2$ (for $n \ge 1$, $1+2n \ge n$) and $c_2 = 4$. Thus: This statement is **true**. The correct statements are Option 2, Option 3, and Option 4. Answer: \boxed{\text{The closed-form solution for } $a_n$ \text{ is } $a_n = (1+2n)2^n$, \text{ The value of } $a_3$ \text{ is } $56$, \text{ The asymptotic complexity of } $a_n$ \text{ is } $\Theta(n 2^n)$}

The solution involves applying the fundamental counting principles combined with a number theory property. **Step 1: Identify the condition for divisibility.** A number is divisible by $4$ if and only if the number formed by its last two digits is divisible by $4$. **Step 2: Find all possible valid endings for the 4-digit number.** We need to find pairs of distinct digits from the set $S = \{1, 2, 3, 4, 5\}$ that form a two-digit number divisible by $4$. Let the $4$-digit number be $d_1 d_2 d_3 d_4$. We are looking for the possible values of the number $10d_3 + d_4$. The valid pairs for the last two digits $(d_3, d_4)$ are: - $12$ (since $12 \div 4 = 3$) - $24$ (since $24 \div 4 = 6$) - $32$ (since $32 \div 4 = 8$) - $52$ (since $52 \div 4 = 13$) There are $4$ possible cases for the ending of the number. These cases are mutually exclusive. **Step 3: Calculate the number of ways to form the first two digits for each case.** For any chosen pair of last two digits, two distinct digits from $S$ are used. Since there are $5$ digits in total, $5 - 2 = 3$ digits remain available for the first two positions ($d_1, d_2$). - The first digit ($d_1$) can be chosen in any of the $3$ remaining ways. - After choosing $d_1$, the second digit ($d_2$) can be chosen in any of the $2$ remaining ways. By the Rule of Product, the number of ways to fill the first two positions is $3 \times 2 = 6$. This is constant for each of the $4$ valid endings. **Step 4: Calculate the total count using the Rule of Sum.** We sum the possibilities for each mutually exclusive case. Since the number of ways to form the first part of the number is the same ($6$) for each of the $4$ valid endings, we can multiply. Total number of such integers = (Number of valid endings) $\times$ (Number of ways to form the first two digits for each ending) Thus, there are $24$ such numbers. Answer: $\boxed{24}$

**Step 1: Treat the Mathematics books as a single block.** Since the 3 distinct Mathematics books ($M_1$, $M_2$, $M_3$) must be kept together, we consider them as one unit, let's call it $M_{block}$. The number of ways to arrange the books within this $M_{block}$ is: **Step 2: Calculate total arrangements where Mathematics books are together, without considering the Physics books constraint.** Now, we are arranging the following 5 distinct entities: 1. The $M_{block}$ 2. Physics book $P_1$ 3. Physics book $P_2$ 4. Chemistry book $C_1$ 5. Chemistry book $C_2$ These 5 distinct entities can be arranged in $5!$ ways. Considering the internal arrangements of the Mathematics books, the total arrangements where all Mathematics books are together (and no other constraint) is: **Step 3: Calculate arrangements where Mathematics books are together AND Physics books are also together.** If the two distinct Physics books ($P_1$, $P_2$) must also be together, we treat them as a single unit, $P_{block}$. The number of ways to arrange the books within this $P_{block}$ is: Now, we are arranging the following 4 distinct entities: 1. The $M_{block}$ 2. The $P_{block}$ 3. Chemistry book $C_1$ 4. Chemistry book $C_2$ These 4 distinct entities can be arranged in $4!$ ways. Combining this with the internal arrangements of the Mathematics books and Physics books, the total arrangements where Mathematics books are together AND Physics books are together is: **Step 4: Apply the complement principle to find arrangements where Mathematics books are together, but Physics books are NOT together.** The number of arrangements where Mathematics books are together, but Physics books are not together, is the total arrangements where Mathematics books are together (from Step 2) minus the arrangements where both Mathematics and Physics books are together (from Step 3). Answer: $\boxed{432}$