Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Solution 2)
(→‎Solution 3 (Casework))
 
(8 intermediate revisions by 4 users not shown)
Line 34: Line 34:
 
The total number of digits cannot exceed <math>7</math>. If the number has 6 digits in binary or less: this is equivalent to solving <math>a+b+c \le 6</math>, where <math>a, b, c</math> represent how many 1s, 0s, and 1s are in the three blocks where <math>a, b, c</math> are positive integers. Using stars and bars, we find that there are <math>\binom{6}{3}=20</math> such binary numbers.
 
The total number of digits cannot exceed <math>7</math>. If the number has 6 digits in binary or less: this is equivalent to solving <math>a+b+c \le 6</math>, where <math>a, b, c</math> represent how many 1s, 0s, and 1s are in the three blocks where <math>a, b, c</math> are positive integers. Using stars and bars, we find that there are <math>\binom{6}{3}=20</math> such binary 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=26</math> valid numbers. <math>\fboxed{(C)}</math>
+
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 ==
 
== 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}}

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.

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

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1997_AHSME_Problems/Problem_30&oldid=199185"