Maths Olympiad Prep

Library / /158 of 1394

Combinatorics Difficulty 4.8 AIME Find the answer United States

Problem:

Let aa, bb be integers chosen independently and uniformly at random from the set {0,1,2,,80}\{0,1,2, \ldots, 80\}. Compute the expected value of the remainder when the binomial coefficient (ab)=a!b!(ab)!\binom{a}{b}=\frac{a!}{b!(a-b)!} is divided by 33. (Here (00)=1\binom{0}{0}=1 and (ab)=0\binom{a}{b}=0 whenever a<ba<b.)

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

Answer: 18166561\frac{1816}{6561}

By Lucas' Theorem we're looking at
i=14(aibi) \prod_{i=1}^{4} \binom{a_{i}}{b_{i}}
where the aia_{i} and bib_{i} are the digits of aa and bb in base 33. If any ai<bia_{i}<b_{i}, then the product is zero modulo 33.

Otherwise, the potential residues are (20)=1\binom{2}{0}=1, (21)=2\binom{2}{1}=2, (22)=1\binom{2}{2}=1, (10)=1\binom{1}{0}=1, (11)=1\binom{1}{1}=1, (00)=1\binom{0}{0}=1.

So each term in the product has a 13\frac{1}{3} chance of being zero; given that everything is nonzero, each term has a 16\frac{1}{6} chance of being 22 and a 56\frac{5}{6} chance of being 11. The probability that an even number of terms are 11 given that none are zero is then given by the roots of unity filter
(56+16(1))4+(56+16(1))42=81+16162=97162 \frac{\left(\frac{5}{6}+\frac{1}{6} \cdot(1)\right)^{4}+\left(\frac{5}{6}+\frac{1}{6} \cdot(-1)\right)^{4}}{2}=\frac{81+16}{162}=\frac{97}{162}
Thus the expected value is
(23)4(297162)=18166561 \left(\frac{2}{3}\right)^{4}\left(2-\frac{97}{162}\right)=\frac{1816}{6561}

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.