wu :: forums
wu :: forums - Multiplicative function

Welcome, Guest. Please Login or Register.
Aug 8th, 2022, 4:04pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Icarus, towr, Eigenray, SMQ, william wu, Grimbal)
   Multiplicative function
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Multiplicative function  (Read 880 times)
NickH
Senior Riddler
****





   
WWW

Gender: male
Posts: 341
Multiplicative function  
« on: Jan 30th, 2003, 6:36pm »
Quote Quote Modify Modify

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.
IP Logged

Nick's Mathematical Puzzles
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: Multiplicative function  
« Reply #1 on: Jan 30th, 2003, 7:42pm »
Quote Quote Modify Modify

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?
IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Pietro K.C.
Full Member
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Re: Multiplicative function  
« Reply #2 on: Feb 4th, 2003, 3:30pm »
Quote Quote Modify Modify

A word on not-so-hard Putnams: is it me or is the 1985 one (http://www.unl.edu/amc/a-activities/a7-problems/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 Tongue). 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(n0) = n0 for some n0, then f(n) = n for all n < n0 also.
 
Suppose that f(n) is not identically equal to n; then there must be a least n0 such that f(n0) > n0, with f(n) = n for all n < n0. As far as we know right now, this could be anything greater than 2.
 
Suppose this n0 is not a prime or a prime power; then there exist coprime a,b < n0 such that n0 = ab. However, this entails
 
f(n0) = f(ab) = f(a)f(b) = ab = n0.
 
We conclude that, if the set A = {n : f(n) > n} is not empty, its least element must be of the form pk, p a prime.
 
Suppose now that k is greater than 1. We then have
 
f(pk+p) = f(p(pk-1+1)) = f(p)f(pk-1+1) = p(pk-1+1) = pk+p.
 
This implies that f(pk) = pk, 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 ad-lib, 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.
 
« Last Edit: Feb 4th, 2003, 3:31pm by Pietro K.C. » IP Logged

"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: Multiplicative function  
« Reply #3 on: Feb 4th, 2003, 6:20pm »
Quote Quote Modify Modify

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 58th 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!
IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Pietro K.C.
Full Member
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Re: Multiplicative function  
« Reply #4 on: Feb 5th, 2003, 7:00am »
Quote Quote Modify Modify

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. Smiley
IP Logged

"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
BNC
Uberpuzzler
*****





   


Gender: male
Posts: 1732
Re: Multiplicative function  
« Reply #5 on: Feb 5th, 2003, 8:30am »
Quote Quote Modify Modify

Pietro,
 
1980 - 1999 are here:
http://amath.colorado.edu/activities/Putnam/
 
1975-.. here:
http://www.math.niu.edu/~rusin/problems-math/
 
And the winner! : 1938-...
http://www.kalva.demon.co.uk/putnam.html
IP Logged

How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
NickH
Senior Riddler
****





   
WWW

Gender: male
Posts: 341
Re: Multiplicative function  
« Reply #6 on: Feb 9th, 2003, 6:38pm »
Quote Quote Modify Modify

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.
IP Logged

Nick's Mathematical Puzzles
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board