Maths Olympiad Prep

Library / /1278 of 1394

Combinatorics Difficulty 6.0 AIME, harder Prove it United States

Problem:
The Cantor set is defined as the set of real numbers xx such that 0x<10 \leq x < 1 and the digit 11 does not appear in the base-33 expansion of xx. Two numbers are uniformly and independently selected at random from the Cantor set. Compute the expected value of their absolute difference.

(Formally, one can pick a number xx uniformly at random from the Cantor set by first picking a real number yy uniformly at random from the interval [0,1)[0,1), writing it out in binary, reading its digits as if they were in base-33, and setting xx to 22 times the result.)

Solution

Solution:
Let dd be the expected value of the absolute difference. Observe that the Cantor set is made up of two smaller copies of itself, each scaled down by a factor of 33. There is a 12\frac{1}{2} chance that the two selected numbers are in the same copy, in which case the expected value of their absolute difference is 13d\frac{1}{3} d. Otherwise, we can write them as 2+x3\frac{2 + x}{3} and y3\frac{y}{3} for independently and uniformly randomly selected xx and yy in the Cantor set. Their difference is 2+(xy)3\frac{2 + (x - y)}{3}, which by symmetry has expected value 23\frac{2}{3}. Thus
d=1213d+1223d=[25]. d = \frac{1}{2}\cdot \frac{1}{3} d + \frac{1}{2}\cdot \frac{2}{3} \Rightarrow d = \left[\frac{2}{5}\right].

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.