1997 AHSME Problems/Problem 30
Problem
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 ?
Solution
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 odd . 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
See also
1997 AHSME (Problems • Answer Key • Resources) | ||
Preceded by Problem 29 |
Followed by Last Question | |
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 |