Question 7 of 12

Question 7

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. (a) $S=\{1,\dots,200\}$, 101 integers selected. (b) 8 distinguishable fair dice.

Find. (a) A pigeonhole proof that some pair in the selection is coprime. (b) $P(\text{all six face values appear among the 8 rolls})$.

Approach. Partition $S$ into 100 pigeonholes of consecutive-integer pairs and apply the pigeonhole principle for (a); use inclusion–exclusion (surjection counting) for (b).

1. a) Partition $S$ into consecutive pairs. Group $\{1,\dots,200\}$ into the 100 pairs $\{1,2\},\{3,4\},\{5,6\},\dots,\{199,200\}$ — i.e. $\{2k-1,2k\}$ for $k=1,\dots,100$. These 100 sets partition $S$ (every element in exactly one pair).
2. a) Apply the pigeonhole principle. Selecting 101 integers from $S$ means placing 101 "pigeons" into these 100 "holes" (each selected integer belongs to exactly one pair). Since $101>100$, by the pigeonhole principle at least one pair $\{2k-1,2k\}$ has BOTH of its elements selected.
3. a) Consecutive integers are coprime. For consecutive integers $m=2k-1,\ n=2k$: any common divisor $d$ of $m,n$ must divide $n-m=1$, so $d=1$, i.e. $\gcd(m,n)=1$. $\boxed{\text{Some selected pair } m,n \text{ has } \gcd(m,n)=1}$, proven.
4. b) Count surjections from 8 dice to 6 faces. "All six numbers appear" among 8 rolls means the function (roll $\to$ face shown) is surjective onto $\{1,\dots,6\}$. By inclusion–exclusion, the number of surjective functions from an 8-set to a 6-set is $$\sum_{i=0}^{6}(-1)^i\binom{6}{i}(6-i)^8 = 191{,}520$$
5. b) Divide by the total outcome count. Total equally-likely outcomes for 8 distinct dice: $6^8=1{,}679{,}616$. $$P=\frac{191{,}520}{1{,}679{,}616}=\frac{665}{5832}$$ $\boxed{P=665/5832\approx0.1140}$