Difference between revisions of "1997 AHSME Problems/Problem 30"

(Solution 2)
(Unrelated Sidenote from samrocksnature)
(One intermediate revision by the same user not shown)
Line 35: Line 35:
  
 
If the number has <math>7</math> digits: we see that there are <math>5</math> 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 <math>20+5+1=\fbox{(C) 26}</math> numbers.
 
If the number has <math>7</math> digits: we see that there are <math>5</math> 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 <math>20+5+1=\fbox{(C) 26}</math> numbers.
 +
 +
==Sidenote from samrocksnature==
 +
Note that any binary number <math>n_2</math> must start with <math>1,</math> end with <math>1,</math> and have some number of <math>0</math>s in between in order for <math>D(n)=2.</math> Let <math>n_2</math> have <math>a</math> leading <math>1</math>s, <math>b</math> middle <math>0</math>s, and <math>c</math> trailing <math>1</math>s. Also let <math>n_2</math> have <math>k</math> digits.
 +
 +
Lemma 1: There are <math>\binom{k-1}{2}</math> positive integers <math>n_2</math> with <math>k</math> digits such that <math>D(n)=2.</math>
 +
 +
There are <math>k-2</math> slots to fill in with <math>a+b+c</math> digits, where <math>a,c\geq 0</math> and <math>b \geq 1.</math> Let <math>b'=b-1</math> such that <math>b \geq 0,</math> since we must have at least <math>0</math> in our <math>k-2</math> slots. Thus, there are now <math>k-1</math> slots to fill in with <math>a+b'+c</math> digits for any nonnegative integers <math>a,b',c.</math> By stars and bars, there are <math>\binom{k-1}{2}</math> ways to do this.
 +
 +
It makes sense that <math>k \geq 3,</math> since <math>101_2</math> is the smallest such <math>n_2</math> that satisfies <math>D(n)=2.</math>
 +
 +
Lemma 2: There are <math>\frac{x(x-1)(x-2)}{6}</math> ways for <math>D(n)=2</math> when <math>n \leq 2^{x+1}-1</math> for some nonnegative integer <math>x.</math>
 +
 +
This inequality condition for <math>n</math> translates to <math>n</math> having less than or equal to <math>x</math> digits in base <math>2.</math> By Lemma 1, the sum we seek is <math>\sum_{k=3}^{x}\binom{k-1}{2}=1+3+6+ \cdots + \text{ (x-2)th triangular number}.</math> By telescoping or prior knowledge of the formula, we obtain our lemma.
  
 
== See also ==
 
== See also ==
 
{{AHSME box|year=1997|num-b=29|after=Last Question}}
 
{{AHSME box|year=1997|num-b=29|after=Last Question}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 02:51, 3 July 2021

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.

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.

See also

1997 AHSME (ProblemsAnswer KeyResources)
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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png