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