1997 AHSME Problems/Problem 30

Problem

For positive integers $n$ , denote $D(n)$ by the number of pairs of different adjacent digits in the binary (base two) representation of $n$ . For example, $D(3) = D(11_{2}) = 0$ , $D(21) = D(10101_{2}) = 4$ , and $D(97) = D(1100001_{2}) = 2$ . For how many positive integers less than or equal $97$ to does $D(n) = 2$ ?

$\textbf{(A)}\ 16\qquad\textbf{(B)}\ 20\qquad\textbf{(C)}\ 26\qquad\textbf{(D)}\ 30\qquad\textbf{(E)}\ 35$

Solution 1

If $D(n)$ is even, then the binary expansion of $n$ will both begin and end with a $1$ , because all positive binary numbers begin with a $1$ , and if you switch digits twice, you will have a $1$ at the end. Thus, we are only concerned with the $49$ odd numbers between $1$ and $98$ inclusive.

All of these odd numbers will have an even $D(n)$ . $D(n) = 0$ will be given by the numbers $1, 11, 111, 1111, 11111, 111111$ , which is a total of $6$ numbers.

We skip $D(n) = 2$ for now, and move to $D(n) = 4$ , which is easier to count. The smallest $D(n) = 4$ happens when $n = 10101$ . To get another number such that $D(n) = 4$ , we may extend any of the five blocks of zeros or ones by one digit. This will form $110101, 100101, 101101, 101001, 101011$ , all of which are odd numbers that have $D(n) = 4$ . To find seven digit numbers that have $D(n) = 4$ , we can again extend any block by one, so long as it remains less than $1100001$ or under. There are five cases.

1) Extending $110101$ is impossible without going over $1100001$ .

2) Extending $100101$ by putting a $1$ at the beginning will go over $1100001$ , but the other four extensions work, giving $1000101, 1001101, 1001001, 1001011$ .

3) Extending $101101$ by putting a $1$ at the beginning will go over $1100001$ , but the other four extensions give $1001101, 1011101, 1011001, 1011011$ . However, $1001101$ already appeared in #2, giving only three new numbers.

4) Extending $101001$ at the first group is impossible. The other four extensions are $1001001, 1011001, 1010001, 1010011$ , but the first two are repeats. Thus, there are only two new numbers.

5) Extending $101011$ at the first group is impossible. The other four extensions give $1001011, 1011011, 1010011, 1010111$ , but only the last number is new.

Thus, there is $1$ five digit number, $5$ six digit numbers, and $4 + 3 + 2 + 1 = 10$ seven digit numbers under $1100001$ for which $D(n) = 4$ . That gives a total of $16$ numbers.

There smallest number for which $D(n) = 6$ is $1010101$ , which is under $98$ . Further extensions, as well as cases where $D(n) > 6$ , are not possible.

Thus, we know that there are $6$ odd numbers that have $D(n) = 0$ , and $16$ odd numbers that have $D(n) = 4$ , and $1$ number that has $D(n) = 6$ . The remaining odd numbers must have $D(n) = 2$ . This means there are $49 - 6 - 16 - 1 = 26$ numbers that have $D(n) = 2$ , which is option $\boxed{C}$

Solution 2

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 $111001$ 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 $1\dots0\dots1\dots$

The total number of digits cannot exceed $7$ . If the number has 6 digits in binary or less: this is equivalent to solving $a+b+c \le 6$ , where $a, b, c$ represent how many 1s, 0s, and 1s are in the three blocks where $a, b, c$ are positive integers. Using stars and bars, we find that there are $\binom{6}{3}=20$ such binary numbers.

If the number has $7$ digits: we see that there are $5$ 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 $20+5+1=\fbox{(C) 26}$ numbers.

Solution 3 (Casework)

For $D(n)$ to be $2$ , $n$ must be in the form $1...10...01...1$ . Note that $n$ must be at least $3$ digits for $D(n)$ to be $2$

Case $1$ : $n$ has $3$ digits $n$ = $101_2$ , there is only $1$ possible value for $n$ when $n$ has $3$ digits.

Case $2$ : $n$ has $4$ digits $n = 1$ _ _ $1$ , there could be $1$ zero or $2$ zeros in between the first digit and the last digit. If there is only $1$ zero, the zero has $2$ possible places. If there are $2$ zeros, there is only $1$ possible placement. Therefore, there are $2+1=3$ possible values for $n$ when $n$ has $4$ digits.

Case $3$ : $n$ has $5$ digits $n = 1$ _ _ _ $1$ , there could be $1$ , $2$ or $3$ zeros in between the first digit and the last digit. If there is only $1$ zero, the zero has $3$ possible places. If there are $2$ zeros, there are $2$ possible placements. If there are $3$ zeros, there is only $1$ possible placement. Therefore, there are $3+2+1=6$ possible values for $n$ when $n$ has $5$ digits.

Case $4$ : $n$ has $6$ digits $n = 1$ _ _ _ _ $1$ , there could be $1$ , $2$ , $3$ or $4$ zeros in between the first digit and the last digit. If there is only $1$ zero, the zero has $4$ possible places. If there are $2$ zeros, there are $3$ possible placements. If there are $3$ zeros, there are $2$ possible placements. If there are $4$ zeros, there is only $1$ possible placement. Therefore, there are $4+3+2+1=10$ possible values for $n$ when $n$ has $6$ digits.

Case $4$ : $n$ has $7$ digits Given by the problem, $n \le 1100001_2$ . We could first count the number of $n$ that is in the form of $10$ _ _ _ _ $1$ , where the digits between the second and last digit are in the form of $0...01...1$ .

There could be $0$ , $1$ , $2$ , $3$ or $4$ zeros. Therefore, there are $5$ possible values for $n$ when $n=10$ _ _ _ _ $1$ .

There is also the case were $n = 1100001_2$ . Therefore, there are $5+1=6$ possible values for $n$ when $n$ has $7$ digits.

Therefore, the answer is $1+3+6+15+6=\boxed{\textbf{(C) } 26}$ .

~isabelchen

Sidenote from samrocksnature

Note that any binary number $n_2$ must start with $1,$ end with $1,$ and have some number of $0$ s in between in order for $D(n)=2.$ Let $n_2$ have $a$ leading $1$ s, $b$ middle $0$ s, and $c$ trailing $1$ s. Also let $n_2$ have $k$ digits.

Lemma 1: There are $\binom{k-1}{2}$ positive integers $n_2$ with $k$ digits such that $D(n)=2.$

There are $k-2$ slots to fill in with $a+b+c$ digits, where $a,c\geq 0$ and $b \geq 1.$ Let $b'=b-1$ such that $b \geq 0,$ since we must have at least $0$ in our $k-2$ slots. Thus, there are now $k-1$ slots to fill in with $a+b'+c$ digits for any nonnegative integers $a,b',c.$ By stars and bars, there are $\binom{k-1}{2}$ ways to do this.

It makes sense that $k \geq 3,$ since $101_2$ is the smallest such $n_2$ that satisfies $D(n)=2.$

Lemma 2: There are $\frac{x(x-1)(x-2)}{6}$ ways for $D(n)=2$ when $n \leq 2^{x+1}-1$ for some nonnegative integer $x.$

This inequality condition for $n$ translates to $n$ having less than or equal to $x$ digits in base $2.$ By Lemma 1, the sum we seek is $\sum_{k=3}^{x}\binom{k-1}{2}=1+3+6+ \cdots + \text{ (x-2)th triangular number}.$ By telescoping or prior knowledge of the formula, we obtain our lemma.

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

Page

Toolbox

Search