Problem:
A permutation of the set of positive integers is a sequence such that each element of appears precisely one time as a term of the sequence. For example, is a permutation of [5]. Let be the number of permutations of for which is a perfect square for all . Find with proof the smallest such that is a multiple of .
Solution:
Solution from Andy Niedermier: Every integer in can be uniquely written in the form , where either 1 or square free, that is, a product of distinct primes. Let denote the set {. }.
Note that for to satisfy the square-free property, it must permute for every . To see this, notice that given an arbitrary square-free , in order for to be a square, needs to contribute one of every prime factor in , after which it can take only even powers of primes. Thus, is equal to the product of and some perfect square.
The number of that permute the is equal to
For to divide , we simply need 67 ! to appear in this product, which will first happen in so long as for some and . The smallest such is .
This problem was proposed by Andy Niedermier.
The problems on this page are the property of the MAA's American Mathematics Competitions