Hotel Puzzle

Only the room numbers which are perfect square will be left close! There are 31 perfect squares (natural numbers) less than 1000. Hence, 1000 - 31 = 969 will be left open.

Detailed explanation: A room is left close if number of its divisors (including 1 and the number itself) is odd. For example, take room no. 4: Divisors - 1 ( -> close), 2 ( -> open), 4 ( ->close). Hence, finally close.

Now a natural number $n$ can be written in the form of

$n = p^{a}*q^{b}*r^{c}....$

where, $p$ , $q$ , $r$ , $...$ are prime factors of $n$ and $a$ , $b$ , $c$ , $...$ are natural numbers.

Number of divisors,

$D(n) = (a+1)(b+1)(c+1)....$ .

$D(n)$ can be odd only if each of $a, b, c, ...$ is even. This in turn implies that number $n$ is a perfect square.

First, I asked a question to myself: What makes a door closed? The answer is simple: It has to be opened and closed an odd number of times. The only numbers that follow this condition are perfect squares. Hence, 31 are closed, which means 1000-31=169 are open.

Quick solution using numpy :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

import numpy as np

doors = np.array([1 for i in range(1000)])

for n in range(1, 1001):
    # where 1 is a open door, and 0 is closed
    state_change = np.array([1 if i % n == 0 else 0 for i in range(1,1001)])
    doors = (doors + state_change) % 2

print(sum(doors))

int openDoors() { int doorState[1000]; int i = 0; int waiter = 2; int oDoors = 0;

while(i < 1000)
{
    doorState[i++] = 0;
}

while(waiter <= 1000)
{
    i = 0;
    while(i < 1000)
    {
        if( ((i + 1) % waiter) == 0)
        {
            if(doorState[i] > 0)
            {
                doorState[i] = 0;
            }
            else
            {
                doorState[i] = 1;
            }
        }
        i = i + 1;
    }
    waiter = waiter + 1;
}

i = 0;

while(i < 1000)
{
    if(doorState[i++])
    {
        oDoors = oDoors + 1;
    }
}
printf("Open doors = %d", oDoors);

}