Maths Olympiad Prep

Library / /1285 of 1394

, 2019

Combinatorics Difficulty 6.0 AIME, harder Prove it United States

Problem:

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

Solution

Solution:

A=4A=4, B=7B=7. There are 2828 total ways of choosing an element from UU and VV, so there must be 1414 ways where UU's is larger. If we relabel the elements to be 0,1,,100,1, \cdots, 10, then element ii is greater than exactly ii elements in the set. However, we overcount other elements in UU, so the four elements in U={a,b,c,d}U=\{a, b, c, d\} must satisfy
(a0)+(b1)+(c2)+(d3)=14a+b+c+d=20 (a-0)+(b-1)+(c-2)+(d-3)=14 \Rightarrow a+b+c+d=20
To remove the uniqueness condition, we subtract 11 from bb, 22 from cc, and 33 from dd, so we wish to find solutions abcd7a \leq b \leq c \leq d \leq 7 to a+b+c+d=14a+b+c+d=14. From here, we do casework. If a=0a=0, b=0,1,2,3,4b=0,1,2,3,4 give 1,1,2,2,31,1,2,2,3 solutions, respectively. If a=1a=1, b=1,2,3,4b=1,2,3,4 give 2,2,3,12,2,3,1 solutions, respectively. If a=2a=2, b=2,3,4b=2,3,4 give 3,2,13,2,1 solutions, respectively. If a=3a=3, the only solution is 3,3,4,43,3,4,4. Thus, the answer is (1+1+2+2+3)+(2+2+3+1)+(3+2+1)+1=24(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,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.