28th Putnam 1967

We are given a sequence a₁, a₂, ... , a_n. Each a_i can take the values 0 or 1. Initially, all a_i = 0. We now successively carry out steps 1, 2, ... , n. At step m we change the value of a_i for those i which are a multiple of m. Show that after step n, a_i = 1 iff i is a square. Devise a similar scheme give a_i = 1 iff i is twice a square.

Solution

a_i is changed once for each divisor of i. If i is non-square then it has an even number of divisors (they come in pairs d, i/d), so a_i ends as 0. If i is square it has an odd number of divisors and so a_i ends as 1.

We change those that a multiple of 2, then those that are a multiple of 4, then those that are a multiple of 6 and so on. This only affects the even numbers and indeed a_2i is changed once for each divisor of i, so the same argument as before shows that a_2i ends as 1 iff i is a square. Note that a_2i+1 is never changed, so it remains 0.

28th Putnam 1967

© John Scholes
jscholes@kalva.demon.co.uk
14 Jan 2002