Open-Close doors puzzle

August 25, 2010

I come across an interesting puzzle on Gulli’s blog.

Given a number N, how may factor does it have? For example 4 has 1, 2 and 4 as factor, total 3. Can we generalize? Yes, we can.

Any number can be expressed as powers of prime numbers. Assume ‘x’ is prime in the following,

N = x^m – then N will have (m+1) factors. It is not necessary that N limits to one prime, an number can be power of more than one prime number.

N = x^m * yⁿ – in this case N will have (n+1)*(m+1) factors.

Here is interesting puzzle from the book introduction to algorithms by Anany V. Levitin,

“Locker doors: There are N lockers in a hallway, numbered sequentially from 1 to N. Initially all the locker doors are closed. You make N passes by the locker, each time starting with locker #1. on the k^th pass. K = 1, 2, … N, you toggle the door of every k^th locker, i.e. if the door is locked, open it and if the door is closed, open it. On the second pass toggle 2^nd, 4^th, 6^th … so on doors. After last pass (N^th) how many doors are closed and how many are opened?”

From the Euler’s analogy, each number except perfect square will even number of factors and perfect squares will have odd number of factors. Using the fact, we can conclude those number which are perfect squares must be toggled odd number of times, and other doors even number of times. Hence only those doors represent perfect square numbers will be toggled from their original position (i.e. they will be in open position if initially closed and vice versa). All other doors will be in their initial position.

Similar sort of puzzle we can found in the book “Heard on the Street”.