In Volume 3 Number 3 of

A Little Number Theory

by Peter MeyerApple GramGreg Enos poses a problem involving 1000 doors and 1000 men. Initially all doors are closed; each man in turn then opens or closes doors as follows: Thekth man opens/closes thekth door and each subsequentkth door. So, e.g., after the first two men have done their thing, the third man opens/closes the 3rd, 6th, 9th, ..., 999th doors.

Query:After all men are through, which doors are open?

Answer:Doornis open if and only ifnis a perfect square.The problem raised, to which I will here provide an answer is: Why?

The reasoning below is based on elementary algebra and number theory. In what follows "iff" stands for "if and only if".

Consider door

n. This is opened/closed by thekth man iffnis divisible byk(as a little reflection will reveal).kmay be 1 orn(the first door is opened by the first man, and the last door is opened or closed by the last man).All doors are initially closed, so after all the men have done their thing door

nwill be open iff it was opened/closed an odd number of times iffnhas an odd number of divisors (including 1 andn).By a well-known number theorem, an integer > 1 may be expressed uniquely as a product of primes > 1, thus:

Clearly the number of divisors of

n(including 1 andn) is:This is odd iff

nis odd for all_{i}+ 1i( 1 <=i<=m) iffnis even for all_{i}i.Thus the number of divisors of

nis odd iffnmay be expressed as a product of primes thus:Since this equals , a perfect square, we have that the number of divisors of

n(including 1 andn) is odd iffnis a perfect square. This completes the proof.

This article has been published only once before,Apple Gram

in, the magazine of the Apple Corps of Dallas.

It appeared in the August 1981 issue on pages 21-22.

Mathematical Software Hermetic Systems Home Page