Difference between revisions of "1990 AIME Problems/Problem 13"
m (→Problem) |
Mathandski (talk | contribs) |
||
(11 intermediate revisions by 4 users not shown) | |||
Line 2: | Line 2: | ||
Let <math>T = \{9^k : k ~ \mbox{is an integer}, 0 \le k \le 4000\}</math>. Given that <math>9^{4000}_{}</math> has 3817 [[digit]]s and that its first (leftmost) digit is 9, how many [[element]]s of <math>T_{}^{}</math> have 9 as their leftmost digit? | Let <math>T = \{9^k : k ~ \mbox{is an integer}, 0 \le k \le 4000\}</math>. Given that <math>9^{4000}_{}</math> has 3817 [[digit]]s and that its first (leftmost) digit is 9, how many [[element]]s of <math>T_{}^{}</math> have 9 as their leftmost digit? | ||
− | + | ==Solution 1== | |
+ | '''Lemma''': For all positive integers n, there's exactly one n-digit power of 9 that does not have a left-most digit 9 | ||
− | + | ''(Not-so-rigorous) Proof: One can prove by contradiction that there must be at least either one or two n-digit power of 9 for all n. | |
+ | If there is exactly 1 n-digit power of 9, then such a number <math>m</math> cannot begin with 9 since that would result in <math>\frac{m}{9}</math> also being an n-digits, hence a contradiction. Therefore, this single n-digit power of 9 must not begin with 9. In the case that there are 2 n-digit powers of 9, we have already discovered that one of them must begin with 9, let it be <math>9^k = m</math>. The integer <math>9^{k - 1} = \frac{m}{9}</math> must then be an n-digit number that begins with <math>1</math>. '' | ||
+ | |||
+ | |||
+ | Using this lemma, out of the 4001 powers of 9 in T, exactly 3816 must not begin with 9 (one for each digit). Therefore, the answer is <math>4000 - 3816 = \boxed{184}</math> numbers have 9 as their leftmost digits. | ||
+ | |||
+ | ~Edited by Mathandski (with help from a math god) | ||
+ | |||
+ | ==Solution 2== | ||
+ | Let's divide all elements of <math>T</math> into sections. Each section ranges from <math>10^{i}</math> to <math>10^{i+1}</math> And, each section must have 1 or 2 elements. So, let's consider both cases. | ||
+ | |||
+ | If a section has 1 element, we claim that the number doesn't have 9 as the leftmost digit. Let this element be <math>9^{k}</math> and the section ranges from <math>10^{i}</math> to <math>10^{i+1}</math>. To the contrary, let's assume the number (<math>9^{k}</math>) does have 9 as the leftmost digit. Thus, <math>9 \cdot 10^i \leq 9^k</math>. But, if you divide both sides by 9, you get <math>10^i \leq 9^{k-1}</math>, and because <math>9^{k-1} < 9^{k} < 10^{i+1}</math>, so we have another number (<math>9^{k-1}</math>) in the same section (<math>10^i \leq 9^{k-1} < 10^{i+1}</math>). Which is a contradiction to our assumption that the section only has 1 element. So in this case, the number doesn't have 9 as the leftmost digit. | ||
+ | |||
+ | If a section has 2 elements, we claim one has to have a 9 as the leftmost digit, one doesn't. Let the elements be <math>9^{k}</math> and <math>9^{k+1}</math>, and the section ranges from <math>10^{i}</math> to <math>10^{i+1}</math>. | ||
+ | So We know <math>10^{i} \leq 9^{k} < 9^{k+1} < 10^{i+1}</math>. From <math>10^{i} \leq 9^{k} </math>, we know <math>9 \cdot 10^{i} \leq 9^{k+1} </math>, and since <math>9^{k+1} < 10^{i+1}</math>. The number(<math>9^{k+1}</math>)'s leftmost digit must be 9, and the other number(<math>9^{k}</math>)'s leftmost digit is 1. | ||
+ | |||
+ | There are total 4001 elements in <math>T</math> and 3817 sections that have 1 or 2 elements. And, no matter how many elements a section has, each section contains exactly one element that doesn't begin with 9. We can take 4001 elements, subtract 3817 elements that don't have 9 as the leftmost digit, and get <math>\boxed{184}</math> numbers that have 9 as the leftmost digit. | ||
+ | |||
+ | - AlexLikeMath | ||
+ | |||
+ | ==Solution 3== | ||
+ | |||
+ | We know that <math>9</math> is very close to <math>10</math>. But we also know that for all <math>k \in \mathbb{Z}^+</math>, <math>10^k</math> has <math>k+1</math> digits. Hence <math>10^{4000}</math> has <math>4001</math> digits. Now, notice that if a power of <math>9^n</math> has <math>9</math> as the leftmost digit, then <math>9^{n-1}</math> has <math>1</math> as the leftmost digit and will preserve the same number of digits (just due to division). Hence we find that consecutive powers of <math>9</math> are "supposed" to increase by one digit, however, when consecutive powers of <math>9</math> have leading digit <math>1</math> then leading digit <math>9</math> they "lose" this one digit. Therefore, it suffices to find the number of times that <math>9^k</math> has "lost" a digit since the number of times that this occurs shows us the number of pairs where the leading digit of <math>9^k</math> is <math>1</math> and the leading digit of <math>9^{k+1}</math> is <math>9</math>. Hence, we find that <math>9^{4000}</math> is "supposed" to have <math>4001</math> digits, but only has <math>3817</math> digits. Thus, the number of times <math>9^k</math> has lost a digit is <math>4001-3817 = 184</math>. Thus, <math>\boxed{184}</math> elements of <math>T</math> have <math>9</math> as their leading digit. | ||
+ | |||
+ | ~qwertysri987 | ||
== See also == | == See also == |
Latest revision as of 01:18, 10 February 2023
Problem
Let . Given that
has 3817 digits and that its first (leftmost) digit is 9, how many elements of
have 9 as their leftmost digit?
Solution 1
Lemma: For all positive integers n, there's exactly one n-digit power of 9 that does not have a left-most digit 9
(Not-so-rigorous) Proof: One can prove by contradiction that there must be at least either one or two n-digit power of 9 for all n.
If there is exactly 1 n-digit power of 9, then such a number cannot begin with 9 since that would result in
also being an n-digits, hence a contradiction. Therefore, this single n-digit power of 9 must not begin with 9. In the case that there are 2 n-digit powers of 9, we have already discovered that one of them must begin with 9, let it be
. The integer
must then be an n-digit number that begins with
.
Using this lemma, out of the 4001 powers of 9 in T, exactly 3816 must not begin with 9 (one for each digit). Therefore, the answer is numbers have 9 as their leftmost digits.
~Edited by Mathandski (with help from a math god)
Solution 2
Let's divide all elements of into sections. Each section ranges from
to
And, each section must have 1 or 2 elements. So, let's consider both cases.
If a section has 1 element, we claim that the number doesn't have 9 as the leftmost digit. Let this element be and the section ranges from
to
. To the contrary, let's assume the number (
) does have 9 as the leftmost digit. Thus,
. But, if you divide both sides by 9, you get
, and because
, so we have another number (
) in the same section (
). Which is a contradiction to our assumption that the section only has 1 element. So in this case, the number doesn't have 9 as the leftmost digit.
If a section has 2 elements, we claim one has to have a 9 as the leftmost digit, one doesn't. Let the elements be and
, and the section ranges from
to
.
So We know
. From
, we know
, and since
. The number(
)'s leftmost digit must be 9, and the other number(
)'s leftmost digit is 1.
There are total 4001 elements in and 3817 sections that have 1 or 2 elements. And, no matter how many elements a section has, each section contains exactly one element that doesn't begin with 9. We can take 4001 elements, subtract 3817 elements that don't have 9 as the leftmost digit, and get
numbers that have 9 as the leftmost digit.
- AlexLikeMath
Solution 3
We know that is very close to
. But we also know that for all
,
has
digits. Hence
has
digits. Now, notice that if a power of
has
as the leftmost digit, then
has
as the leftmost digit and will preserve the same number of digits (just due to division). Hence we find that consecutive powers of
are "supposed" to increase by one digit, however, when consecutive powers of
have leading digit
then leading digit
they "lose" this one digit. Therefore, it suffices to find the number of times that
has "lost" a digit since the number of times that this occurs shows us the number of pairs where the leading digit of
is
and the leading digit of
is
. Hence, we find that
is "supposed" to have
digits, but only has
digits. Thus, the number of times
has lost a digit is
. Thus,
elements of
have
as their leading digit.
~qwertysri987
See also
1990 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 12 |
Followed by Problem 14 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.