PUMaC 2015 · 数论（A 组） · 第 3 题

PUMaC 2015 — Number Theory (Division A) — Problem 3

[ 4 ] What is the largest positive integer n less than 10 , 000 such that in base 4, n and 3 n have the same number of digits; in base 8, n and 7 n have the same number of digits; and in base 16, n and 15 n have the same number of digits? Express your answer in base 10. 15

解析

[ 4 ] What is the largest positive integer n less than 10 , 000 such that in base 4, n and 3 n have the same number of digits; in base 8, n and 7 n have the same number of digits; and in base 16, n and 15 n have the same number of digits? Express your answer in base 10. Solution: The conditions are basically stating that in each of the three bases, n must appear “alphabet- k 4 ically” before 1111 . . . . Let k , k , and k be the largest positive integers such that 4 < n , 4 8 16 k k k k k 8 16 4 8 16 8 < n , and 16 < n . Then n < 2 · 4 , n < 2 · 8 , and n < 2 · 16 . In other words, 2 k +1 3 k +1 4 k +1 2 k 3 k 4 k 4 8 16 4 8 16 n < 2 , n < 2 , and n < 2 , but n > 2 , n > 2 . and n > 2 . It follows 12 k that the greatest power of 2 that is less than n must be 2 for some integer k (because 12 is the least common multiple of 2, 3, and 4). The largest such k can be 1 if n is to be less than 10 , 000. From here it is easy to see that the largest possible value of n is the smallest of 1111 , 11111 , and 1111111 , and that is 1111 = 4369 . 16 8 4 16 Author: Eric Neyman 15