

Title: Multiplicative function Post by NickH on Jan 30^{th}, 2003, 6:36pm Here's one from the 1963 Putnam (though that's not where I originally found it) that I think is a bit easier than most Putnams... Suppose {f(n)} is a strictly increasing sequence of positive integers such that: f(2) = 2 f is multiplicative (m and n coprime => f(mn) = f(m)f(n)) Show that f(n) = n for every positive integer n. 

Title: Re: Multiplicative function Post by Icarus on Jan 30^{th}, 2003, 7:42pm Some Putnams aren't that hard. Particularly if you see the trick. This one is pretty straightforward though. Question (I don't know the answer yet): is it still true if you drop "strictly" from the wording? 

Title: Re: Multiplicative function Post by Pietro K.C. on Feb 4^{th}, 2003, 3:30pm A word on notsohard Putnams: is it me or is the 1985 one (http://www.unl.edu/amc/aactivities/a7problems/putnam/1985.pdf) REALLY easy? I'd like to see how other people did this one. My method, particularly the last steps, seem to me open to many alternatives (though I haven't found them :P). It is as follows: Since {f(n)} is strictly increasing and f(2) = 2, it's clear that f(n) >= n for all natural numbers n. Also, if f(n_{0}) = n_{0} for some n_{0}, then f(n) = n for all n < n_{0} also. Suppose that f(n) is not identically equal to n; then there must be a least n_{0} such that f(n_{0}) > n_{0}, with f(n) = n for all n < n_{0}. As far as we know right now, this could be anything greater than 2. Suppose this n_{0} is not a prime or a prime power; then there exist coprime a,b < n_{0} such that n_{0} = ab. However, this entails f(n_{0}) = f(ab) = f(a)f(b) = ab = n_{0}. We conclude that, if the set A = {n : f(n) > n} is not empty, its least element must be of the form p^{k}, p a prime. Suppose now that k is greater than 1. We then have f(p^{k}+p) = f(p(p^{k1}+1)) = f(p)f(p^{k1}+1) = p(p^{k1}+1) = p^{k}+p. This implies that f(p^{k}) = p^{k}, by the observation in the beginning. Hence, min(A) = p, a prime. Now suppose that p > 3; then one of (p+1)/2, (p+3)/2 is odd, and we have f(p+i) = f(2*(p+i)/2) = f(2)f((p+i)/2) = 2*(p+i)/2 = p+i for the appropriate i. So the only choice left is min(A) = 3. This is where we adlib, and where I would like to see alternatives. To show that f(3) = 3, I assumed that f(3) >= 4 and reasoned as follows: f(21) < f(22) <=> f(3)f(7) < f(2)f(11) => 4f(7) < 2f(11) => 2f(7) < f(11) => f(14) < f(11); absurd! So min(A) does not exist, and hence A is empty. We have f(n) = n for all natural numbers n. 

Title: Re: Multiplicative function Post by Icarus on Feb 4^{th}, 2003, 6:20pm Unfortunately I don't remember exactly what I did. It may be that I overlooked the problem with 3. Concerning the 1985 Putnams. I thought it was easier than the 1984 test. I was ranked 58^{th} in '85, whereas I was somewhere in the lower 100s in 1984 (the only other one I competed in.) Apparently not everyone agreed it was that much easier! 

Title: Re: Multiplicative function Post by Pietro K.C. on Feb 5^{th}, 2003, 7:00am I don't have the Putnams prior to 1985... everywhere I look online, it's 1985 onwards. So I mean the "easiness" in comparison with the later ones. For 1985, I was able to do all but two (A6 and B6) of the questions in just over two hours! Not that I sat down with the purpose of timing myself, but the solutions just kept coming. After this burst, it took me another fifty minutes or so to do A6, but I admit B6 still has me stumped. This is in stark contrast to what I have been capable of in the later Putnams  that's why I thought this one might have been consensually considered easier. :) 

Title: Re: Multiplicative function Post by BNC on Feb 5^{th}, 2003, 8:30am Pietro, 1980  1999 are here: http://amath.colorado.edu/activities/Putnam/ 1975.. here: http://www.math.niu.edu/~rusin/problemsmath/ And the winner! : 1938... http://www.kalva.demon.co.uk/putnam.html 

Title: Re: Multiplicative function Post by NickH on Feb 9^{th}, 2003, 6:38pm Pietro, that's a characteristically ingenious solution. My solution is at http://www.qbyte.org/puzzles/p042s.html Icarus, I'm not sure whether the result follows if we remove "strictly" from the wording. I can't derive a contradiction from assuming f(3) = 2, but I may be missing something. 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 