Permutation and Combination: CAT Previous Year Questions

Ans: A

Explanation:
The total number of ways to place an order for a sandwich can be calculated by considering each choice independently and then multiplying the number of options for each choice.

1. **Types of Sandwiches**: There are 5 distinct types of sandwiches. So, there are 5 choices.

2. **Types of Breads**: For each sandwich type, there are 4 bread options. So, there are 4 choices.

3. **Sandwich Sizes**: For each sandwich type, there are 2 size options (small or large). So, there are 2 choices.

4. **Sauces**: A customer can add up to 2 out of 6 available sauces. This means the customer can choose:
* 0 sauces
* 1 sauce
* 2 sauces

The number of ways to choose sauces is calculated using combinations:
* Number of ways to choose 0 sauces from 6: $C(6, 0) = \frac{6!}{0!(6-0)!} = 1$
* Number of ways to choose 1 sauce from 6: $C(6, 1) = \frac{6!}{1!(6-1)!} = 6$
* Number of ways to choose 2 sauces from 6: $C(6, 2) = \frac{6!}{2!(6-2)!} = \frac{6 \times 5}{2 \times 1} = 15$

The total number of options for sauces is $1 + 6 + 15 = 22$.

To find the total number of different ways an order can be placed, we multiply the number of choices for each step:
Total ways = (Number of sandwich types) $\times$ (Number of bread types) $\times$ (Number of sizes) $\times$ (Number of sauce options)
Total ways = $5 \times 4 \times 2 \times 22$
Total ways = $20 \times 2 \times 22$
Total ways = $40 \times 22$
Total ways = $880$

Therefore, there are 880 different ways in which an order can be placed for a sandwich.

The final answer is $\boxed{880}$.

Correct_Option:A

Ans: 31

Given a set of $n$ unique digits, if the task is to determine the sum of all possible $n$-digit numbers that can be formed using these digits without repetition, the following formula can be applied:

$ \text{Sum of numbers} = (10^{n-1} + 10^{n-2} + \dots + 10^1 + 10^0) \times (n-1)! \times (\text{Sum of the given digits}) $

For a case where $n=4$, let the distinct digits be $a, b, c, d$. The formula becomes:

$ (10^3 + 10^2 + 10^1 + 10^0) \times (4-1)! \times (a+b+c+d) $
$ (1000 + 100 + 10 + 1) \times 3! \times (a+b+c+d) $
$ (1111) \times 6 \times (a+b+c+d) $
$ 6666 \times (a+b+c+d) $

The problem states that this calculated sum is equal to $153310 + n$.

$ 6666 \times (a+b+c+d) = 153310 + n $

Given that $n$ is a single-digit natural number, the total value $153310 + n$ should be an exact multiple of $6666$.

Dividing $153310$ by $6666$ yields a quotient of approximately $22.99$. The closest integer quotient is $23$.

Let’s test if $6666 \times 23$ matches $153310 + n$:

$ 6666 \times 23 = 153318 $

So, we have:

$ 153318 = 153310 + n $

Solving for $n$:

$ n = 153318 – 153310 $
$ n = 8 $

This confirms that $n=8$, which is a single-digit natural number.

From the equation $6666 \times (a+b+c+d) = 153318$, we can find the sum of the digits:

$ a+b+c+d = \frac{153318}{6666} $
$ a+b+c+d = 23 $

Finally, the sum of $a+b+c+d+n$ is:

$ 23 + 8 = 31 $

Ans: 378

We will analyze numbers with one, two, and three digits separately.

**One-digit numbers:**
There are nine such positive integers (1 through 9).

**Two-digit numbers:**
The first digit (tens place) has 9 possible choices (1 through 9). The second digit (units place) has 9 possible choices (0 through 9, excluding the digit already used in the tens place). This gives a total of $9 \times 9 = 81$ numbers.

**Three-digit numbers:**
The first digit (hundreds place) can be one of 1, 2, 3, or 4, providing 4 options. The second digit (tens place) has 9 possible choices (0 through 9, excluding the digit used in the hundreds place). The third digit (units place) has 8 possible choices (0 through 9, excluding the two digits already used in the hundreds and tens places). This results in $4 \times 9 \times 8 = 288$ numbers.

Summing these up: $9 + 81 + 288 = 378$.

Thus, 378 is the final count.

Ans: 84

Explanation:Let $x_1, x_2, x_3, x_4$ be the number of balloons received by the four children.
The total number of balloons is 20, so $x_1 + x_2 + x_3 + x_4 = 20$.
Each child gets some balloons, so $x_i \geq 1$ for $i=1, 2, 3, 4$.
No child gets an odd number of balloons. This means that each $x_i$ must be an even number.
Let $x_i = 2y_i$, where $y_i$ are positive integers (since $x_i \geq 1$ and is even, $x_i \geq 2$, so $y_i \geq 1$).
Substituting this into the equation:
$2y_1 + 2y_2 + 2y_3 + 2y_4 = 20$
Dividing by 2, we get:
$y_1 + y_2 + y_3 + y_4 = 10$
Here, $y_i$ are positive integers, so $y_i \geq 1$.
This is a stars and bars problem. We need to find the number of ways to distribute 10 identical items into 4 distinct bins, with each bin having at least one item.
The formula for the number of ways to distribute $n$ identical items into $k$ distinct bins such that each bin has at least one item is $\binom{n-1}{k-1}$.
In this case, $n=10$ and $k=4$.
So the number of ways is $\binom{10-1}{4-1} = \binom{9}{3}$.
$\binom{9}{3} = \frac{9!}{3!(9-3)!} = \frac{9!}{3!6!} = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} = 3 \times 4 \times 7 = 84$.

Final_Answer:84

Ans: A

The total count of distinct 4-digit arrangements that can be formed using the digits 1, 1, 2, and 4 is calculated as $\frac{4!}{2!} = 12$.

Considering the distribution of digits in the units place across all these 12 numbers, the frequency of the digit 1, the digit 2, and the digit 4 will be in the proportion of 2:1:1. This implies that there will be 6 instances of the digit 1, 3 instances of the digit 2, and 3 instances of the digit 4 appearing in the units position.

The sum of the digits in the units place across all possible numbers is thus $6 \times 1 + 3 \times 2 + 3 \times 4 = 24$.

This same distribution and sum will hold true for the digits in the tens, hundreds, and thousands places as well.

Therefore, the overall sum of all these 12 numbers is:
Sum = (Sum of units digits) + (Sum of tens digits) $\times 10$ + (Sum of hundreds digits) $\times 100$ + (Sum of thousands digits) $\times 1000$
Sum = $24 + 24(10) + 24(100) + 24(1000) = 24(1 + 10 + 100 + 1000) = 24(1111)$.

The average (mean) of these numbers is then calculated by dividing the total sum by the count of numbers:
Mean = $\frac{24 \times 1111}{12} = 2 \times 1111 = 2222$.

The correct option is A.

Ans: 47

The possible arrangements are structured as follows:

* **35 _**: The single remaining digit can be chosen from the 6 available options in 6 ways.
* **35 _ _**: We select 2 digits from the remaining 6 in $^6C_2=15$ ways. Subtracting the 1 instance where both 7 and 8 are chosen leaves 14 ways.
* **35 _ _ _**: We select 3 digits from the remaining 6 in $^6C_3=20$ ways. Subtracting the 4 instances where both 7 and 8 are chosen leaves 16 ways.
* **35 _ _ _ _**: We select 4 digits from the remaining 6 in $^6C_4=15$ ways. Subtracting the 6 instances where both 7 and 8 are chosen leaves 9 ways.
* **35 _ _ _ _ _**: We can select either 7 or 8, along with the other required numbers and remaining available digits, in 2 ways.

The total number of arrangements is the sum of these cases: 6 + 14 + 16 + 9 + 2 = 47.

Alternatively:

The arrangements require selecting 3 or more digits, including 3 and 5, with the constraint that 7 and 8 are never selected together. We can categorize the cases based on the inclusion of 7, 8, or neither.

**Case 1: Only 7 is selected.**
We must include digits 3, 5, and 7. For the remaining 4 positions, each digit can either be included or excluded. With 4 remaining digits, this gives $2^4 = 16$ possibilities.

**Case 2: Only 8 is selected.**
Similarly, if only 8 is selected (along with 3 and 5), there are $2^4 = 16$ possibilities for the remaining 4 positions.

**Case 3: Neither 7 nor 8 is selected.**
We must include digits 3 and 5, and exclude both 7 and 8. For the remaining 4 positions, we can choose from digits 1, 2, 4, and 6. Each of these can be included or not, yielding $2^4 = 16$ possibilities. However, we must exclude the scenario where none of these 4 digits are chosen, as this would result in a two-digit number. Therefore, there are 16 – 1 = 15 cases in this category.

The total number of possibilities is the sum of these cases: 16 + 16 + 15 = 47.

Ans: 1000

This problem is an illustration of the fundamental principle of counting, specifically the multiplication rule, combined with combinations with repetition.

The multiplication rule states that if there are $x$ ways to perform one task and $y$ ways to perform a second task, then there are $xy$ ways to perform both tasks. This principle can be extended to more than two tasks.

**Task 1: Distributing Balloons**
Each of the 3 children must receive a minimum of 4 balloons. We first fulfill this minimum requirement by giving 4 balloons to each child. This uses $4 \times 3 = 12$ balloons.
We are left with $15 – 12 = 3$ balloons to distribute among the 3 children.
The number of ways to distribute $n$ identical items to $r$ distinct recipients, where each recipient can receive any number of items (including zero), is given by the stars and bars formula: $\binom{n+r-1}{r-1}$.
In this case, $n=3$ (remaining balloons) and $r=3$ (children).
Number of ways = $\binom{3+3-1}{3-1} = \binom{5}{2} = \frac{5 \times 4}{2 \times 1} = 10$.

**Task 2: Distributing Pencils**
Each of the 3 children must receive at least one pencil. We first allocate 1 pencil to each child, using $1 \times 3 = 3$ pencils.
We are left with $6 – 3 = 3$ pencils to distribute among the 3 children.
Using the same stars and bars formula with $n=3$ (remaining pencils) and $r=3$ (children):
Number of ways = $\binom{3+3-1}{3-1} = \binom{5}{2} = \frac{5 \times 4}{2 \times 1} = 10$.

**Task 3: Distributing Erasers**
We need to distribute 3 identical erasers among the 3 children.
Using the stars and bars formula with $n=3$ (erasers) and $r=3$ (children):
Number of ways = $\binom{3+3-1}{3-1} = \binom{5}{2} = \frac{5 \times 4}{2 \times 1} = 10$.

**Total Number of Ways**
By applying the multiplication rule for these independent tasks, the total number of ways to distribute the items is the product of the number of ways for each task:
Total ways = $10 \times 10 \times 10 = 1000$.

Ans: 50

Explanation:Let the four-digit number be represented by $d_1d_2d_3d_4$. The digits used can only be 1, 2, and 3.
The condition is that both digits 2 and 3 must appear at least once.

First, let’s find the total number of four-digit numbers that can be formed using only the digits 1, 2, and 3 without any restrictions.
For each of the four positions, there are 3 choices (1, 2, or 3).
So, the total number of such four-digit numbers is $3 \times 3 \times 3 \times 3 = 3^4 = 81$.

Now, we need to subtract the numbers that do not satisfy the condition that both 2 and 3 appear at least once. This means we need to subtract the numbers where either:
1. The digit 2 does not appear at all.
2. The digit 3 does not appear at all.

Case 1: The digit 2 does not appear at all.
In this case, the four-digit number can only be formed using the digits 1 and 3.
For each of the four positions, there are 2 choices (1 or 3).
So, the number of such four-digit numbers is $2 \times 2 \times 2 \times 2 = 2^4 = 16$.

Case 2: The digit 3 does not appear at all.
In this case, the four-digit number can only be formed using the digits 1 and 2.
For each of the four positions, there are 2 choices (1 or 2).
So, the number of such four-digit numbers is $2 \times 2 \times 2 \times 2 = 2^4 = 16$.

We need to be careful not to double-count any numbers. The numbers that are subtracted in both Case 1 and Case 2 are those that use only the digit 1.
The number where only the digit 1 is used is 1111. This number is counted in Case 1 (formed by 1 and 3, excluding 2) and also in Case 2 (formed by 1 and 2, excluding 3).
So, the number of four-digit numbers formed using only the digit 1 is $1^4 = 1$.

Using the principle of inclusion-exclusion, the number of four-digit numbers where either 2 does not appear or 3 does not appear is:
(Number of numbers without 2) + (Number of numbers without 3) – (Number of numbers without 2 and without 3)
= $16 + 16 – 1$
= $32 – 1 = 31$.

These 31 numbers are the ones that do not satisfy the condition that both 2 and 3 appear at least once.

Now, subtract these from the total number of possible four-digit numbers formed using 1, 2, and 3:
Number of all such four-digit numbers = (Total number of numbers) – (Number of numbers where 2 is missing or 3 is missing)
= $81 – 31$
= $50$.

Final_Answer:50

Ans: 315

Here are the two scenarios to consider:

Scenario 1: The digit 7 is positioned at the leftmost position.
In this situation, the digit 3 has three available spots to be placed. The remaining two positions can be filled using any of the other eight digits (0, 1, 2, 4, 5, 6, 8, 9).
The total number of arrangements in this case is calculated as 3 multiplied by 8, and then multiplied by 7, resulting in 168 possibilities.

Scenario 2: The digit 7 is not at either of the extreme ends.
This scenario involves three possible positions for the digit 7. The remaining two positions can be filled in 7 by 7 ways. It’s important to recall that the digit 0 cannot be placed in the leftmost position.
Therefore, the total number of arrangements in this case is 3 multiplied by 7, and then multiplied by 7, yielding 147 possibilities.

The aggregate number of possibilities is the sum of the possibilities from both scenarios: 168 + 147 = 315.

Ans: 3920

The total number of routes from point (1, 1) to point (8, 10) that must pass through point (4, 6) is determined by multiplying the number of routes from (1,1) to (4,6) by the number of routes from (4,6) to (8,10).

To find the number of routes from (1,1) to (4,6), we need to take 4-1 = 3 steps horizontally and 6-1 = 5 steps vertically.
Therefore, the number of distinct routes from (1,1) to (4,6) is given by the combination formula: $^{(3+5)}C_3$ = 56.

To find the number of routes from (4,6) to (8,10), we need to take 8-4 = 4 steps horizontally and 10-6 = 4 steps vertically.
Therefore, the number of distinct routes from (4,6) to (8,10) is given by the combination formula: $^{(4+4)}C_4$ = 70.

The total number of routes from (1, 1) to (8, 10) via (4, 6) is the product of these two values: 56 * 70 = 3920.

Ans: 502

The condition dictates that the digits within a formed number must be in increasing sequence. This implies that for any set of chosen digits, there’s a unique way to arrange them to create a valid number.

We have a set of nine distinct digits available (1, 2, 3, 4, 5, 6, 7, 8, 9).

The count of two-digit numbers that can be formed under this rule is given by the combination formula $9C_2$.
Similarly, the count of three-digit numbers is $9C_3$.
This pattern continues up to the formation of nine-digit numbers, which can be formed in $9C_9$ ways.

A fundamental property of binomial coefficients states that the sum of combinations from $nC_0$ to $nC_n$ equals $2^n$.
Applying this to our case with $n=9$, we get:
$9C_0 + 9C_1 + 9C_2 + \dots + 9C_9 = 2^9$
$9C_0 + 9C_1 + 9C_2 + \dots + 9C_9 = 512$

The problem requires us to form numbers with at least two digits. Therefore, we must exclude the cases that would result in single-digit numbers. These correspond to $9C_0$ (representing the selection of zero digits, which doesn’t form a number) and $9C_1$ (representing the selection of one digit, which would form a single-digit number). We need to remove these terms from the total sum.

Subtracting $9C_0$ and $9C_1$ from both sides of the equation:
$9C_2 + 9C_3 + \dots + 9C_9 = 512 – 9C_0 – 9C_1$
$9C_2 + 9C_3 + \dots + 9C_9 = 512 – 1 – 9$
$9C_2 + 9C_3 + \dots + 9C_9 = 502$

Thus, the total count of such numbers is $502$.

Ans: 1098

In a competition, there are 43 participants in the junior category and 51 participants in the senior category.
Let ‘g_j’ represent the count of female participants in the junior category. The provided information states that the count of matches played exclusively between female participants in the junior category is 153.
$\Rightarrow$ g_jC2 = 153
$\Rightarrow$ g_j(g_j-1)/2 = 153
$\Rightarrow$ g_j(g_j-1) = 306
=> g_j$^{2}$-g_j-306 = 0
=> (g_j+17)(g_j-18)=0
=> g_j=18 (since the count cannot be negative)
Consequently, the count of male participants in the junior category is 43 – 18 = 25.
Let ‘b_s’ represent the count of male participants in the senior category. The provided information states that the count of matches played exclusively between male participants in the senior category is 276.
$\Rightarrow$ b_sC2 = 276
$\Rightarrow$ b_s = 24
Consequently, the count of female participants in the senior category is 51 – 24 = 27.
Therefore, the total count of matches played between male and female participants is (18 * 25) + (24 * 27) = 1098

Ans: 160

The problem provides a total of 11 distinct points. Of these, 10 points are situated on the perimeter of a circle, and 1 point is located at the circle’s center.

The total number of unique triangles that can be formed by selecting any three of these 11 points is calculated using combinations: 11C3.

11C3 = (11 * 10 * 9) / (3 * 2 * 1) = 11 * 5 * 3 = 165.

However, there are certain sets of three points that do not form valid triangles because they are collinear (lie on a straight line). These collinear sets are formed by pairs of diametrically opposite points on the circumference and the center point. Specifically, the pairs AOB, COD, EOF, GOH, and JOK each represent three points lying on a single straight line.

Since these 5 sets of three points cannot form triangles, they must be subtracted from the total possible combinations.

Therefore, the actual number of triangles that can be formed is 165 – 5 = 160.

Ans: A

We are informed that the sum of four variables, let’s call them a, b, c, and d, is equal to 7.

The total number of ways to distribute 7 identical items among 4 distinct recipients such that each recipient receives a minimum of one item can be calculated using the stars and bars method. This is given by the formula $(n-1)C(r-1)$, where n is the total number of items (7) and r is the number of recipients (4).

Applying this formula, we get:
$(7-1)C(4-1) = 6C3 = (6 * 5 * 4) / (3 * 2 * 1) = 20$

Next, we need to account for scenarios where any single recipient might receive more than 3 items. Given that each recipient must receive at least one item, the maximum number of items any one recipient can have is 4 (since 7 – 1 – 1 – 1 = 4). There are 4 distinct recipients, so there are 4 such cases where one recipient could potentially receive 4 items.

We subtract these unfavorable cases from the total number of distributions to find the valid arrangements.

Therefore, the final answer is the total number of distributions minus the cases where one recipient gets more than 3 items:
$20 – 4 = 16$

Ans: 6

Explanation:This is a classic stars and bars problem with constraints.
Let $x_A$, $x_B$, and $x_K$ be the number of pens distributed to Amal, Bimal, and Kamal, respectively.
We are given that the pens are identical, so we are looking for the number of non-negative integer solutions to the equation:
$x_A + x_B + x_K = 8$

However, we have the following constraints:
Amal gets at least 1 pen: $x_A \ge 1$
Bimal gets at least 2 pens: $x_B \ge 2$
Kamal gets at least 3 pens: $x_K \ge 3$

To handle these constraints, we can introduce new variables. Let:
$y_A = x_A – 1$ => $x_A = y_A + 1$, where $y_A \ge 0$
$y_B = x_B – 2$ => $x_B = y_B + 2$, where $y_B \ge 0$
$y_K = x_K – 3$ => $x_K = y_K + 3$, where $y_K \ge 0$

Substitute these into the original equation:
$(y_A + 1) + (y_B + 2) + (y_K + 3) = 8$
$y_A + y_B + y_K + 6 = 8$
$y_A + y_B + y_K = 8 – 6$
$y_A + y_B + y_K = 2$

Now, we need to find the number of non-negative integer solutions to this new equation. This is a standard stars and bars problem. We have 2 “stars” (the pens to distribute after satisfying the minimum requirements) and 2 “bars” to separate them into 3 categories (for $y_A$, $y_B$, and $y_K$).

The formula for stars and bars is C(n + k – 1, k – 1) or C(n + k – 1, n), where n is the number of stars and k is the number of bins (variables).
In our case, n = 2 (the sum) and k = 3 (the number of variables $y_A, y_B, y_K$).

So, the number of ways is:
C(2 + 3 – 1, 3 – 1) = C(4, 2)
Or
C(2 + 3 – 1, 2) = C(4, 2)

Calculating the combination:
C(4, 2) = 4! / (2! * (4-2)!) = 4! / (2! * 2!) = (4 * 3 * 2 * 1) / ((2 * 1) * (2 * 1)) = (4 * 3) / (2 * 1) = 12 / 2 = 6.

The possible distributions for $(y_A, y_B, y_K)$ are:
(2, 0, 0) => $(x_A, x_B, x_K) = (3, 2, 3)$
(0, 2, 0) => $(x_A, x_B, x_K) = (1, 4, 3)$
(0, 0, 2) => $(x_A, x_B, x_K) = (1, 2, 5)$
(1, 1, 0) => $(x_A, x_B, x_K) = (2, 3, 3)$
(1, 0, 1) => $(x_A, x_B, x_K) = (2, 2, 4)$
(0, 1, 1) => $(x_A, x_B, x_K) = (1, 3, 4)$

All these distributions satisfy the original conditions.

Final_Answer:6

Ans: 50

To ensure a number is divisible by 6, two conditions must be met: the sum of its digits must be divisible by 3, and its last digit must be an even number. We will examine different sets of digits to form such numbers.

**Scenario 1: Digits are 2, 3, 4, 6**
In this case, the units digit can be any of the three even digits: 2, 4, or 6. Once the units digit is chosen, the remaining three digits can be arranged in the other three positions in $3!$ (3 factorial) ways, which equals 6.
Therefore, the total number of arrangements for this set is $3 \times 6 = 18$.

**Scenario 2: Digits are 0, 2, 3, 4**
We need to consider two sub-cases here, depending on whether 0 is the units digit.

* **Sub-case 2a: 0 is the units digit.**
If 0 is in the units place, the remaining three non-zero digits (2, 3, 4) can be arranged in the first three positions in $3! = 6$ ways.

* **Sub-case 2b: 0 is not the units digit.**
The units digit can be chosen in 2 ways (either 2 or 4, as it must be even and not 0).
For the thousands place, we have 3 remaining digits, but since 0 cannot be the leading digit, we have 2 choices for the thousands place (the two digits not used for the units place and not 0).
The remaining two digits can then be arranged in the remaining two places in $2! = 2$ ways.
Thus, the total number of ways for this sub-case is $2 \times 2 \times 2 = 8$.
The total number of arrangements for Scenario 2 is the sum of these sub-cases: $6 + 8 = 14$.

**Scenario 3: Digits are 0, 2, 4, 6**
Similar to Scenario 2, we consider two sub-cases.

* **Sub-case 3a: 0 is the units digit.**
If 0 is in the units place, the remaining three non-zero even digits (2, 4, 6) can be arranged in the first three positions in $3! = 6$ ways.

* **Sub-case 3b: 0 is not the units digit.**
The units digit can be chosen in 3 ways (2, 4, or 6).
For the thousands place, we have 3 remaining digits, but 0 cannot be the leading digit, so we have 2 choices for the thousands place (the two digits not used for the units place and not 0).
The remaining two digits can then be arranged in the remaining two places in $2! = 2$ ways.
Thus, the total number of ways for this sub-case is $3 \times 2 \times 2 = 12$.
The total number of arrangements for Scenario 3 is the sum of these sub-cases: $6 + 12 = 18$.

**Total Number of Ways**
The total number of ways to form a number divisible by 6 using the given digits is the sum of the ways from each scenario: $18 (\text{from Scenario 1}) + 14 (\text{from Scenario 2}) + 18 (\text{from Scenario 3}) = 50$.