CMI M.Sc. and Ph.D. Computer Science Chapter Practice

**Step 1: Determine the size of the sample space $|\Omega|$.** The experiment involves choosing two distinct numbers sequentially from the set $S = \{1, 2, 3, 4, 5\}$. This forms an ordered pair $(x, y)$ where $x \neq y$. The number of choices for the first number $x$ is 5. After choosing $x$, there are 4 remaining choices for the second number $y$. Thus, the total number of ordered pairs is $5 \times 4 = 20$. Therefore, the statement "The size of the sample space $|\Omega|$ is 20." is **correct**. **Step 2: Determine the size of event $E_1$.** Event $E_1$ is that the sum $x+y$ is even. For the sum of two integers to be even, both integers must be even, or both must be odd. From $S = \{1, 2, 3, 4, 5\}$: * Odd numbers: $O = \{1, 3, 5\}$ (3 numbers) * Even numbers: $V = \{2, 4\}$ (2 numbers) Case 1: Both $x$ and $y$ are odd. Since $x \neq y$, we choose 2 distinct odd numbers sequentially. The number of ways is $3 \times 2 = 6$. Case 2: Both $x$ and $y$ are even. Since $x \neq y$, we choose 2 distinct even numbers sequentially. The number of ways is $2 \times 1 = 2$. The total size of event $E_1$ is the sum of these cases: Therefore, the statement "The size of event $E_1$ is 8." is **correct**. **Step 3: Determine the size of event $E_2$.** Event $E_2$ is that the first number $x$ is greater than the second number $y$ (i.e., $x > y$). Since $x$ and $y$ are distinct, for any pair of distinct numbers chosen from $S$, say $a$ and $b$, either $a > b$ or $b > a$. The total number of ordered pairs is 20. By symmetry, exactly half of these pairs will have the first element greater than the second, and the other half will have the second element greater than the first. Alternatively, we can list them: * If $x=2, y=1$: (2,1) * If $x=3, y \in \{1,2\}$: (3,1), (3,2) * If $x=4, y \in \{1,2,3\}$: (4,1), (4,2), (4,3) * If $x=5, y \in \{1,2,3,4\}$: (5,1), (5,2), (5,3), (5,4) Summing these up: $1 + 2 + 3 + 4 = 10$. Therefore, the statement "The size of event $E_2$ is 12." is **incorrect**. **Step 4: Determine the size of event $E_3$.** Event $E_3$ is that the product $xy$ is a multiple of 3. For the product $xy$ to be a multiple of 3, at least one of $x$ or $y$ must be a multiple of 3. From $S = \{1, 2, 3, 4, 5\}$, the only number that is a multiple of 3 is 3. Let $M_3 = \{3\}$ and $S \setminus M_3 = \{1, 2, 4, 5\}$ (4 numbers). Case 1: $x$ is 3. If $x=3$, then $y$ can be any of the other 4 distinct numbers from $S$ (i.e., $y \in \{1, 2, 4, 5\}$). This gives 4 pairs: $(3,1), (3,2), (3,4), (3,5)$. Case 2: $y$ is 3. If $y=3$, then $x$ can be any of the other 4 distinct numbers from $S$ (i.e., $x \in \{1, 2, 4, 5\}$). This gives 4 pairs: $(1,3), (2,3), (4,3), (5,3)$. Since $x \neq y$, there is no overlap between these two cases (i.e., $(3,3)$ is not a possible outcome). The total size of event $E_3$ is the sum of these cases: Therefore, the statement "The size of event $E_3$ is 8." is **correct**. **Conclusion:** The correct statements are: * The size of the sample space $|\Omega|$ is 20. * The size of event $E_1$ is 8. * The size of event $E_3$ is 8.

**1. Define the Sample Space and its Size:** The sample space $\Omega$ consists of all possible binary strings of length 4. Since each of the 4 positions can be either '0' or '1' independently, the total number of possible strings is $2^4 = 16$. **2. Calculate the Size of Each Event:** * **Event $E_1$: The string contains an even number of '1's.** This means the string can have 0, 2, or 4 '1's. * Number of strings with 0 '1's: $\binom{4}{0} = 1$ (0000) * Number of strings with 2 '1's: $\binom{4}{2} = \frac{4 \times 3}{2} = 6$ (e.g., 1100, 1010, 1001, 0110, 0101, 0011) * Number of strings with 4 '1's: $\binom{4}{4} = 1$ (1111) Thus, $|E_1| = 1 + 6 + 1 = 8$. * **Event $E_2$: The string starts with '1' and ends with '0'.** The format of such a string is $1 b_2 b_3 0$. The bits $b_2$ and $b_3$ can each be '0' or '1'. There are $1 \times 2 \times 2 \times 1 = 4$ such strings. $E_2 = \{1000, 1010, 1100, 1110\}$. Thus, $|E_2| = 4$. * **Event $E_3$: The string is a palindrome.** A binary string $b_1 b_2 b_3 b_4$ is a palindrome if $b_1 = b_4$ and $b_2 = b_3$. We need to choose $b_1$ (2 options: 0 or 1) and $b_2$ (2 options: 0 or 1). The bits $b_3$ and $b_4$ are then determined. There are $2 \times 2 = 4$ palindromic strings. $E_3 = \{0000, 0110, 1001, 1111\}$. Thus, $|E_3| = 4$. * **Event $E_4$: The string contains at least three '1's.** This means the string can have 3 '1's or 4 '1's. * Number of strings with 3 '1's: $\binom{4}{3} = 4$ (e.g., 1110, 1101, 1011, 0111) * Number of strings with 4 '1's: $\binom{4}{4} = 1$ (1111) Thus, $|E_4| = 4 + 1 = 5$. $E_4 = \{1110, 1101, 1011, 0111, 1111\}$. **3. Evaluate Each Statement:** * **Statement 1: $|E_1| = 8$** From our calculation, $|E_1| = 8$. This statement is **Correct**. * **Statement 2: $E_3 \subseteq E_1$** A string in $E_3$ is a palindrome of the form $b_1 b_2 b_2 b_1$. The number of '1's in such a string is $2 \times (\text{value of } b_1) + 2 \times (\text{value of } b_2)$. This sum is always an even number (0, 2, or 4). For example, the strings in $E_3$ are: * 0000 (0 '1's - even) * 0110 (2 '1's - even) * 1001 (2 '1's - even) * 1111 (4 '1's - even) Since all strings in $E_3$ have an even number of '1's, they are all included in $E_1$. Therefore, $E_3 \subseteq E_1$. This statement is **Correct**. * **Statement 3: $|E_2 \cup E_4| = 8$** Using the Principle of Inclusion-Exclusion, $|E_2 \cup E_4| = |E_2| + |E_4| - |E_2 \cap E_4|$. We know $|E_2| = 4$ and $|E_4| = 5$. We need to find $|E_2 \cap E_4|$. $E_2 \cap E_4$ consists of strings that start with '1', end with '0', AND contain at least three '1's. Comparing $E_2 = \{1000, 1010, 1100, 1110\}$ and $E_4 = \{1110, 1101, 1011, 0111, 1111\}$, the only common string is $1110$. So, $E_2 \cap E_4 = \{1110\}$, and $|E_2 \cap E_4| = 1$. Therefore, $|E_2 \cup E_4| = 4 + 5 - 1 = 8$. This statement is **Correct**. * **Statement 4: $|E_1 \cap E_4| = 2$** $E_1 \cap E_4$ consists of strings that have an even number of '1's AND contain at least three '1's. From $E_4 = \{1110, 1101, 1011, 0111, 1111\}$, let's check which strings have an even number of '1's: * 1110 (3 '1's - odd) * 1101 (3 '1's - odd) * 1011 (3 '1's - odd) * 0111 (3 '1's - odd) * 1111 (4 '1's - even) So, $E_1 \cap E_4 = \{1111\}$. Therefore, $|E_1 \cap E_4| = 1$. This statement is **Incorrect**. The correct statements are 1, 2, and 3.

**1. Determining the Sample Space $|\Omega|$:** Since two balls are drawn sequentially without replacement from 5 distinct balls, the order of drawing matters. The number of ways to choose the first ball is 5, and the number of ways to choose the second ball from the remaining 4 is 4. Therefore, the statement "The size of the sample space, $|\Omega|$, is 20." is **CORRECT**. **2. Determining the size of Event $E_1$ (both balls of the same color):** The balls are: R1, R2, B3, B4, G5. For both balls to be of the same color, they must either both be Red or both be Blue, as there is only one Green ball. * **Both Red:** The possible ordered pairs are (R1, R2) and (R2, R1). There are $2 \times 1 = 2$ outcomes. * **Both Blue:** The possible ordered pairs are (B3, B4) and (B4, B3). There are $2 \times 1 = 2$ outcomes. * **Both Green:** Not possible, as there is only one green ball. Thus, the total number of outcomes in $E_1$ is $|E_1| = 2 + 2 = 4$. Therefore, the statement "Let $E_1$ be the event that both balls drawn are of the same color. Then $|E_1| = 4$." is **CORRECT**. **3. Determining the size of Event $E_2$ (sum of numbers is odd):** The numbers on the balls are {1, 2, 3, 4, 5}. Odd numbers: {1, 3, 5} (3 balls) Even numbers: {2, 4} (2 balls) The sum of two numbers is odd if and only if one number is odd and the other is even. * **Case 1: First ball is Odd, second ball is Even.** There are 3 choices for the first (odd) ball and 2 choices for the second (even) ball. This gives $3 \times 2 = 6$ ordered pairs. Examples: (1,2), (1,4), (3,2), (3,4), (5,2), (5,4). * **Case 2: First ball is Even, second ball is Odd.** There are 2 choices for the first (even) ball and 3 choices for the second (odd) ball. This gives $2 \times 3 = 6$ ordered pairs. Examples: (2,1), (2,3), (2,5), (4,1), (4,3), (4,5). Thus, the total number of outcomes in $E_2$ is $|E_2| = 6 + 6 = 12$. Therefore, the statement "Let $E_2$ be the event that the sum of the numbers on the two drawn balls is odd. Then $|E_2| = 10$." is **INCORRECT**. **4. Determining the size of Event $E_3$ (first ball Red, second ball Green):** * **First ball is Red:** There are 2 red balls (R1, R2). So, 2 choices for the first ball. * **Second ball is Green:** There is 1 green ball (G5). So, 1 choice for the second ball. Since the draws are sequential and without replacement, the number of outcomes in $E_3$ is $2 \times 1 = 2$. The specific outcomes are (R1, G5) and (R2, G5). Therefore, the statement "Let $E_3$ be the event that the first ball drawn is Red and the second ball drawn is Green. Then $|E_3| = 2$." is **CORRECT**.

We are given the set of digits $S = \{1, 2, 3, 4, 5\}$. A 3-digit number is formed by selecting three distinct digits from $S$ and arranging them. **1. Determine the size of the sample space $\Omega$:** The sample space $\Omega$ consists of all possible 3-digit numbers formed by selecting three distinct digits from $S$ and arranging them. This is a permutation problem. The number of ways to choose 3 distinct digits from 5 and arrange them is given by the permutation formula $P(n, k) = \frac{n!}{(n-k)!}$. Here, $n=5$ and $k=3$. Thus, the statement "The size of the sample space $\Omega$ is 60" is **true**. **2. Determine the size of event $E_1$ (number formed is even):** For a 3-digit number to be even, its last digit must be an even number from $S$. The even digits in $S$ are $\{2, 4\}$. We consider two cases: * **Case A: The last digit is 2.** The first digit can be any of the remaining 4 digits ($S \setminus \{2\}$). The second digit can be any of the remaining 3 digits. Number of such arrangements = $4 \times 3 = 12$. * **Case B: The last digit is 4.** The first digit can be any of the remaining 4 digits ($S \setminus \{4\}$). The second digit can be any of the remaining 3 digits. Number of such arrangements = $4 \times 3 = 12$. The total number of even numbers is the sum of numbers from Case A and Case B: Thus, the statement "Let $E_1$ be the event that the number formed is even. The size of $E_1$ is 36" is **false**. **3. Determine the size of event $E_2$ (number formed is greater than 300):** For a 3-digit number to be greater than 300, its first digit must be 3, 4, or 5. We consider three cases: * **Case A: The first digit is 3.** The remaining two digits must be chosen from $S \setminus \{3\} = \{1, 2, 4, 5\}$ and arranged. Number of such arrangements = $P(4,2) = 4 \times 3 = 12$. * **Case B: The first digit is 4.** The remaining two digits must be chosen from $S \setminus \{4\} = \{1, 2, 3, 5\}$ and arranged. Number of such arrangements = $P(4,2) = 4 \times 3 = 12$. * **Case C: The first digit is 5.** The remaining two digits must be chosen from $S \setminus \{5\} = \{1, 2, 3, 4\}$ and arranged. Number of such arrangements = $P(4,2) = 4 \times 3 = 12$. The total number of numbers greater than 300 is the sum of numbers from Case A, B, and C: Thus, the statement "Let $E_2$ be the event that the number formed is greater than 300. The size of $E_2$ is 36" is **true**. **4. Determine the size of event $E_3$ (digits are in strictly increasing order):** If the digits of the 3-digit number are in strictly increasing order, then once we choose a set of 3 distinct digits from $S$, there is only one way to arrange them in increasing order (e.g., if we choose $\{1, 2, 3\}$, the only number is 123). So, the size of $E_3$ is simply the number of ways to choose 3 distinct digits from the 5 available digits in $S$. This is a combination problem. Thus, the statement "Let $E_3$ be the event that the digits of the number are in strictly increasing order. The size of $E_3$ is 10" is **true**. Therefore, the correct statements are options 1, 3, and 4.

**Step 1: Determine the total number of balls and the number of balls drawn.** The box contains: * Red balls: $R = 3$ * Blue balls: $B = 2$ * Green balls: $G = 1$ Total number of balls $N = R + B + G = 3 + 2 + 1 = 6$. Number of balls drawn simultaneously: $k = 3$. **Step 2: Calculate the size of the sample space $|\Omega|$.** Since the balls are drawn simultaneously and without replacement, the order does not matter. The size of the sample space is the number of ways to choose 3 balls from 6, which is given by the combination formula $\binom{N}{k}$. Thus, the statement "The size of the sample space $|\Omega|$ is 20." is **correct**. **Step 3: Calculate the size of event $E_1$ (All three balls drawn are of different colors).** For all three balls to be of different colors, we must draw 1 red ball, 1 blue ball, and 1 green ball. * Number of ways to choose 1 red ball from 3: $\binom{3}{1} = 3$. * Number of ways to choose 1 blue ball from 2: $\binom{2}{1} = 2$. * Number of ways to choose 1 green ball from 1: $\binom{1}{1} = 1$. Thus, the statement "The size of event $E_1$ is 6." is **correct**. **Step 4: Calculate the size of event $E_2$ (Exactly two balls drawn are of the same color).** This event can occur in two mutually exclusive ways: * **Case A: Two Red balls and one ball of a different color (Blue or Green).** * Choose 2 red balls from 3: $\binom{3}{2} = 3$. * Choose 1 non-red ball from the remaining 2 blue balls or 1 green ball (total 3 non-red balls): $\binom{2}{1} + \binom{1}{1} = 2 + 1 = 3$, or simply $\binom{3}{1} = 3$. * Number of ways for Case A: $\binom{3}{2} \times \binom{3}{1} = 3 \times 3 = 9$. * **Case B: Two Blue balls and one ball of a different color (Red or Green).** * Choose 2 blue balls from 2: $\binom{2}{2} = 1$. * Choose 1 non-blue ball from the remaining 3 red balls or 1 green ball (total 4 non-blue balls): $\binom{3}{1} + \binom{1}{1} = 3 + 1 = 4$, or simply $\binom{4}{1} = 4$. * Number of ways for Case B: $\binom{2}{2} \times \binom{4}{1} = 1 \times 4 = 4$. * **Case C: Two Green balls.** This is not possible as there is only 1 green ball. Total size of event $E_2$: $|E_2| = 9 + 4 = 13$. Thus, the statement "The size of event $E_2$ is 12." is **incorrect**. **Step 5: Calculate the size of event $E_3$ (All three balls drawn are red).** * Number of ways to choose 3 red balls from 3: $\binom{3}{3} = 1$. Thus, the statement "The size of event $E_3$ is 2." is **incorrect**. **Summary of Correct Statements:** * The size of the sample space $|\Omega|$ is 20. * The size of event $E_1$ is 6.

Let $R = \{1, 2, 3\}$ be the set of red balls and $B = \{4, 5, 6\}$ be the set of blue balls. The total number of balls is $N=6$. We draw two balls sequentially without replacement. **1. Size of the sample space $\Omega$:** The sample space $\Omega$ consists of all ordered pairs of distinct balls drawn from the 6 balls. The number of ways to choose the first ball is 6, and the number of ways to choose the second ball from the remaining 5 is 5. Thus, the statement is **true**. **2. Size of event $E_1$: Both balls drawn are red.** For $E_1$, both balls must be chosen from the set of red balls $R = \{1, 2, 3\}$. There are 3 red balls. The number of ways to choose two distinct red balls sequentially is $P(3, 2)$. Thus, the statement is **true**. **3. Intersection of $E_1$ and $E_2$:** Event $E_1$ means the first ball drawn is red AND the second ball drawn is red. (e.g., $(R_1, R_2)$) Event $E_2$ means the first ball drawn is blue AND the second ball drawn is red. (e.g., $(B_4, R_1)$) Since the color of the first ball is different for $E_1$ (red) and $E_2$ (blue), there can be no common outcomes between these two events. Therefore, $E_1$ and $E_2$ are disjoint. Thus, the statement is **true**. **4. Size of event $E_3$: The sum of the numbers on the two balls is even.** Let the numbers on the two drawn balls be $x_1$ and $x_2$. The sum $x_1 + x_2$ is even if and only if both $x_1$ and $x_2$ are odd, or both $x_1$ and $x_2$ are even. Identify the odd and even numbers among the 6 balls: Odd numbers: $O = \{1, 3, 5\}$ (3 balls) Even numbers: $V = \{2, 4, 6\}$ (3 balls) Case 1: Both balls drawn are odd. We choose 2 distinct odd balls sequentially from $O$. The number of ways is $P(3, 2)$. Case 2: Both balls drawn are even. We choose 2 distinct even balls sequentially from $V$. The number of ways is $P(3, 2)$. The total number of outcomes for $E_3$ is the sum of outcomes from Case 1 and Case 2 (since these cases are mutually exclusive): Thus, the statement is **false**. Based on the analysis, the true statements are , , and .

Let the set of cards be $S = \{1, 2, 3, 4, 5\}$. Three cards are drawn sequentially without replacement. **Analysis of Statement 1:** $\Omega$ is the sample space of ordered sequences of three distinct cards drawn from $S$. The number of ways to choose 3 distinct items from 5 and arrange them in order is given by the number of permutations $P(n, k) = \frac{n!}{(n-k)!}$. Here, $n=5$ and $k=3$. Thus, the statement 'The size of $\Omega$ is $60$.' is **true**. **Analysis of Statement 2:** $\Omega'$ is the sample space of unordered sets of three distinct cards drawn from $S$. The number of ways to choose 3 distinct items from 5 without regard to order is given by the number of combinations $C(n, k) = \frac{n!}{k!(n-k)!}$. Here, $n=5$ and $k=3$. Thus, the statement 'The size of $\Omega'$ is $10$.' is **true**. **Analysis of Statement 3:** Let $A$ be the event that the sum of the numbers on the three drawn cards is even, considering $\Omega'$. We need to find the number of unordered sets of 3 cards whose sum is even. The set $S$ contains: Odd numbers: $O = \{1, 3, 5\}$ (3 numbers) Even numbers: $E = \{2, 4\}$ (2 numbers) For the sum of three numbers to be even, the parities of the chosen numbers must be either: 1. All three are even (E + E + E = E). This is not possible since there are only 2 even numbers in $S$. 2. One is even and two are odd (E + O + O = E). This is possible. Number of ways to choose 1 even number from $E$: $C(2,1) = 2$. Number of ways to choose 2 odd numbers from $O$: $C(3,2) = 3$. So, the number of sets in event $A$ is $|A| = C(2,1) \times C(3,2) = 2 \times 3 = 6$. The sets are: \{1, 3, 2\}, \{1, 3, 4\}, \{1, 5, 2\}, \{1, 5, 4\}, \{3, 5, 2\}, \{3, 5, 4\}. Thus, the statement 'Let $A$ be the event that the sum of the numbers on the three drawn cards is even, considering $\Omega'$. Then $|A| = 6$.' is **true**. **Analysis of Statement 4:** Let $B$ be the event that the cards are drawn in strictly increasing order, considering $\Omega$. This means that if the sequence of drawn cards is $(c_1, c_2, c_3)$, then $c_1 < c_2 < c_3$. For any unique set of 3 cards (e.g., \{1, 2, 3\}), there is exactly one way to arrange them in strictly increasing order (e.g., $(1, 2, 3)$). Therefore, the number of such ordered sequences is equal to the number of ways to choose 3 distinct cards from 5, which is $C(5,3)$. Thus, the statement 'Let $B$ be the event that the cards are drawn in strictly increasing order, considering $\Omega$. Then $|B| = 10$.' is **true**. All four statements are true.

First, let's formally define the sample space $\Omega$ for this experiment. An outcome consists of two parts: the number of tosses $N$ until the first Head, and the real number $X$ chosen from $[0, N]$. The possible values for $N$ are $1, 2, 3, \ldots$, so $N \in \mathbb{Z}^+$. For each $n \in \mathbb{Z}^+$, the corresponding $X$ can be any real number in the interval $[0, n]$. Thus, the sample space is: Let's evaluate each option: **The sample space $\Omega$ is discrete.** This statement is false. A discrete sample space has a finite or countably infinite number of outcomes. In this experiment, for any fixed $n$, the set of possible values for $X$ is the interval $[0, n]$, which is an uncountably infinite set. Since $\Omega$ contains uncountably many outcomes (e.g., for $n=1$, it contains all pairs $(1, x)$ where $x \in [0, 1]$), it is not discrete. Instead, it is a continuous sample space due to the continuous component $X$. **The set $A = \{ (n, x) \in \Omega : n \text{ is even and } x > 1 \}$ is an an event.** This statement is true. An event is any well-defined subset of the sample space $\Omega$. The set $A$ is clearly defined as a collection of outcomes $(n, x)$ that satisfy certain conditions ($n$ is even and $x > 1$). For $n$ to be even, $n \in \{2, 4, 6, \ldots \}$. For such $n$, $x \in [0, n]$. The condition $x > 1$ is perfectly valid for these values of $n$ (since $n \ge 2$, the interval $[0, n]$ always includes values greater than 1). For example, $(2, 1.5)$ is an outcome in $A$ because $n=2$ is even and $1.5 > 1$ and $1.5 \in [0, 2]$. Therefore, $A$ is a valid subset of $\Omega$ and thus an event. **An individual outcome of the experiment is fully described by the value of $N$.** This statement is false. An individual outcome of this experiment is a pair $(n, x)$, where $n$ is the number of tosses until the first head, and $x$ is the real number chosen from $[0, n]$. Specifying only $N$ (e.g., $N=3$) does not fully describe the outcome, as the value of $X$ (e.g., $X=0.5$ or $X=2.1$) is also part of the outcome. For example, $(3, 0.5)$ and $(3, 2.1)$ are two distinct outcomes, both having $N=3$. **The sample space $\Omega$ is an uncountably infinite set.** This statement is true. As established in the analysis of the first option, $\Omega$ contains uncountably many outcomes. More formally, we can write $\Omega$ as a countable union of uncountably infinite sets: Each set $\{n\} \times [0, n]$ for a fixed $n$ is uncountably infinite because the interval $[0, n]$ is uncountably infinite. A countable union of uncountably infinite sets is itself uncountably infinite. Therefore, $\Omega$ is an uncountably infinite set. Based on the analysis, the second and fourth statements are true.