Problem:
Let S be the set of integers between 1 and 240 whose binary expansions have exactly two 1's. If a number is chosen at random from S, the probability that it is divisible by 9 is p/q, where p and q are relatively prime positive integers. Find p+q.
Solution:
An element of S has the form 2a+2b, where 0≤a≤39,0≤b≤39, and aî€ =b, so S has (240​)=780 elements. Without loss of generality, assume a<b. Note that 9 divides 2a+2b=2a(2b−a+1) if and only if 9 divides 2b−a+1, that is, when 2b−a≡8(mod9). Because 21,22,23,24,25,26, and 27≡2,4,8,7,5,1, and 2 (mod9), respectively, conclude that 2b−a≡8(mod9) when b−a=6k−3 for positive integers k. But b−a=6k−3 implies that 0≤a≤39−(6k−3), so there are 40−(6k−3)=43−6k ordered pairs (a,b) that satisfy b−a=6k−3. Because 6k−3≤39, conclude that 1≤k≤7. The number of multiples of 9 in S is therefore ∑k=1​(43−6k)=7â‹…43−6â‹…7â‹…8/2=7(43−24)=133. Thus the probability that an element of S is divisible by 9 is 133/780, so p+q=913​.
OR
There are (240​)=780 such numbers, which can be viewed as strings of length 40 containing 38 0's and two 1's. Express these strings in base-8 by partitioning them into 13 groups of 3 starting from the right and one group of 1, and then expressing each 3-digit binary group as a digit between 0 and 7. Because 9= 118​, a divisibility test similar to the one for 11 in base 10 can be used. Let (ad​ad−1​…a0​)b​ represent a (d+1)-digit number in base b. Then
(ad​ad−1​…a0​)b​=k=0∑d​ak​bk≡k=0∑d​ak​(−1)k(modb+1)​
Thus a base- 8 number is divisible by 9 if and only if the sum of the digits in the even-numbered positions differs from the sum of the digits in the odd-numbered positions by a multiple of 9. Because the given base-8 string has at most two nonzero digits, and its greatest digit is at most 1102​ or 6, the two sums must differ by 0. There are two cases. If the first (leftmost) digit in the base-2 string is 1, then the other 1 must be in an odd-numbered group of 3 that has the form 001. There are seven such numbers. In the second case, if the first digit in the base-2 string is 0, one of the 1's must be in an even-numbered group of 3 , the other must be in an odd-numbered group, and they must be in the same relative position within each group, that is, both 100 , both 010 , or both 001. There are 7⋅6⋅3=126 such numbers. Thus the required probability is (7+126)/780=133/780.
The problems on this page are the property of the MAA's American Mathematics Competitions