Question 6 of 12

Question 6

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. 26 letters (5 vowels, 21 consonants) arranged in one sequence; the multiset $\{A,A,A,B,B,B\}$ arranged at random; a 26-element domain mapped to the 2-element codomain $\{0,1\}$.

Find. (a) a pigeonhole proof of a forced run of 4 consonants; (b) $P(\text{sequence}=AAABBB)$; (c) the number of functions $\{26 \text{ letters}\}\to\{0,1\}$.

Approach. (a) is a pigeonhole argument on the "gaps" created by the 5 vowels; (b) is classical probability over the multiset permutations; (c) is direct application of the counting-functions rule $|B|^{|A|}$.

1. 6a) Pigeonhole proof. The 5 vowels split the 26-letter sequence into at most $5+1=6$ maximal runs of consonants (before the first vowel, between consecutive vowels, and after the last vowel — some runs may be empty). If every run had at most 3 consonants, the total number of consonants placed would be at most $$6\times3=18$$ but there are 21 consonants to place, and $21>18$. By the pigeonhole principle this is a contradiction, so at least one of the 6 runs must contain $\geq4$ consecutive consonants. $\boxed{\text{some run has} \geq 4 \text{ consecutive consonants (pigeonhole: } 21>6\times3)}$
2. 6b) Probability of exactly AAABBB. The number of distinguishable arrangements of $\{A,A,A,B,B,B\}$ is $\binom{6}{3}=20$ (choose which 3 of the 6 positions hold the A's); exactly one of these 20 equally-likely arrangements is the sequence AAABBB itself: $$P(\text{AAABBB})=\frac{1}{\binom{6}{3}}=\frac{1}{20}$$ $\boxed{P=\dfrac{1}{20}=0.05}$
3. 6c) Functions from the alphabet to {0,1}. A function assigns one of 2 codomain values to each of the 26 independent domain elements, so by the product rule there are $$2^{26}=67{,}108{,}864$$ distinct functions. $\boxed{2^{26}=67{,}108{,}864}$