<p>Let <em>A</em> = {0, 5, 10, 15, ..., 195}. Let <em>B</em> be any subset of <em>A</em> with at least 15 elements. What is the probability that <em>B</em> has at least one pair of elements whose sum is divisible by 15?</p>
Step-by-Step Solution
Key Concept: Partition A into residue classes modulo 15, then apply pigeonhole principle: if B has 15+ elements from a set with only 14 residue pairs that avoid sum ≡ 0 (mod 15), at least one problematic pair must exist.
<p><strong>Step 1:</strong> Identify the structure of A. Since A = {0, 5, 10, 15, ..., 195}, every element is 5k where 0 ≤ k ≤ 39. So |A| = 40.</p><p><strong>Step 2:</strong> Work modulo 15. Two numbers sum to a multiple of 15 iff their residues mod 15 sum to 0 or 15. Partitioning by residue classes mod 15 of elements in A:</p><ul><li>Class 0: {0, 15, 30, ...} (elements ≡ 0 mod 15) → 4 elements</li><li>Class 5: {5, 20, 35, ...} (elements ≡ 5 mod 15) → 4 elements</li><li>Class 10: {10, 25, 40, ...} (elements ≡ 10 mod 15) → 4 elements</li></ul><p>Each residue class has exactly 4 elements. Problematic pairs: (0,0), (5,10).</p><p><strong>Step 3:</strong> Any two elements from class 0 sum to ≡ 0 (mod 15). Any element from class 5 paired with class 10 sums to ≡ 0 (mod 15).</p><p><strong>Step 4:</strong> To avoid such pairs, B can contain at most 1 element from class 0, and cannot contain elements from both classes 5 and 10 simultaneously. Maximum safe subset size: max(1 + 4 + 0, 1 + 0 + 4) = 5 elements.</p><p><strong>Step 5:</strong> Since |B| ≥ 15 and the maximum subset avoiding problematic pairs has ≤ 5 elements, every B with 15+ elements must contain at least one pair summing to a multiple of 15.</p><p>∴ <strong>Answer: B (Probability = 1)</strong></p>
Correct Answer: B