Hosted by The Math
Forum## Problem of the Week 967## An Unusual Multiplicative FunctionMacPOW Home || Math Forum POWs || Search MacPOW
## Solution:I received a few solutions from several of you. Some were correct. Many were not. Here is a solution by Chunwei Song, U of Pennsylvania Let x = f(3). Since And we can now prove that f(n) = n by induction. Assume f(k) = k for k < n. Consider f(n) where n > 3. Since f((n - 2)(n - 1)) = f(n - 2) f(n - 1) = (n - 2)(n - 1), and this argument is greater than n - 1, the amount of space in the interval forces f to be the identity on the interval, so f(n) is n. Dave Witte (Williams College) points out that this is an old Putnam problem related to a theorem of P. Erdos. This problem (in the strong form f(n) = n) was #2 on the morning session of the 1963 Putnam exam. Although you say "increasing," you define this as what I would call "strictly increasing." A theorem of Erdos [Ann Math 47 (1946) 1-20] states, more generally, that if f is an increasing multiplicative function, then f(n) = n^k, for some real number k. (If f is integer-valued, then k has to be a natural number.) As a personal note, I'll mention that I rediscovered this general result when I was an undergrad at the U of Wisconsin [J Undergrad Math 12 (1980) 1-2]. For generalizations, and references to simpler proofs than Erdos, see: Here's a quick solution to your #967: © Copyright 2001 Stan Wagon. Reproduced with permission. |

[**Privacy Policy**]
[**Terms of Use**]

Home || The Math Library || Quick Reference || Search || Help

http://mathforum.org/

17 October 2002