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

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

Page

Toolbox

Search

2020 CIME II Problems/Problem 4

Contents

Problem

Solution

Similar Problems

See also