35th BMO 1999 Problem 4 Find the smallest possible sum of digits for a number of the form 3n 2 + n + 1 (where n is a positive integer). Does there exist a number of this form with sum of digits 1999? Solution
: n = 8 gives 201 with sum of digits 3. Yes, eg take n = 10 222 - 1. The only one digit number has sum of digits 5. 3n 2 + n + 1 = n(3n+1) + 1 and n and 3n+1 have opposite parity, so 3n 2 + n + 1 must be odd. In particular, the last digit cannot be 0, so for n > 1 the number has at least two non-zero digits (the first and the last) and hence the sum of digits is at least 2. It can only be 2 if the number is 10 a + 1 and hence n(3n+1) = 10 a . But n and 3n+1 are relatively prime, so we must have n = 2 a , 3n+1 = 5 a . But (5/2) a > 6 for a > 1, so there are no solutions with a > 1. If a = 1, then n = 2, so 3n+1 = 7 not 5, so a = 1 is not a solution either. Thus the sum of digits cannot be 2. n = 8 gives 201 with sum of digits 3, so that is the best possible. We claim that if n = 10 m - 1, then 3n 2 + n + 1 = 29...950...03, where there are m-1 9s and m-1 0s. Thus if we take m = 222, then we get a number with 221 9s, one 2, one 3 and one 5, so the sum of digits is 1999. To prove the assertion, note that 3n 2 + n + 1 = 3·10 2m - 6·10 m + 3 + 10 m = (3·10 m-1 - 1) 10 m+1 + 5·10 m + 3. Now 3·10 m-1 - 1 is an m-digit number 29...9. Multiplying by 10 m+1 means it is followed by m+1 zero digits. But 5·10 m + 3 is an m+1 digit number 50...03, so the sum is as claimed. 35th BMO 1999 © John Scholes jscholes@kalva.demon.co.uk 18 Jul 2002