21st Putnam 1960

------
 
 
Problem A7

Let f(n) be the smallest integer such that any permutation on n elements, repeated f(n) times, gives the identity. Show that f(n) = p f(n - 1) if n is a power of p, and f(n) = f(n - 1) if n is not a prime power.

 

Solution

A permutation on n elements can be written as a product of disjoint cycles of length <= n. So f(n) is the smallest number divisible by 2, 3, ... , n.

If n is not a power of a prime, then we can write n = rs, with r and s relatively prime and each greater than 1. Then r, s < n - 1, so r and s divide f(n-1) and hence n divides f(n-1). So f(n) = f(n-1). If n = pm+1, then pm divides f(n-1), but not pm+1, so f(n) = p f(n).

 


 

21st Putnam 1960

© John Scholes
jscholes@kalva.demon.co.uk
15 Feb 2002