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

Latest revision as of 20:01, 5 October 2023

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_2$ , there could be $1$ zero or $2$ zeros 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_2$ , there could be $1$ , $2$ or $3$ zeros 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_2$ , there could be $1$ , $2$ , $3$ or $4$ zeros 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_2$ , 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_2$ .

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+10+6=\boxed{\textbf{(C) } 26}$ .

~isabelchen

small edit ~Mathlete0001

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.

@@ 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.
+==Solution 3 (Casework)==
+For <math>D(n)</math> to be <math>2</math>, <math>n</math> must be in the form <math>1...10...01...1</math>. Note that <math>n</math> must be at least <math>3</math> digits for <math>D(n)</math> to be <math>2</math>
+Case <math>1</math>: <math>n</math> has <math>3</math> digits
+<math>n</math> = <math>101_2</math>, there is only <math>1</math> possible value for <math>n</math> when <math>n</math> has <math>3</math> digits.
+Case <math>2</math>: <math>n</math> has <math>4</math> digits
+<math>n = 1</math> _ _ <math>1_2</math>, there could be <math>1</math> zero or <math>2</math> zeros between the first digit and the last digit. If there is only <math>1</math> zero, the zero has <math>2</math> possible places. If there are <math>2</math> zeros, there is only <math>1</math> possible placement. Therefore, there are <math>2+1=3</math> possible values for <math>n</math> when <math>n</math> has <math>4</math> digits.
+Case <math>3</math>: <math>n</math> has <math>5</math> digits
+<math>n = 1</math> _ _ _ <math>1_2</math>, there could be <math>1</math>, <math>2</math> or <math>3</math> zeros between the first digit and the last digit. If there is only <math>1</math> zero, the zero has <math>3</math> possible places. If there are <math>2</math> zeros, there are <math>2</math> possible placements. If there are <math>3</math> zeros, there is only <math>1</math> possible placement. Therefore, there are <math>3+2+1=6</math> possible values for <math>n</math> when <math>n</math> has <math>5</math> digits.
+Case <math>4</math>: <math>n</math> has <math>6</math> digits
+<math>n = 1</math> _ _ _ _ <math>1_2</math>, there could be <math>1</math>, <math>2</math>, <math>3</math> or <math>4</math> zeros between the first digit and the last digit. If there is only <math>1</math> zero, the zero has <math>4</math> possible places. If there are <math>2</math> zeros, there are <math>3</math> possible placements. If there are <math>3</math> zeros, there are <math>2</math> possible placements. If there are <math>4</math> zeros, there is only <math>1</math> possible placement. Therefore, there are <math>4+3+2+1=10</math> possible values for <math>n</math> when <math>n</math> has <math>6</math> digits.
+Case <math>4</math>: <math>n</math> has <math>7</math> digits
+Given by the problem, <math>n \le 1100001_2</math>. We could first count the number of <math>n</math> that is in the form of <math>10</math> _ _ _ _ <math>1_2</math>, where the digits between the second and last digit are in the form of <math>0...01...1</math>.
+There could be <math>0</math>, <math>1</math>, <math>2</math>, <math>3</math> or <math>4</math> zeros. Therefore, there are <math>5</math> possible values for <math>n</math> when <math>n=10</math> _ _ _ _ <math>1_2</math>.
+There is also the case were <math>n = 1100001_2</math>. Therefore, there are <math>5+1=6</math> possible values for <math>n</math> when <math>n</math> has <math>7</math> digits.
+Therefore, the answer is <math>1+3+6+10+6=\boxed{\textbf{(C) } 26}</math>.
+~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen]
+small edit ~[https://artofproblemsolving.com/wiki/index.php/User:Mathlete0001 Mathlete0001]
+==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 ==
 {{AHSME box|year=1997|num-b=29|after=Last Question}}
 {{MAA Notice}}

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