2020 CIME II Problems/Problem 4

Problem

The probability a randomly chosen positive integer $N<1000$ has more digits when written in base $7$ than when written in base $8$ can be expressed in the form $\tfrac mn$, where $m$ and $n$ are relatively prime positive integers. Find $m+n$.

Solution

If a positive integer $N$ has more digits in base $7$ than base $8$, then $7^k \le N < 8^k$ for some positive integer $k$. There are $8^k-7^k$ positive integers $N$ that satisfy this condition for every positive integer $k$. If $k \geq 4$, $N$ will be greater than $1000$, so we only need to consider $k \le 3$. The number of possible values of $N$ is \[\sum^{3}_{k=1}[8^k-7^k]=8-7+64-49+512-343=185.\] The requested probability is \[\frac{185}{999}=\frac{5}{27},\] and so the answer is $5+27=\boxed{032}$.

Similar Problems

2009 AIME I Problem 6

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 (ProblemsAnswer KeyResources)
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. AMC logo.png