34th Swedish 1994 Problem 6 Let N be the set of non-negative integers. The function f:N→N satisfies f(a+b) = f(f(a)+b) for all a, b and f(a+b) = f(a)+f(b) for a+b < 10. Also f(10) = 1. How many three digit numbers n satisfy f(n) = f(N), where N is the "tower" 2, 3, 4, 5, in other words, it is 2 a , where a = 3 b , where b = 4 5 ?
100 Solution f(1+0) = f(1) + f(0), so f(0) = 0. f(10+0) = f(f(10)) + f(0), so 1 = f(10) = f(1). Now f(a+b) = f(a) + f(b) for a+b < 10 gives f(2) = 2, f(3) = 3, ... , f(9) = 9. Now putting a = 10 in the first equation gives f(9+k) = f(k) for all k. Hence f(n) = remainder on dividing n by 9. We have 2 k = 1, 2, 4, 8, 7, 5 mod 9 for k = 0, 1, 2, 3, 4, 5 mod 6. So for k a power of 9, we have 2 k = 8 mod 9. But 3 4 5 is a power of 9, so f(N) = 8. So we have to find how many three digit numbers = 8 mod 9. Evidently the smallest is 107 = 9·11 + 8, and the largest is 998 = 9·110 + 8. Hence there are 100. Thanks to Suat Namli 34th Swedish 1994 © John Scholes jscholes@kalva.demon.co.uk 20 February 2004 Last corrected/updated 20 Feb 04