Maths Olympiad Prep

Library / /1236 of 1394

, 2023

Combinatorics Difficulty 5.8 AIME, harder Prove it United States

Problem:

A subset SS of the set {1,2,…,10}\{1,2, \ldots, 10\} is chosen randomly, with all possible subsets being equally likely. Compute the expected number of positive integers which divide the product of the elements of SS. (By convention, the product of the elements of the empty set is 11.)

Solution

Solution:

For primes p=2,3,5,7p=2,3,5,7, let the random variable XpX_{p} denote the number of factors of pp in the product of the elements of SS, plus 11. Then we wish to find E(X2X3X5X7)\mathbb{E}\left(X_{2} X_{3} X_{5} X_{7}\right).

If there were only prime powers between 11 and 1010, then all XpX_{p} would be independent. However, 66 and 1010 are non-prime powers, so we will do casework on whether these elements are included:

- Case 1: none included. Note that E(X2∣6,10∉S)=1+12(1+2+3)=4\mathbb{E}\left(X_{2} \mid 6,10 \notin S\right)=1+\frac{1}{2}(1+2+3)=4, since each of {2,4,8}\{2,4,8\} has a 1/21/2 chance of being included in SS. Similarly, E(X3∣6,10∉S)=52\mathbb{E}\left(X_{3} \mid 6,10 \notin S\right)=\frac{5}{2} and E(X5∣6,10∉S)=E(X7∣6,10∉S)=32\mathbb{E}\left(X_{5} \mid 6,10 \notin S\right)=\mathbb{E}\left(X_{7} \mid 6,10 \notin S\right)=\frac{3}{2}. The values of X2,X3,X5X_{2}, X_{3}, X_{5}, and X7X_{7} are independent given that 6,10∉S6,10 \notin S, so E(X2X3X5X7∣6,10∉S)=4⋅52⋅32⋅32=452\mathbb{E}\left(X_{2} X_{3} X_{5} X_{7} \mid 6,10 \notin S\right)=4 \cdot \frac{5}{2} \cdot \frac{3}{2} \cdot \frac{3}{2}=\frac{45}{2}.

- Case 2: 66 included. Now, we have E(X2∣6∈S,10∉S)=5\mathbb{E}\left(X_{2} \mid 6 \in S, 10 \notin S\right)=5 and E(X3∣6∈S,10∉S)=72\mathbb{E}\left(X_{3} \mid 6 \in S, 10 \notin S\right)=\frac{7}{2}, since we know 6∈S6 \in S. We still have E(X5∣6∈S,10∉S)=E(X7∣6∈S,10∉S)=32\mathbb{E}\left(X_{5} \mid 6 \in S, 10 \notin S\right)=\mathbb{E}\left(X_{7} \mid 6 \in S, 10 \notin S\right)=\frac{3}{2}. The values of X2,X3,X5X_{2}, X_{3}, X_{5}, and X7X_{7} are independent given that 6∈S6 \in S but 10∉S10 \notin S, so E(X2X3X5X7∣6∈S,10∉S)=5⋅72⋅32⋅32=3158\mathbb{E}\left(X_{2} X_{3} X_{5} X_{7} \mid 6 \in S, 10 \notin S\right)=5 \cdot \frac{7}{2} \cdot \frac{3}{2} \cdot \frac{3}{2}=\frac{315}{8}.

- Case 3: 1010 included. We have E(X2∣10∈S,6∉S)=5\mathbb{E}\left(X_{2} \mid 10 \in S, 6 \notin S\right)=5 and E(X5∣10∈S,6∉S)=52\mathbb{E}\left(X_{5} \mid 10 \in S, 6 \notin S\right)=\frac{5}{2}, since we know 10∈S10 \in S. We also have E(X3∣10∈S,6∉S)=52\mathbb{E}\left(X_{3} \mid 10 \in S, 6 \notin S\right)=\frac{5}{2} and E(X7∣10∈S,6∉S)=32\mathbb{E}\left(X_{7} \mid 10 \in S, 6 \notin S\right)=\frac{3}{2}, hence E(X2X3X5X7∣10∈S,6∉S)=5⋅52⋅52⋅32=3758\mathbb{E}\left(X_{2} X_{3} X_{5} X_{7} \mid 10 \in S, 6 \notin S\right)=5 \cdot \frac{5}{2} \cdot \frac{5}{2} \cdot \frac{3}{2}=\frac{375}{8}.

- Case 4: 66 and 1010 included. We have E(X2∣6,10∈S)=6\mathbb{E}\left(X_{2} \mid 6,10 \in S\right)=6, E(X3∣6,10∈S)=72\mathbb{E}\left(X_{3} \mid 6,10 \in S\right)=\frac{7}{2}, and E(X5∣6,10∈S)=52\mathbb{E}\left(X_{5} \mid 6,10 \in S\right)=\frac{5}{2}. We still have E(X7∣6,10∈S)=32\mathbb{E}\left(X_{7} \mid 6,10 \in S\right)=\frac{3}{2}, hence E(X2X3X5X7∣6,10∈S)=6⋅72⋅52⋅32=3154\mathbb{E}\left(X_{2} X_{3} X_{5} X_{7} \mid 6,10 \in S\right)=6 \cdot \frac{7}{2} \cdot \frac{5}{2} \cdot \frac{3}{2}=\frac{315}{4}.

The average of these quantities is 14(452+3158+3758+3154)=3758\frac{1}{4}\left(\frac{45}{2}+\frac{315}{8}+\frac{375}{8}+\frac{315}{4}\right)=\frac{375}{8}, as desired.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.