HMMT February, 2019

Combinatorics Difficulty 6.0 AIME, harder Prove it United States

Problem:

Let $A=\left\lceil 1 / H_{3}\right\rceil$ , $B=\left\lceil H_{5} / 2\right\rceil$ . How many ways are there to partition the set $\{1,2, \ldots, A+B\}$ into two sets $U$ and $V$ with size $A$ and $B$ respectively such that the probability that a number chosen from $U$ uniformly at random is greater than a number chosen from $V$ uniformly at random is exactly $\frac{1}{2}$ ?

Solution

Solution:

$A=4$ , $B=7$ . There are $28$ total ways of choosing an element from $U$ and $V$ , so there must be $14$ ways where $U$ 's is larger. If we relabel the elements to be $0,1, \cdots, 10$ , then element $i$ is greater than exactly $i$ elements in the set. However, we overcount other elements in $U$ , so the four elements in $U=\{a, b, c, d\}$ must satisfy
$(a-0)+(b-1)+(c-2)+(d-3)=14 \Rightarrow a+b+c+d=20$
To remove the uniqueness condition, we subtract $1$ from $b$ , $2$ from $c$ , and $3$ from $d$ , so we wish to find solutions $a \leq b \leq c \leq d \leq 7$ to $a+b+c+d=14$ . From here, we do casework. If $a=0$ , $b=0,1,2,3,4$ give $1,1,2,2,3$ solutions, respectively. If $a=1$ , $b=1,2,3,4$ give $2,2,3,1$ solutions, respectively. If $a=2$ , $b=2,3,4$ give $3,2,1$ solutions, respectively. If $a=3$ , the only solution is $3,3,4,4$ . Thus, the answer is $(1+1+2+2+3)+(2+2+3+1)+(3+2+1)+1=24$ .

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

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