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.
Sidenote from samrocksnature
Note that any binary number must start with end with and have some number of s in between in order for Let have leading s, middle s, and trailing s. Also let have digits.
Lemma 1: There are positive integers with digits such that
There are slots to fill in with digits, where and Let such that since we must have at least in our slots. Thus, there are now slots to fill in with digits for any nonnegative integers By stars and bars, there are ways to do this.
It makes sense that since is the smallest such that satisfies
Lemma 2: There are ways for when for some nonnegative integer
This inequality condition for translates to having less than or equal to digits in base By Lemma 1, the sum we seek is By telescoping or prior knowledge of the formula, we obtain our lemma.
|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|
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.