Hosted by The Math
Problem of the Week 967
An Unusual Multiplicative Function
MacPOW Home || Math Forum POWs || Search MacPOW
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.
Home || The Math Library || Quick Reference || Search || Help