Problem of the Week 967

An Unusual Multiplicative Function

MacPOW 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
x(x+2) = f(3)f(5) = f(15) <= f(18) - 3 = 2 f(9) - 3 <= 2(f(10) - 1) - 3 = = 4 f(5) - 5 <= 4(f(6) - 1) - 5 = 8x - 9 we have
x(x+2) - (8*x-9)<= 0 or (x-3)^2 <= 0 so x = 3.

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:
Mate, Attila: A new proof of a theorem of P. Erdos.
Proc. Amer. Math. Soc. 18 (1967) 159-162.
MR 34 #4234
Katai, I. A remark on additive arithmetical functions.
Ann. Univ. Sci. Budapest. Eotvos Sect. Math. 10 (1967) 81-83.
MR 41 #1666

Here's a quick solution to your #967:
f(3) f(5) = f(15) < f(18) = 2 f(9) < 2 f(10) = 4 f(5), so f(3) < 4. Since f(3) > f(2) = 2, we conclude that f(3) = 3.

© Copyright 2001 Stan Wagon. Reproduced with permission.