2020 CIME II Problems/Problem 4
Contents
[hide]Problem
The probability a randomly chosen positive integer has more digits when written in base
than when written in base
can be expressed in the form
, where
and
are relatively prime positive integers. Find
.
Solution
If a positive integer has more digits in base
than base
, then
for some positive integer
. There are
positive integers
that satisfy this condition for every positive integer
. If
,
will be greater than
, so we only need to consider
. The number of possible values of
is
The requested probability is
and so the answer is
.
Similar Problems
The intuition behind the above solution:
consider 7^3 = 343 <= N < 8^3 = 512 ; notice that any N in this range will have 4 digits in base 7 ( since 1*7^3 <= N) and since 1*8^3 > N , we have almost 3 digits in base 8 representation of N
its easy to see 3 can be replaced by any positive integer k , where k = 1,2,3
See also
2020 CIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 3 |
Followed by Problem 5 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All CIME Problems and Solutions |
The problems on this page are copyrighted by the MAC's Christmas Mathematics Competitions.