Difference between revisions of "1997 AHSME Problems/Problem 30"
Talkinaway (talk | contribs) |
Mathlete0001 (talk | contribs) (→Solution 3 (Casework)) |
||
(13 intermediate revisions by 6 users not shown) | |||
Line 5: | Line 5: | ||
<math> \textbf{(A)}\ 16\qquad\textbf{(B)}\ 20\qquad\textbf{(C)}\ 26\qquad\textbf{(D)}\ 30\qquad\textbf{(E)}\ 35 </math> | <math> \textbf{(A)}\ 16\qquad\textbf{(B)}\ 20\qquad\textbf{(C)}\ 26\qquad\textbf{(D)}\ 30\qquad\textbf{(E)}\ 35 </math> | ||
− | ==Solution== | + | ==Solution 1== |
If <math>D(n)</math> is even, then the binary expansion of <math>n</math> will both begin and end with a <math>1</math>, because all positive binary numbers begin with a <math>1</math>, and if you switch digits twice, you will have a <math>1</math> at the end. Thus, we are only concerned with the <math>49</math> odd numbers between <math>1</math> and <math>98</math> inclusive. | If <math>D(n)</math> is even, then the binary expansion of <math>n</math> will both begin and end with a <math>1</math>, because all positive binary numbers begin with a <math>1</math>, and if you switch digits twice, you will have a <math>1</math> at the end. Thus, we are only concerned with the <math>49</math> odd numbers between <math>1</math> and <math>98</math> inclusive. | ||
− | All of these odd numbers will have an | + | All of these odd numbers will have an even <math>D(n)</math>. <math>D(n) = 0</math> will be given by the numbers <math>1, 11, 111, 1111, 11111, 111111</math>, which is a total of <math>6</math> numbers. |
We skip <math>D(n) = 2</math> for now, and move to <math>D(n) = 4</math>, which is easier to count. The smallest <math>D(n) = 4</math> happens when <math>n = 10101</math>. To get another number such that <math>D(n) = 4</math>, we may extend any of the five blocks of zeros or ones by one digit. This will form <math>110101, 100101, 101101, 101001, 101011</math>, all of which are odd numbers that have <math>D(n) = 4</math>. To find seven digit numbers that have <math>D(n) = 4</math>, we can again extend any block by one, so long as it remains less than <math>1100001</math> or under. There are five cases. | We skip <math>D(n) = 2</math> for now, and move to <math>D(n) = 4</math>, which is easier to count. The smallest <math>D(n) = 4</math> happens when <math>n = 10101</math>. To get another number such that <math>D(n) = 4</math>, we may extend any of the five blocks of zeros or ones by one digit. This will form <math>110101, 100101, 101101, 101001, 101011</math>, all of which are odd numbers that have <math>D(n) = 4</math>. To find seven digit numbers that have <math>D(n) = 4</math>, we can again extend any block by one, so long as it remains less than <math>1100001</math> or under. There are five cases. | ||
Line 28: | Line 28: | ||
Thus, we know that there are <math>6</math> odd numbers that have <math>D(n) = 0</math>, and <math>16</math> odd numbers that have <math>D(n) = 4</math>, and <math>1</math> number that has <math>D(n) = 6</math>. The remaining odd numbers must have <math>D(n) = 2</math>. This means there are <math>49 - 6 - 16 - 1 = 26</math> numbers that have <math>D(n) = 2</math>, which is option <math>\boxed{C}</math> | Thus, we know that there are <math>6</math> odd numbers that have <math>D(n) = 0</math>, and <math>16</math> odd numbers that have <math>D(n) = 4</math>, and <math>1</math> number that has <math>D(n) = 6</math>. The remaining odd numbers must have <math>D(n) = 2</math>. This means there are <math>49 - 6 - 16 - 1 = 26</math> numbers that have <math>D(n) = 2</math>, which is option <math>\boxed{C}</math> | ||
+ | |||
+ | ==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 <math>111001</math> 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 <cmath>1\dots0\dots1\dots</cmath> | ||
+ | |||
+ | 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=\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}} |
Latest revision as of 21:01, 5 October 2023
Contents
Problem
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
?
Solution 1
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
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 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.
Solution 3 (Casework)
For to be
,
must be in the form
. Note that
must be at least
digits for
to be
Case :
has
digits
=
, there is only
possible value for
when
has
digits.
Case :
has
digits
_ _
, there could be
zero or
zeros between the first digit and the last digit. If there is only
zero, the zero has
possible places. If there are
zeros, there is only
possible placement. Therefore, there are
possible values for
when
has
digits.
Case :
has
digits
_ _ _
, there could be
,
or
zeros between the first digit and the last digit. If there is only
zero, the zero has
possible places. If there are
zeros, there are
possible placements. If there are
zeros, there is only
possible placement. Therefore, there are
possible values for
when
has
digits.
Case :
has
digits
_ _ _ _
, there could be
,
,
or
zeros between the first digit and the last digit. If there is only
zero, the zero has
possible places. If there are
zeros, there are
possible placements. If there are
zeros, there are
possible placements. If there are
zeros, there is only
possible placement. Therefore, there are
possible values for
when
has
digits.
Case :
has
digits
Given by the problem, . We could first count the number of
that is in the form of
_ _ _ _
, where the digits between the second and last digit are in the form of
.
There could be ,
,
,
or
zeros. Therefore, there are
possible values for
when
_ _ _ _
.
There is also the case were . Therefore, there are
possible values for
when
has
digits.
Therefore, the answer is .
small edit ~Mathlete0001
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.
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.