1997 AHSME Problems/Problem 30
For positive integers , denote by the number of pairs of different adjacent digits in the binary (base two) representation of . For example, , , and . For how many positive integers less than or equal to does ?
If is even, then the binary expansion of will both begin and end with a , because all positive binary numbers begin with a , and if you switch digits twice, you will have a at the end. Thus, we are only concerned with the odd numbers between and inclusive.
All of these odd numbers will have an even . will be given by the numbers , which is a total of numbers.
We skip for now, and move to , which is easier to count. The smallest happens when . To get another number such that , we may extend any of the five blocks of zeros or ones by one digit. This will form , all of which are odd numbers that have . To find seven digit numbers that have , we can again extend any block by one, so long as it remains less than or under. There are five cases.
1) Extending is impossible without going over .
2) Extending by putting a at the beginning will go over , but the other four extensions work, giving .
3) Extending by putting a at the beginning will go over , but the other four extensions give . However, already appeared in #2, giving only three new numbers.
4) Extending at the first group is impossible. The other four extensions are , but the first two are repeats. Thus, there are only two new numbers.
5) Extending at the first group is impossible. The other four extensions give , but only the last number is new.
Thus, there is five digit number, six digit numbers, and seven digit numbers under for which . That gives a total of numbers.
There smallest number for which is , which is under . Further extensions, as well as cases where , are not possible.
Thus, we know that there are odd numbers that have , and odd numbers that have , and number that has . The remaining odd numbers must have . This means there are numbers that have , which is option
Each pair of different adjacent digits corresponds to a change from one a chain of 1s to a chain of 0s or vice versa. For example, in the number there are 2 such pairs and also 2 changes (three 1s change to two 0s, then change back to 1). Thus, in a number with 2 changes, there will be three "blocks" of consecutive digits. Since the number always starts with a 1, each valid number will have the form
The total number of digits cannot exceed . If the number has 6 digits in binary or less: this is equivalent to solving , where represent how many 1s, 0s, and 1s are in the three blocks where are positive integers. Using stars and bars, we find that there are such binary numbers.
If the number has digits: we see that there are numbers for which the second digit is 0, and only 1 valid number for which the second digit is 1 (97 is 1100001 in binary). Thus, we have a total of numbers.
|1997 AHSME (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 • 26 • 27 • 28 • 29 • 30|
|All AHSME Problems and Solutions|