CombinatoricsDifficulty 6.0AIME, harderProve itUnited States
Problem: The Cantor set is defined as the set of real numbers x such that 0≤x<1 and the digit 1 does not appear in the base-3 expansion of x. 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 x uniformly at random from the Cantor set by first picking a real number y uniformly at random from the interval [0,1), writing it out in binary, reading its digits as if they were in base-3, and setting x to 2 times the result.)
Solution
Solution: Let d 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 3. There is a 21 chance that the two selected numbers are in the same copy, in which case the expected value of their absolute difference is 31d. Otherwise, we can write them as 32+x and 3y for independently and uniformly randomly selected x and y in the Cantor set. Their difference is 32+(x−y), which by symmetry has expected value 32. Thus d=21⋅31d+21⋅32⇒d=[52].
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.